Графы и сети. Харитонова Е.В. - 86 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

85
ОТВЕТЫ К УПРАЖНЕНИЯМ
Раздел 1.
1.
(а).
3.
(в).
5.
(а), (в).
7.
(б).
9.
Предположим, что граф G связный и ровно две его вершины имеют нечет-
ную степень. Пусть a и b – вершины нечетной степени. Если между a и b
ребро отсутствует, добавим его. Теперь каждая вершина имеет четную сте-
пень, поэтому новый граф имеет эйлеров цикл. В этом цикле следует прохо-
дить и ребро
{a, b}. Например, проходя цикл, мы движемся от а к b. Если
начать с этого ребра и пройти цикл, то легко заметить, что если ребро уда-
лить, начать путь в вершине b и пройти его, следуя циклу, то получим эйле-
ров путь из b в a. Если между a и
b имеется ребро, удалим его. Новый граф
имеет эйлеров цикл, если он по-прежнему связный. Пусть эйлеров цикл на-
чинается и заканчивается в вершине а. Если мы пройдем этот цикл, а затем
проследуем вдоль удаленного ребра от а к b, то получим эйлеров путь от а к
b. Если новый граф
перестал быть связным, то он имеет эйлеров цикл для
компоненты, содержащей вершину а, который начинается и заканчивается в
вершине b. Пройдем эйлеров цикл от а к а, удаленное ребро от а к b, затем
пройдем эйлеров цикл от b к b. В результате получим эйлеров путь от а к b.
Предположим, что граф G имеет эйлеров путь. Пусть, например, он начи-
нается в вершине а и заканчивается в вершине b. После первого ребра пути,
выходящего из а, для каждого ребра пути, который ведет в а, должно суще-
ствовать ребро, выходящего из а. Поэтому вершина а должна иметь нечет-
ную степень.
Аналогично, вершина b должна иметь нечетную степень. В
любых других вершинах, для любого ребра пути, который ведет в эту вер-
шину, должно существовать ребро, которое выходит и этой вершины. По-
этому вершина имеет четную степень.
11.
Если граф сильно связный, то для любой его вершины υ, несомненно, любая
другая вершина достижима из вершины υ, и υ достижима из любой другой
его вершины. Обратно, пусть имеется вершина υ, обладающая указанным
свойством. Пусть а и b – произвольные вершины. Поскольку существует
путь из а в υ и путь и
υ в b, то существует путь из а в b, поэтому рассматри-
ваемый граф сильно связный.
13.
a) acgƒedba; б) abƒecda; в) abihƒdcega; г) не существует; д) не сущест-
вует.
15.
a) abcde; б) abcdeƒ; в) fdcegabih г) egacdfhb д) adbcefgh.
17.
Если граф G имеет гамильтонов цикл, то любое ребро является частью цик-
ла. Но разрезающее ребро не может быть ребром, входящим в цикл. Следо-
вательно, G не содержит разрезающее ребро. Путь {a, b} – разрезающее реб-
ро и компоненты С
1
и С
2
– компоненты, имеющие гамильтоновы циклы, на-

Страницы