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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Х
2
Х
3
Х
6
Х
4
Х
5
Х
1
Рис. 18 Построение цикла
2. -для каждой помеченной вершины x
i
все вершины из множества Г
+1
(x
i
)
помечены, но существуют другие, еще не помеченные вершины;
3.-некоторая вершина, например x
ik
, которая была уже помечена каким-то
знаком (“+” или “-“), может быть помечена теперь (со стороны другой вершины)
знаком, противоположным приписанному вершине x
ik
.
В случае 1 все вершины , помеченные знаком “+” отнесем к множеству X
a
, а
помеченные знаком “-“ - к множеству X
b
. Поскольку все ребра соединяют
вершины , помеченные противоположными знаками, то граф является
двудольным.
Рассмотрим граф на рис. 17,б . Пометим знаком “+”, например, вершину x
1
.
Найдем отображение Г
+
( x
1
) = { x
4
, x
5
}. Вершины x
4
и x
5
пометим знаком “-“.
Отображение Г
+
( x
4
, x
5
) = { x
2
, x
3
}, помечаем вершины x
2
и x
3
знаком “+”. Г
+
( x
2
, x
3
) = { x
4
, x
5
, x
6
}. Оставшуюся непомеченной вершину x
6
помечаем знаком “-“.
Таким образом, получили два подмножества вершин X
a
= { x
1
, x
2
, x
3
} и X
b
= {
x
4
, x
5
, x
6
} и показали, что рассматриваемый граф является двудольным.
Случай 2 означает, что между помеченной и непомеченной вершинами не
существует дуги. Перейдем к неориентированному графу и процедуру пометок
знаками "+" и "-" повторим. Если остались непомеченные вершины, то это
означает, что граф распадается на две или больше частей, и каждая из них
может тогда рассматриваться
отдельно. Итак, в конце приходим к случаю (1).
В графе на рис. 17,в пометки были начаты знаком "+" с вершины х
2
. Г
+
(х
2
) =
{ х
4
}. Вершина х
4
помечается знаком "-". Г
+
(х
4
) = { х
3
}. Вершина х
3
помечается
знаком "+". Г
+
(х
3
) = ∅.
В графе остались непомеченные вершины, но если перейти к
неориентированному двойнику этого графа, то процедура пометок легко
выполняется и множество вершин разбивается на два подмножества
Х
а
= { х
1
, х
2
, х
3
} и Х
b
= { х
4
, х
5
, х
6
}, тем самым исходный граф является
двудольным.
В случае (3) вершина х
ik
должна быть помечена знаком "+" на некотором
маршруте, (например, М
1
), состоящем из вершин х
i1
, x
i2
, ..., x
ik
; причем знаки "+" и
"-", приписываемые этим вершинам при движении по маршруту М
1
должны
образовывать чередующуюся последовательность. Например, для графа на
рис.18. маршрут M
1
можно выбрать таким:
M
1
: x
1
→ x
3
→ x
5
→ x
4 →
x
2
.
"+" "-" "+" "-" "+" 
                    Х1              Х2          Х5




                         Х3         Х4          Х6


                    Рис. 18 Построение цикла



2. -для каждой помеченной вершины xi все вершины из множества Г+1(xi)
помечены, но существуют другие, еще не помеченные вершины;
    3.-некоторая вершина, например xik, которая была уже помечена каким-то
знаком (“+” или “-“), может быть помечена теперь (со стороны другой вершины)
знаком, противоположным приписанному вершине xik.
В случае 1 все вершины , помеченные знаком “+” отнесем к множеству Xa, а
помеченные знаком “-“ - к множеству Xb. Поскольку все ребра соединяют
вершины , помеченные противоположными знаками,                     то граф является
двудольным.
Рассмотрим граф на рис. 17,б . Пометим знаком “+”, например, вершину x1.
Найдем отображение Г+ ( x1 ) = { x4, x5 }. Вершины x4 и x5 пометим знаком “-“.
Отображение Г+ ( x4, x5) = { x2, x3 }, помечаем вершины x2 и x3 знаком “+”. Г+ ( x2, x3
) = { x4, x5, x6 }. Оставшуюся непомеченной вершину x6 помечаем знаком “-“.
Таким образом, получили два подмножества вершин Xa = { x1, x2, x3 } и Xb = {
x4, x5, x6 } и показали, что рассматриваемый граф является двудольным.
Случай 2 означает, что между помеченной и непомеченной вершинами не
существует дуги. Перейдем к неориентированному графу и процедуру пометок
знаками "+" и "-" повторим. Если остались непомеченные вершины, то это
означает, что граф распадается на две или больше частей, и каждая из них
может тогда рассматриваться отдельно. Итак, в конце приходим к случаю (1).
    В графе на рис. 17,в пометки были начаты знаком "+" с вершины х2.         Г+ (х2) =
                                                +
{ х4 }. Вершина х4 помечается знаком "-".      Г (х4) = { х3 }. Вершина х3 помечается
знаком "+".       Г+ (х3) = ∅.
В графе остались непомеченные вершины,                         но если перейти к
неориентированному двойнику этого графа, то процедура пометок легко
выполняется и множество вершин разбивается на два подмножества
Ха = { х1, х2, х3 } и Хb = { х4, х5, х6 }, тем самым исходный граф является
двудольным.
   В случае (3) вершина хik должна быть помечена знаком "+" на некотором
маршруте, (например, М1), состоящем из вершин хi1, xi2, ..., xik; причем знаки "+" и
"-", приписываемые этим вершинам при движении по маршруту М1 должны
образовывать чередующуюся последовательность. Например, для графа на
рис.18.            маршрут          M1        можно             выбрать        таким:
M1: x1 → x3 → x5 → x4 → x2 .
    "+" "-" "+" "-" "+"

Страницы