1.6. Специальные графы

В этом разделе мы рассмотрим специальные классы графов, часто встречающиеся в теории графов.

Полный граф G — простой граф, в котором каждая пара вершин смежна. Если полный граф G имеет вершин, то он обозначается через Легко видеть, что имеет ребер. В качестве примера на рис. 1.12 представлен граф

Граф G называется однородным, если в нем все вершины имеют равную степень. Если граф G однороден и для всех вершин в G, то G называют -однородным графом. -однородный граф представлен на рис. 1.13.

Рис. 1.12. Граф К.

Рис. 1.13. 4-однородный граф.

Отметим, что является -однородным графом.

Граф называется двудольным графом, если множество его вершин V можно разбить на два таких подмножества , что каждое ребро, принадлежащее Е, имеет одну концевую вершину в подмножестве а другую — в называют двудольным разбиением

Если в простом двудольном графе G с разбиением для каждой-вершины в 1/2 существует ребро то G называют полным двудольным графом и обозначают через если содержит вершин, а

Двудольный граф и полный двудольный граф представлены на рис. 1.14.

Граф называется -дольным, если V можно разбить на k таких подмножеств что каждое ребро графа G имеет одну концевую вершину в некотором подмножестве а другую — в некотором подмножестве Полный -дольный граф G — простой -дольный граф с разбиением множества вершин

Рис. 1.14. а — двудольный граф; б — полный двудольный граф

Рис. 1.15. Полный -дольный граф.

, обладающий таким свойством, что для каждой вершины является ребром графа G. Полный -дольный граф представлен на рис. 1.15.