Разновидности графов

В данном пункте речь пойдёт о простых графах, т.е. графах без петель и кратных рёбер.

1. Граф называется полным, если у него любые две вершины смежные. Обозначаются полные графы как K_n. Примеры полных графов:

K₁ – полный граф с одной вершиной:

K₂ – с двумя:

K₃ – с тремя:

K₄ – полный граф с четырьмя вершинами:

K₅ – полный пятивершинник:

2. Регулярным, или однородным графом степени r называется граф, все вершины которого имеют одинаковую степень r. Очевидно, полный граф K_n является регулярным степени n-1. Пустым графом является дополнение полного графа – граф без ребер, состоящий из изолированных вершин. Так, связный регулярный граф степени 2 называется циклическим графом C_n.

Пример: граф Петерсена.

3. Платоновы графы - графы, образованные вершинами и ребрами 5-ти правильных многогранников – Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. – Земля, вода, огонь, воздух, эфир.

Кликой графа G называется полный подграф G.

4. Двудольные графы. – Графы, в которых можно разбить множество вершин на два непересекающихся подмножества так, чтобы в каждом подмножестве не было смежных вершин, но каждая вершина одного подмножества была смежна некоторым вершинам другого подмножества и наоборот: V₁ÇV₂ = V; V₁ÈV₂ =Æ/ Вершины двудольных графов можно окрасить в два цвета так, что каждое ребро будет окрашено в разные цвета.

Граф называется полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества. Обозначение: K_m,n (К_3,3).