Математическое моделирование на графах. Часть 1. Берцун В.Н. - 73 стр.

UptoLike

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

Рубрика:

Глава 2. Плоские и планарные графы 73

Задачи

1. Доказать, что для плоского графа с р компонентами связности

формула Эйлера имеет вид

n – m + f = p + 1.

2. Доказать, что число граней любой укладки планарного связно-

го графа не зависит от выбора укладки.

3. Существует ли эйлеров цикл в графах?

4. Отыскать эйлеровы цепи в графе.

5. Где на выставке следовало бы сделать выход и вход, чтобы

можно было провести экскурсию по всем залам, побывав в каждом

один раз?

6. Найти замкнутый маршрут из вершины А, содержащий все

ребра графа дважды.