Связность графа

Операции над множествами

Два множества А и В равны (А=В), если они состоят из одних и тех же элементов.

Например, если А={1, 2, 3, 4}, B={3, 1, 4, 2} то А=В.

Объединением (суммой) множеств А и В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств.

Например, если А={1, 2, 4}, B={3, 4, 5, 6}, то А ∪ B = {1, 2, 3, 4, 5, 6}

Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В.

Например, если А={1, 2, 4}, B={3, 4, 5, 2}, то А ∩ В = {2, 4}

Разностью множеств А и В называется множество АВ, элементы которого принадлежат множеству А, но не принадлежат множеству В.

Например, если А={1, 2, 3, 4}, B={3, 4, 5}, то АВ = {1, 2}

Симметричной разностью множеств А и В называется множество А Δ В, являющееся объединением разностей множеств АВ и ВА, то есть А Δ В = (АВ) ∪ (ВА).

Например, если А={1, 2, 3, 4}, B={3, 4, 5, 6}, то А Δ В = {1, 2} ∪ {5, 6} = {1, 2, 5, 6}

Свойства операций над множествами

Свойства перестановочности:

1)A ∪ B = B ∪ A

2)A ∩ B = B ∩ A

Сочетательное свойство:

3) (A ∪ B) ∪ C = A ∪ (B ∪ C)

4) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Основные понятия теории графов.

Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.

Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Если ребра не имеют ориентации, граф называется неориентированным.

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь.

Цепь маршрут, в котором все ребра попарно различны.

Цикл замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

Граф отношения делимости

Построим граф, изображающий отношение делимости на множестве {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16).

Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).

Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана.

Связными компонентами графа называются подграфы данного графа, вершины которых связаны.