ВУЗ:
Составители:
Рубрика:
Глава 1. Основные понятия теории графов 21
Граф G = (V,E) называется двудольным (или биграфом), если су-
ществует разбиение множества его вершин V на две части (доли)
V = A ∪ B (А ∩ B = ∅) такое, что никакие две вершины из A или из B
не являются смежными. В таком графе G(A, B, E) концы каждого
ребра принадлежат разным долям. Например, на рис. 1.23, в граф не
является двудольным [2, 11, 18].
A
B
A
B
B
аб в
Рис. 1.23
Отметим, что у графа на рис. 1.23, б две любые вершины, при-
надлежащие разным долям, являются смежными. Такие двудольные
графы называются полными и обозначаются через K
n, m
, где n, m –
количество вершин каждой доли. Граф K
1, m
называется звездным.
Утверждение 1.6. Граф является двудольным тогда и только то-
гда, когда все простые циклы в нем имеют четную длину.
Доказательство. Необходимость. Пусть G(A, B, E) – двудольный
граф, имеющий простой цикл нечетной длины a
1
, a
2
,..., a
2j+1
, a
1
, в ко-
тором вершины с нечетными номерами находятся в доле A. Тогда
наличие ребра (a
1
, a
2j+1
) ∈ А противоречит двудольности графа.
Достаточность. Пусть G – связный граф (для несвязного графа
каждую компоненту можно рассматривать отдельно), который не
содержит простых нечетных циклов. Выберем произвольную вер-
шину a
1
∈ G, которую поместим в долю А.
В эту же долю включим все вершины, удаленные от a
1
на четное
число ребер (на четное расстояние). Остальные вершины (с нечет-
ным расстоянием до a
1
∈А) поместим в долю В. Допустим, что во
множестве вершин доли В есть две вершины p, q, соединенные реб-
ром (p,q)∈Е. Рассмотрим две кратчайшие простые цепи (a
1
,p) и
(a
1
,q). Они имеют нечетную длину и хотя бы одну общую вершину.
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
