Составители:
Рубрика:
90
2. Пусть w – вершина, в которую мы пришли в ре-
зультате выполнения 1 шага алгоритма и k – но-
мер, присвоенный очередному ребру на этом шаге.
Выбираем произвольное ребро инцидентное вер-
шине w, причем мост выбираем только в крайнем
случае, если других возможностей выбора ребра
не существует. Присваиваем ребру номер k + 1 и
вычеркиваем его
. Процесс длится до тех пор, пока
все ребра не вычеркнут.
Примечание: Мостом называется ребро (рис. 3.1),
удаление которого лишает данный граф связности,
т.е. увеличивает число компонент связности.
Рис. 3.1.
87
строен. Если же некоторые ребра не использованы,
то пусть Ф – только что построенный цикл. Так
как граф G связен, то цикл Ф должен проходить
через некоторую вершину, скажем x
i
, являющуюся
конечной вершиной какого-либо до сих пор не ис-
пользованного ребра. Если удалить все ребра,
принадлежащие Ф, то в оставшемся графе все
вершины по-прежнему будут иметь четную сте-
пень, так как в цикле Ф должно быть четное число
ребер (0 является четным числом), инцидентных
каждой вершине.
Начиная теперь с
x
i
, получаем цикл Ф
′
, на-
чинающийся и оканчивающийся в x
i
. Если все ос-
тавшиеся ранее ребра использованы для цикла Ф
′
,
то процесс окончен. Нужный эйлеров цикл будет
образован частью цикла Ф от вершины x
0
до x
i
, за-
тем циклом Ф′ и, наконец, частью цикла Ф от
вершины x
i
до x
0
. Если же все еще остались неис-
пользованные ребра, то объединение построенных
выше циклов Ф и Ф′ дает новый цикл Ф. Мы снова
можем найти вершину x
j
, принадлежащую циклу и
являющуюся концевой вершиной некоторого не-
использованного ребра. Затем мы можем присту-
пить к построению нового цикла Ф′, начинавшего-
ся в x
j
, и так до тех пор, пока не будут использова-
ны все ребра и не будет получен таким образом
эйлеров цикл Ф. Это доказывает теорему.
2. Пусть w – вершина, в которую мы пришли в ре- строен. Если же некоторые ребра не использованы,
зультате выполнения 1 шага алгоритма и k – но- то пусть Ф – только что построенный цикл. Так
мер, присвоенный очередному ребру на этом шаге. как граф G связен, то цикл Ф должен проходить
Выбираем произвольное ребро инцидентное вер- через некоторую вершину, скажем xi, являющуюся
шине w, причем мост выбираем только в крайнем конечной вершиной какого-либо до сих пор не ис-
случае, если других возможностей выбора ребра пользованного ребра. Если удалить все ребра,
не существует. Присваиваем ребру номер k + 1 и принадлежащие Ф, то в оставшемся графе все
вычеркиваем его. Процесс длится до тех пор, пока вершины по-прежнему будут иметь четную сте-
все ребра не вычеркнут. пень, так как в цикле Ф должно быть четное число
Примечание: Мостом называется ребро (рис. 3.1), ребер (0 является четным числом), инцидентных
каждой вершине.
Начиная теперь с xi, получаем цикл Ф′, на-
чинающийся и оканчивающийся в xi. Если все ос-
тавшиеся ранее ребра использованы для цикла Ф′,
то процесс окончен. Нужный эйлеров цикл будет
образован частью цикла Ф от вершины x0 до xi, за-
тем циклом Ф′ и, наконец, частью цикла Ф от
вершины xi до x0. Если же все еще остались неис-
пользованные ребра, то объединение построенных
выше циклов Ф и Ф′ дает новый цикл Ф. Мы снова
можем найти вершину xj, принадлежащую циклу и
являющуюся концевой вершиной некоторого не-
Рис. 3.1. использованного ребра. Затем мы можем присту-
пить к построению нового цикла Ф′, начинавшего-
удаление которого лишает данный граф связности, ся в xj, и так до тех пор, пока не будут использова-
т.е. увеличивает число компонент связности. ны все ребра и не будет получен таким образом
эйлеров цикл Ф. Это доказывает теорему.
90 87
