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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Мы предположили, что длина цикла нечетная. Поэтому из соотношения x
iq
∈X
a
следует, что x
i1
∈X
b
. Это противоречит исходному условию, поскольку X
a
∩ X
b
= ∅ и вершина не может принадлежать одновременно как X
a
, так и X
b
.
Для большей ясности можно рассмотреть цикл нечетной длины для графа
изображенного на рис.18
x
1
---x
3
--- x
5
--- x
4
--- x
2
--- x
1
X
a
X
b
X
a
X
b
X
a
X
b
Поочередно помечая вершины , мы видим противоречие : вершина X
1
∈X
a
и
согласно определению должна принадлежать X
b
, следовательно
рассматриваемый граф не является двудольным.
2. Достаточность
. Предположим, что в графе G не существует цикла нечетной
длины. Выберем одну из вершин графа , например x
i
, и пометим ее “+”. Выполним
итерационную процедуру.
Берем уже помеченную вершину x
i
и помечаем все вершины из множества Г
+1
(x
i
)
знаком, противоположным тому, который присвоен вершине x
i
.
Будем продолжать эту операцию до тех пор , пока:
1. -все вершины не будут помечены, а знаки, приписанные им, согласованы
(иными словами, любые две вершины, соединенные ребром, помечены
противоположными знаками );
x
5
x
4
X
b
X
a
x
1
x
2
x
3
x
1
x
3
x
5
x
2
x
4
x
6
а)
г)
Рис. 17. Двудольные графы. а) , б), в), - двудольные графы
г) - полный двудольный граф.
x
4
”
−
”
x
5
”
−
”
x
6
”
−
”
x
1
”
+
”
x
2
”
+
”
x
3
”
+
”
б)
x
1
x
2
”
+
”
x
3
”
+
”
x
5
x
4
”
−
”
в) 
                                                                    x2”+”
        a                                             x1”+”                                x3”+”
       X
                              x2                 x3
            x1




                                                                    x5”−”
                              x5            x4        x4”−”                           x6”−”
                     Xb                                                     б)
                                    а)


                            x2”+”                                      x3
                                                          x1                          x5
             x1                          x3”+”




                                                               x2                x4
                       x5           x4”−”
                                                                                              x6
                                                                        г)
                           в)
                  Рис. 17. Двудольные графы. а) , б), в), - двудольные графы
                  г) - полный двудольный граф.
Мы предположили, что длина цикла нечетная. Поэтому из соотношения xiq ∈Xa
следует, что xi1 ∈Xb. Это противоречит исходному условию, поскольку    Xa ∩ Xb
                                                               a  b
= ∅ и вершина не может принадлежать одновременно как X , так и X .
Для большей ясности можно рассмотреть цикл нечетной длины для графа
изображенного на рис.18
                              x1 ---x3--- x5--- x4--- x2--- x1
                             Xa Xb Xa Xb Xa Xb
Поочередно помечая вершины , мы видим противоречие : вершина X1 ∈Xa и
согласно определению должна принадлежать Xb ,                    следовательно
рассматриваемый граф не является двудольным.
2. Достаточность. Предположим, что в графе G не существует цикла нечетной
длины. Выберем одну из вершин графа , например xi, и пометим ее “+”. Выполним
итерационную процедуру.
Берем уже помеченную вершину xi и помечаем все вершины из множества Г+1(xi)
знаком, противоположным тому, который присвоен вершине xi.
Будем продолжать эту операцию до тех пор , пока:
1. -все вершины не будут помечены, а знаки, приписанные им, согласованы
   (иными словами, любые две вершины, соединенные ребром, помечены
   противоположными знаками );

Страницы