Упражнения

Рис. 18 Рис. 19

1. Для вершин b, c графа G на рис. 15 привести при­меры маршрута, цепи, простой цепи. Привести примеры циклического маршрута, цикла, простого цикла. Суще­ствует ли в графе G Эйлеров цикл (цепь), гамильтонов цикл (цепь)?

2. Задача о кёнигсбергских мостах была сформу­лирована и решена Эйлером в 1736 г. План расположе­ния семи мостов в Кенинс­берге XVIII века приведен на рис.18. Задача заключа­ется в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку. Существует ли такой обход мостов? Решить задачу графически, для чего построить граф задачи, в котором каж­дая часть города - вершина, а каждый мост - ребро, инцидентное вершинам, относящимся к соединяемым им час­тям суши.

3. Какими свойствами характеризуются отношения дос­тижимости вершин в ориентированных графах G1 – G3 на рис.19? Какой порядок задают отношения достижимости вершин в G1-G3?

Рис. 20

4. Имеют ли пятигранник-призма и пятиугольник с пет­лями в некоторых вершинах гамильтонов цикл (цепь)?

5. Построить матрицы смежности и инцидентности гра­фов G1 - G10 рис.20. Чему равны степени вершин? Имеют ли графы эйлеров цикл (цепь)? Какому отношению соответ­ствует каждый граф (задать отношение матрицей, опреде­лить свойства отношения)? Каковы расстояния между вер­шинами в графах G1 - G7? Какие вершины графов являются центрами? Каковы радиусы этих графов?

6. Для данного графа задать маршруты, цепи, простую цепь, циклический маршрут, цикл, простой цикл

6. Построить эйлеров цикл для графа

6. Содержит ли гамильтонов цикл граф ромбического додекаэдра

6. Определить расстояние между вершинами. Какие вершины можно назвать центрами графа. Чему равны радиусы графа.

Взвешенные графы

11.Докажите, что в связном графе любые две простые цепи максимальной длины имеют общие вершины.

Взвешенный граф − ориентированный граф D=(V,X), на множестве дуг которого определена не которая функция , которую называют весовой функцией. Цифра над дугой (см. рис. 6) − вес дуги (цена дуги). Обозначения: для любого пути П нагруженного ориентированного графа D через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П). Величина l называется длиной пути.

Рис. 21

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

Путь в нагруженном ориентированном графе из вершины v в вершину w, где vw, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный маршрут в нагруженном графе.

Введем матрицу длин дуг C(D)=[cij] порядка n, причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для  дуги , то  минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для  i,j : путь (маршрут)тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) изv в w, содержащих не более k+1 дуг (ребер), то − минимальный путь (маршрут) изv в u среди путей (маршрутов), содержащих не более k дуг (ребер).