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

UptoLike

ВУЗ: 

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

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

Рубрика: 

96
Если цикл проходит по графу G, то, по край-
ней мере, одно ребро, инцидентное каждой вер-
шине x
i
нечетной степени, должно проходиться
дважды. (Ребро, проходимое дважды, можно рас-
сматривать как два параллельных ребра – одно ре-
альное и одно искусственное – и каждое из них
проходится один раз). Пусть это ребро (x
i
, x
k
). В
случае нечетности степени d
k
вершины x
k
графа G
добавление искусственного ребра, прежде всего,
сделает d
k
четным, и значит только ребро (x
i
, x
k
)
нужно будет проходить дважды, если ограничить-
ся рассмотрением лишь вершин x
i
и x
k
. В случае,
когда d
k
четно, добавление искусственного ребра
сделает d
k
нечетным, а второе ребро, выходящее из
x
k
, должно быть пройдено дважды (т.е. добавляет-
ся еще одно искусственное ребро). Такая ситуация
сохраняется до тех пор, пока не встретится верши-
на нечетной степени, о чем говорилось выше. Сле-
довательно, чтобы удовлетворить условию воз-
вращения в вершину x
i
, нужно дважды пройти всю
цепь из x
i
в некоторую другую вершину нечетной
степени x
r.
∈
.X
.–
. Это автоматически приводит к
выполнению условия прохождения вершины x
r
.
Аналогично обстоит дело для всех других вершин
x
i.
∈
.X
–
. Это значит что все множество M цепей из
G, определенное выше, должно проходиться дваж-
ды, и так как отсюда вытекает, что каждое ребро
81
вую степень, то в этом графе всегда найдется, либо
единственная изолированная вершина, либо един-
ственная вершина, соединенная со всеми другими.
Содержание этой теоремы хорошо разъясня-
ется задачей: группа, состоящая из n
школьников,
обменивается фотографиями. В некоторый момент
времени выясняется, что двое совершили одинако-
вое число обменов. Доказать, что среди школьни-
ков есть либо один еще не начинавший обмена,
либо один уже завершивший его.
Теорема 2.5. Если у графа все простые циклы чет-
ной длины, то он не содержит ни одного цикла
четной длины.
Суть теоремы в том, что на этом графе не-
возможно найти цикл (как простой, так и непро-
стой) нечетной длины, то есть содержащий нечет-
ное число ребер.
Теорема 2.6. Для того, чтобы граф был эйлеро-
вым, необходимо и достаточно, чтобы он был
связным и все его вершины имели четную степень.
Теорема 2.7. Для того чтобы на связном графе
можно было бы проложить цепь АВ, содержащую
все его ребра в точности по одному разу, необхо-
димо и достаточно, чтобы А и В были единствен-
ными нечетными вершинами этого графа.
Доказательство. 
         Если цикл проходит по графу G, то, по край-   вую степень, то в этом графе всегда найдется, либо
ней мере, одно ребро, инцидентное каждой вер-          единственная изолированная вершина, либо един-
шине xi нечетной степени, должно проходиться           ственная вершина, соединенная со всеми другими.
дважды. (Ребро, проходимое дважды, можно рас-                Содержание этой теоремы хорошо разъясня-
сматривать как два параллельных ребра – одно ре-       ется задачей: группа, состоящая из n школьников,
альное и одно искусственное – и каждое из них          обменивается фотографиями. В некоторый момент
проходится один раз). Пусть это ребро (xi, xk). В      времени выясняется, что двое совершили одинако-
случае нечетности степени dk вершины xk графа G        вое число обменов. Доказать, что среди школьни-
добавление искусственного ребра, прежде всего,         ков есть либо один еще не начинавший обмена,
сделает dk четным, и значит только ребро (xi, xk)      либо один уже завершивший его.
нужно будет проходить дважды, если ограничить-         Теорема 2.5. Если у графа все простые циклы чет-
ся рассмотрением лишь вершин xi и xk. В случае,        ной длины, то он не содержит ни одного цикла
когда dk четно, добавление искусственного ребра        четной длины.
сделает dk нечетным, а второе ребро, выходящее из            Суть теоремы в том, что на этом графе не-
xk, должно быть пройдено дважды (т.е. добавляет-       возможно найти цикл (как простой, так и непро-
ся еще одно искусственное ребро). Такая ситуация       стой) нечетной длины, то есть содержащий нечет-
сохраняется до тех пор, пока не встретится верши-      ное число ребер.
на нечетной степени, о чем говорилось выше. Сле-       Теорема 2.6. Для того, чтобы граф был эйлеро-
довательно, чтобы удовлетворить условию воз-           вым, необходимо и достаточно, чтобы он был
вращения в вершину xi, нужно дважды пройти всю         связным и все его вершины имели четную степень.
цепь из xi в некоторую другую вершину нечетной
степени xr. ∈ .X.–. Это автоматически приводит к       Теорема 2.7. Для того чтобы на связном графе
выполнению условия прохождения вершины xr.             можно было бы проложить цепь АВ, содержащую
Аналогично обстоит дело для всех других вершин         все его ребра в точности по одному разу, необхо-
xi. ∈ .X –. Это значит что все множество M цепей из    димо и достаточно, чтобы А и В были единствен-
G, определенное выше, должно проходиться дваж-         ными нечетными вершинами этого графа.
ды, и так как отсюда вытекает, что каждое ребро                         Доказательство.



                           96                                                    81

Страницы