6. Типы графов

Граф называют полным, если для любой пары вершин и в X существует ребро в , т.

Рис. 1.5 (а) Симметрический граф, (б) Антисимметрический граф, (в) Полный симметрический граф, (г) Полный антисимметрический граф.

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

Антисимметрическим графом ¹) называется такой граф, для которого справедливо следующее условие: если то в множестве А нет противоположно ориентированной дуги, т. е. . Очевидно, что в антисимметрическом графе нет петель.

На рис. 1.5(а) показан симметрический граф, а на рис. 1.5(б)-антисимметрический граф.

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

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

Неориентированный граф G=(X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Х^а и Х^b, что каждое ребро имеет один конец в Х^а,с другой в Х^b. Ориентированный граф G называется двудольным, если его неориентированный двойник —двудольный граф. Легко доказать следующее утверждение.

Теорема 1. Неориентированный граф G является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

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

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

Граф G=(X, А) называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произвольные две дуги графа не пересекаются друг с другом. На рис. 1.6(а) показан полный граф К₅, а на рис. 1.6(б)—полный двудольный граф К_3,3, которые являются непланарными.

Рис. 1.6. Непланарные графы Куратовского. (a) K₅. (б) K_3,3.