Основные понятия теории графов. Гладких О.Б - 79 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

98
x
α
в x
β
), соответствующую весу d
αβ
, делая шаг 1.
Добавим искусственные ребра в G, соответст-
вующие ребрам из μ
αβ
, и проделаем это для всех
других цепей из множества M
*
, в результате че-
го получится граф G
–
( M
*
).
4. Сумма весов всех ребер графа G
–
( M
*
), найден-
ная с использованием матрицы [c
ij
] (вес искус-
ственного ребра берется равным весу парал-
лельного ему реального ребра), равна мини-
мальному весу цикла, проходящего по G. При
этом число прохождений цикла по ребру (x
i
, x
j
)
равно общему числу параллельных ребер между
x
i
и x
j
в G
–
( M
*
).
Покажем, что указанный выше алгоритм
строит минимальный цикл. Для этого следует за-
метить, что поскольку на шаге 2 мы используем
минимальное паросочетание, никакие две крат-
чайшие цепи μ
ij
и μ
pq
при таком паросочетании
(скажем, идущие из x
i
в x
j
и из x
p
в x
q
) не могут
иметь общего ребра. Если бы они имели общее
ребро (x
a
, x
b
), то сочетание вершин x
i
и x
q
(исполь-
зующее подцепи от x
i
к x
b
и от x
b
к x
q
) и сочетание
пары вершин x
p
и x
j
(использующее подцепи от x
p
к
x
a
и от x
a
к x
j
) давало бы общее паросочетание веса
2c
ab
, меньшего чем вес первоначального паросоче-
тания, что противоречит предположению о мини-
мальности исходного паросочетания. Следова-
тельно, граф G
–
( M
*
)не должен содержать более
79
шин. Подсчитаем число ребер, сходящихся в каж-
дой вершине, и просуммируем эти числа. Это рав-
носильно нахождению суммы степеней всех вер-
шин. При таком подсчете каждое ребро будет уч-
тено дважды (оно ведь всегда соединяет две вер-
шины).
Отсюда следует:
p(A
1
) + р(А
2
) + ... + p(An) = 0,5N,
или
2 (p(A
1
) + р(А
2
) + ... + p(An)) = N ,
где N – число ребер.
Теорема 2.2. Число нечетных вершин любого
графа четно.
Доказательство.
Пусть a
1
, a
2
, a
3
, …, a
k
– это степени четных
вершин графа, а b
1
, b
2
, b
3
, …, b
m
– степени нечет-
ных вершин графа. Сумма
a
1
+ a
2
+ a
3
+…+ a
k
+ b
1
+ b
2
+ b
3
+…+ b
m
ровно в два раза превышает число ребер графа.
Сумма a
1
+ a
2
+ a
3
+…+ a
k
четная (как сумма чет-
ных чисел), тогда сумма
b
1
+ b
2
+ b
3
+…+ b
m
должна быть четной. Это возможно лишь в том
случае, если m – четное, то есть четным является и
число нечетных вершин графа. Что и требовалось
доказать. 
   xα в xβ), соответствующую весу dαβ, делая шаг 1.    шин. Подсчитаем число ребер, сходящихся в каж-
   Добавим искусственные ребра в G, соответст-         дой вершине, и просуммируем эти числа. Это рав-
   вующие ребрам из μαβ, и проделаем это для всех      носильно нахождению суммы степеней всех вер-
   других цепей из множества M *, в результате че-     шин. При таком подсчете каждое ребро будет уч-
   го получится граф G – ( M *).                       тено дважды (оно ведь всегда соединяет две вер-
4. Сумма весов всех ребер графа G – ( M *), найден-    шины).
   ная с использованием матрицы [cij] (вес искус-            Отсюда следует:
   ственного ребра берется равным весу парал-
   лельного ему реального ребра), равна мини-                   p(A1) + р(А2) + ... + p(An) = 0,5N,
   мальному весу цикла, проходящего по G. При          или
   этом число прохождений цикла по ребру (xi, xj)                2 (p(A1) + р(А2) + ... + p(An)) = N ,
   равно общему числу параллельных ребер между         где N – число ребер.
   xi и xj в G – ( M *).                               Теорема 2.2. Число нечетных вершин любого
       Покажем, что указанный выше алгоритм            графа четно.
строит минимальный цикл. Для этого следует за-                            Доказательство.
метить, что поскольку на шаге 2 мы используем                Пусть a1, a2, a3, …, ak – это степени четных
минимальное паросочетание, никакие две крат-           вершин графа, а b1, b2, b3, …, bm – степени нечет-
чайшие цепи μij и μpq при таком паросочетании          ных вершин графа. Сумма
(скажем, идущие из xi в xj и из xp в xq) не могут           a1 + a2 + a3 +…+ ak + b1 + b2 + b3 +…+ bm
иметь общего ребра. Если бы они имели общее            ровно в два раза превышает число ребер графа.
ребро (xa, xb), то сочетание вершин xi и xq (исполь-   Сумма a1 + a2 + a3 +…+ ak четная (как сумма чет-
зующее подцепи от xi к xb и от xb к xq) и сочетание    ных чисел), тогда сумма
пары вершин xp и xj (использующее подцепи от xp к                       b1 + b2 + b3 +…+ bm
xa и от xa к xj) давало бы общее паросочетание веса    должна быть четной. Это возможно лишь в том
2cab, меньшего чем вес первоначального паросоче-       случае, если m – четное, то есть четным является и
тания, что противоречит предположению о мини-          число нечетных вершин графа. Что и требовалось
мальности исходного паросочетания. Следова-            доказать.
тельно, граф G – ( M *)не должен содержать более

                           98                                                      79

Страницы