Элементы теории графов. Сюсюкалов А.И - 9 стр.

UptoLike

Составители:

Рубрика:

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

его вершины можно по рёбрам перейти к любой другой. В про-

тивном случае граф называется несвязным.

Определение 1.20. Две вершины графа принадлежат одной

компоненте, если от одной из них до другой можно перейти по

рёбрам графа.

Каждая компонента является связным графом.

Определение 1.21. Граф, вершины которого можно разбить

на два множества (две доли) таким образом, что каждое ребро

будет соединять вершины из разных множеств, называется дву-

дольным.

Очевидно, что графы

G и

G , изображенные на рис. 2, яв-

ляются двудольными. (Вершины одной доли помечены I, второй

– II.) На первый взгляд, граф

G на этом же рисунке не является

двудольным. Однако его вершины можно разбить нужным обра-

зом (см. рис. 3), поэтому он также двудольный. А вот требуемое

разбиение вершин графа

G не существует, и этот граф дву-

дольным не будет.

Теорема 1.7 (Кёнига). Для того, чтобы граф был двудоль-

ным, необходимо и достаточно, чтобы он не содержал циклов

нечётной длины.