Определение: Граф называется полным, если любые две различные вершины его соединены одним и только одним ребром (или если любые его две вершины смежны).
Полный неориентированный граф с n вершинами обозначается Kn.
К5:
К4:
К3:
Граф G, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие ребра. Вершины графа G и ребра, которые добавлены, также образуют граф. Он называется дополнением графа G до полного графа.
Определение: Дополнением графа G называется граф с теми же вершинами, что и граф G и теми ребрами, которые необходимо добавить графу G, чтобы получился полный граф.
Пример:
G:
Матрица смежности дополнительного графанаходится по формуле:
A ( ) = J – A (G)
где J – матрица смежности полного графа, состоящая полностью из единиц, за исключением элементов диагонали.
Определение: Двудольнымграфом G = (V, X) называется граф, вершины которого разбиты на два пересекающихся класса, т. е.: V = V1 V2, V1∩V2 = Ø, а ребра связывают вершины только из разных классов – не обязательно все пары.
Определение: Если в двудольном графе каждая из вершин класса V1 связана с каждой из вершин класса V2, то граф называется полнымдвудольным и обозначается Km,n , где m – количество вершин первого класса (множество V1), n – количество вершин второго класса (V2). Граф Km,n содержит (m + n) вершин и m·n ребер.
К3,2 K3,3 Двудольный
Определение: Пусть G = (V, X) V = {v1,v2…,vn}. Если вершины графа имеют одинаковую степень δ(vi) = s для всех i { 1, 2, …, n}, то такой граф называется однородным(регулярным).
Теорема 1: Пусть дан однородный граф G = (V, X), V = {v1,v2…,vn}, тогда:
δ(vi) = n·s;
где n – количество вершин; m – количество ребер; s – степень каждой вершины.
Полный граф является однородным.
Теорема 2: Степень каждой вершины полного графа Kn на 1 меньше числа вершин, т. е. s = n – 1
Теорема 3: Если полный граф имеет n вершин, то
Для однородного графа G матрицы смежности и инцидентности связаны соотношением:
Определение: Граф Gp называется реберным, если в качестве вершин его выбраны ребра исходного графа G с m ребрами и n вершинами, имеющего матрицу инцидентности B(G).
В этом случае матрица смежности реберного графа находится по формуле: A (Gp) = BT(G) · B(G) – 2E
Исходный граф G для построения реберного графа Gp необязательно должен быть регулярным. Если все же граф G является регулярным, то и реберный Gp тоже будет регулярным. В общем случае, если ребро xi в графе G ограничено вершинами vj и vk , степень которых равна δ(vj) и δ(vk) , то степень вершины xiв реберном графе Gp определяется по формуле:
δ(xi) = δ(vj) + δ(vk) – 2
Число ребер в реберном графе Gp определяется по формуле: