Операция дополнения графа

Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

Обозначение.

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

Понятие связного графа. Понятие компоненты связности. Сильная связность, односторонняя связность, слабая связность.

Граф (орграф) называется связным (сильно связным), если для любых двух его вершинv,w существует маршрут (путь), соединяющийv,w (изv иw).

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

Говорят, что два узла гл и v2 сильно связаныв орграфе G, если существует путь (ориентированная цепь) как из v1в v2,так и из v2в гл. Говорят, что два узла гл и v2 односторонне связаныв орграфе G,если существует путь либо из гл в v2,либо из v2в гл. Говорят, что два узла v1 иv2 слабо связаныв орграфе G,если они связаны в графе G',полученном из Gзабыванием ориентации дуг.

Матрица смежности вершин графа (орграфа).

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и – 1, если дуга заходит в нее.

Матрица инцидентности графа (орграфа).

Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m, здесь n – число вершин графа, m– число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.

В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1. То же самое, но наиболее структурировано:

Неориентированный граф

1 – вершина инцидентна ребру

0 – вершина не инцидентна ребру

Ориентированный граф

1 – вершина инцидентна ребру, и является его началом

0 – вершина не инцидентна ребру

-1 – вершина инцидентна ребру, и является его концом

Понятие плоского графа.

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

Для всякого связного плоского графа верно равенство: n – m + f = 2, где n – число вершин m — число ребер, a f— число граней графа.

Понятие подграфа.

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

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

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

Понятие планарного графа.

Планарный граф — граф, который может быть изображён на плоскости без пересечения ребер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, т.е. графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями.

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

Понятие грани планарного графа.

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

Понятие границы планарного графа.

21. Планарные/непланарные графы. (Теоремы). Критерии планарности.

Существуют и непланарные графы. Показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K₅ и K_3,3 соответственно.

Двудольный граф — это граф, вершины которого разбиты на две доли (части), а ребра проходят только между вершинами из разных частей.

Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.

Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К_3,3) нельзя уложить на плоскость.

Доказательство. По формуле Эйлера граф имеет 5 граней.

С другой стороны: любая грань (включая внешнюю) содержит не менее 4 рёбер. Поскольку каждое ребро включается в ровно две грани, получается соотношение , F — количество граней, E — количество рёбер. Подставляем в это неравенство F = 5 и E = 9 и видим, что оно не выполняется.

Формула Эйлера. Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K₅) или графу «домики и колодцы» (K_3,3).

Признакинепланарныхграфов: достаточное условие — если граф содержит двудольный подграф K_3,3 или полный подграф K₅, то он является не планарным; необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.