Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Гамильтоновы циклы и цепи

Определение. Пусть G псевдограф. Цепь и цикл в G называются гамильтоновыми если они проходят через каждую вершину ровно один раз.
Задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины.
Решение этой задачи проводится с помощью метода ветвей и границ.
Гамильтоновы цепи и циклы относятся к числу специальных маршрутов в графах. Очевидно, что свойство маршрутов: проходить через каждую вершину не более одного раза является латинским, а следовательно, все гамильтоновы циклы и цепи можно получить применяя метод латинской композиции.
В этом случае все гамильтоновы цепи будут перечислены в непустых элементах матрицы L_^n-1(G), за исключением элементов главной диагонали, а все гамильтоновы циклы – в каждом диагональном элементе матрицы L_ⁿ(G).


Контрольные вопросы.



Рисунок 1


Рисунок 2

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

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

Рисунок 3

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

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

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

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

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

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

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