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

UptoLike

ВУЗ: 

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

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

Рубрика: 

80
Следствие 1. Нечетное число знакомых в любой
компании всегда четно.
Следствие 2. Число вершин многогранника, в ко-
торых сходится нечетное число ребер, четно.
Следствие 3. Число всех людей, когда-либо по-
жавших руку другим людям, нечетное число раз,
является четным.
Теорема 2.3. Во всяком графе с n вершинами, где
n
больше или равно 2, всегда найдутся две или бо-
лее вершины с одинаковыми степенями.
Доказательство.
Если граф имеет n вершин, то каждая из них
может иметь степень 0, 1, 2, ..., (n – 1). Предполо-
жим, что в некотором графе все его вершины
имеют различную степень, то есть, и покажем, что
этого быть не может. Действительно, если
р(А).=.0,
то это значит, что А – изолированная вершина, и
поэтому в графе не найдется вершины Х со степе-
нью р(Х) = n – 1. В самом деле, эта вершина долж-
на быть соединена с (n – 1) вершиной, в том числе
и с А, но ведь А оказалась изолированной.
Следо-
вательно, в графе, имеющем n вершин, не могут
быть одновременно вершины степени 0 и (n – 1).
Это значит, что из n
вершин найдутся две, имею-
щие одинаковые степени.
Теорема 2.4. Если в графе с n вершинами (n боль-
ше или равно 2) только одна пара имеет одинако-
97
из G
–
(M) должно проходиться один раз, то теоре-
ма доказана.
Алгоритм решения задачи китайского поч-
тальона немедленно следует из доказанной теоре-
мы, так как все, что для этого необходимо, состоит
в нахождении множества цепей M
*
(цепного паро-
сочетания для множества вершин нечетной степе-
ни), дающего наименьший дополнительный вес.
Цикл наименьшего веса, проходящий по G, будет
иметь вес, равный сумме весов всех ребер из G
плюс сумма весов ребер в цепях из M
*
. Это то же
самое, что и сумма весов всех ребер – реальных и
искусственных – графа G
–
(M
*
).
Описание алгоритма решения задачи китайского
почтальона
1. Пусть [c
ij
] – матрица весов ребер G. Используя
алгоритм нахождения кратчайшей цепи, образу-
ем |.X
–
|
*
| X
–
| – матрицу D = [d
ij
], где d
ij
– вес це-
пи наименьшего веса, идущей из некоторой
вершины x
i.
∈
.X
–
в другую вершину x
j
∈
X
–
.
2. Найдем то цепное паросочетание M
*
для мно-
жества X
–
, которое дает наименьший вес (в со-
ответствии с матрицей весов D). Это можно
сделать эффективно с помощью алгоритма ми-
нимального паросочетания.
3. Если вершина x
α
сочетается с другой вершиной
x
β
, то определим цепь μ
αβ
наименьшего веса (из 
Следствие 1. Нечетное число знакомых в любой           из G – (M) должно проходиться один раз, то теоре-
компании всегда четно.                                 ма доказана.
Следствие 2. Число вершин многогранника, в ко-               Алгоритм решения задачи китайского поч-
торых сходится нечетное число ребер, четно.            тальона немедленно следует из доказанной теоре-
Следствие 3. Число всех людей, когда-либо по-          мы, так как все, что для этого необходимо, состоит
жавших руку другим людям, нечетное число раз,          в нахождении множества цепей M * (цепного паро-
является четным.                                       сочетания для множества вершин нечетной степе-
Теорема 2.3. Во всяком графе с n вершинами, где        ни), дающего наименьший дополнительный вес.
n больше или равно 2, всегда найдутся две или бо-      Цикл наименьшего веса, проходящий по G, будет
лее вершины с одинаковыми степенями.                   иметь вес, равный сумме весов всех ребер из G
                 Доказательство.                       плюс сумма весов ребер в цепях из M *. Это то же
      Если граф имеет n вершин, то каждая из них       самое, что и сумма весов всех ребер – реальных и
может иметь степень 0, 1, 2, ..., (n – 1). Предполо-   искусственных – графа G – (M *).
жим, что в некотором графе все его вершины              Описание алгоритма решения задачи китайского
имеют различную степень, то есть, и покажем, что                                почтальона
этого быть не может. Действительно, если р(А).=.0,     1. Пусть [cij] – матрица весов ребер G. Используя
то это значит, что А – изолированная вершина, и           алгоритм нахождения кратчайшей цепи, образу-
поэтому в графе не найдется вершины Х со степе-           ем |.X –| * | X –| – матрицу D = [dij], где dij – вес це-
нью р(Х) = n – 1. В самом деле, эта вершина долж-         пи наименьшего веса, идущей из некоторой
на быть соединена с (n – 1) вершиной, в том числе         вершины xi. ∈ .X – в другую вершину xj ∈ X –.
и с А, но ведь А оказалась изолированной. Следо-       2. Найдем то цепное паросочетание M * для мно-
вательно, в графе, имеющем n вершин, не могут             жества X –, которое дает наименьший вес (в со-
быть одновременно вершины степени 0 и (n – 1).            ответствии с матрицей весов D). Это можно
Это значит, что из n вершин найдутся две, имею-           сделать эффективно с помощью алгоритма ми-
щие одинаковые степени.                                   нимального паросочетания.
Теорема 2.4. Если в графе с n вершинами (n боль-       3. Если вершина xα сочетается с другой вершиной
ше или равно 2) только одна пара имеет одинако-           xβ, то определим цепь μαβ наименьшего веса (из


                           80                                                          97

Страницы