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

UptoLike

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

Рубрика:

д)

16.

а) б)

в) г)

д)

17. Докажите теорему. Если граф G имеет разрезающее ребро, то граф G

не может иметь гамильтонов цикл. Если компоненты графа, полученные при

удалении разрезающего ребра, имеют гамильтоновы циклы, то граф G имеет

гамильтонов путь.

18. Нарисуйте граф с шестью вершинами, который имеет гамильтонов

цикл, но не имеет эйлерова цикла.

19.

Нарисуйте граф с шестью вершинами, который имеет эйлеров цикл,

но не имеет гамильтонова цикла.

III. Используйте алгоритм Дейкстры для нахождения в приведенных ни-

же графах, кратчайшего расстояния между вершинами υ

и υ.

a b

b c

i g

a b c

d e

i h

a b c

d e

i h