Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 31 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

На рис.16 показаны непланарные графы. Эти два графа играют важную роль
в теории планарных графов и известны как графы Куратовского.
Неориентированный граф G = (X, A)называют
двудольным, если множество
его вершин X может быть разбито на такие два подмножества X
a
и X
b
, что
каждое ребро имеет один конец в X
a
, а другой в X
b
(рис.17а).
Ориентированный граф G называется
двудольным, если его
неориентированный двойник - двудольный граф (рис.17б,в).
Двудольный граф G=(X
a
∪X
b
,A) называют полным, если для любых двух
вершин x
i
∈X
a
и x
j
∈X
b
существует ребро (x
i
,x
j
) в G=(X,A).(рис.14.г).
Для доказательства двудольности графа существует теорема .
3.1.1.Теорема о двудольности
Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит
циклов нечетной длины.
Доказательство.
1.Необходимость. Поскольку множество X разбивается на две части X
a
и X
b
, то
X
a
∪ X
b
= X и X
a
∩ X
a
= ∅.
Пусть существует цикл нечетной длины x
i1
, x
i2
, ...,x
iq
, x
i1
. Без потери общности
допустим, что x
i1
∈X
a
. Согласно определению одна из двух следующих друг за
другом вершин этого цикла должна принадлежать множеству X
a
, а другая -
множеству X
b
, тогда имеем: x
i2
∈X
б
, x
i3
∈ X
a
и т.д. Следовательно, x
ik
∈X
a
, если к -
нечетное, и x
ik
∈X
b
, если к -четное.
Рис. 16. Непланарные графы.
     На рис.16 показаны непланарные графы. Эти два графа играют важную роль
в теории планарных графов и известны как графы Куратовского.




                         Рис. 16. Непланарные графы.
     Неориентированный граф G = (X, A)называют двудольным, если множество
его вершин X может быть разбито на такие два подмножества Xa и Xb, что
каждое ребро имеет один конец в Xa, а другой в Xb (рис.17а).
    Ориентированный граф         G называется двудольным,                если   его
неориентированный двойник - двудольный граф (рис.17б,в).
    Двудольный граф G=(Xa∪Xb,A) называют полным, если для любых двух
вершин xi ∈Xa и xj∈Xb существует ребро (xi,xj) в G=(X,A).(рис.14.г).
     Для доказательства двудольности графа существует теорема .

                        3.1.1.Теорема о двудольности
Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит
циклов нечетной длины.

Доказательство.
1.Необходимость. Поскольку множество X разбивается на две части Xa и Xb, то
Xa ∪ Xb = X и Xa ∩ Xa = ∅.
Пусть существует цикл нечетной длины xi1, xi2, ...,xiq, xi1. Без потери общности
допустим, что xi1∈Xa. Согласно определению одна из двух следующих друг за
другом вершин этого цикла должна принадлежать множеству Xa, а другая -
множеству Xb, тогда имеем: xi2 ∈Xб, xi3 ∈ Xa и т.д. Следовательно, xik ∈Xa, если к -
нечетное, и xik ∈Xb, если к -четное.

Страницы