Введение в теорию графов. Индивидуальные задания (66

3. Проверьте выполнение неравенства треугольника(u, ) (u, ) ( , ) графе G2 . В частности, найдите тройки вершин, в которых выполняется равенство, и тройки, удовлетворяющие строгому неравенству.

4.

На приведенном графе найдите вершины, наиболее удаленные от вершины m (номер вашего варианта), и расстояние (m,m 10) . Найдите кратчайший путь другой четности между точками m и ( m 10 ) [длина его будет больше

(m,m 10) ].

другой и определите диаметр получившихся одноцветных максимальных подграфов. Меняя раскраску, постарайтесь получить подграф максимально возможного диаметра.

6. Определите диаметр и радиус колеса Wm 5 , звезды Km 5,1 , полного графа Km 5 , цепи Рm 5 , цикла Сm 5 , полного двудольного графа Km 5,m . Сколько центров у каждого из этих графов?

7. Приведите пример практической деятельности, в которой приходится решать задачу нахождения центральной вершины графа.

11

Задание 7 Граф Московского метрополитена

I

1.Сколько висячих вершин имеет граф?

2.Найдите в нем циклы Сm 3 , Сm 4 .

3.С каким максимальным числом вершин граф метро содержит в качестве подграфа полный граф? Перечислите станции – вершины такого графа.

4.Каким станциям соответствуют вершины с максимальной степенью? Чему она равна?

5.Имеются ли две вершины графа, соединенные двумя цепями одинаковой длины без общих других вершин? Если – да, запишите последовательности станций в этих цепях.

II

Выберите в графе метрополитена 9 вершин – станций, две из которых заданы в варианте, так, чтобы максимальный подграф G , определяемый этими вершинами, был связным. Перерисуйте этот подграф, сохранив все ребра, инцидентные этим и только этим вершинам.

1.Выделите в G разными цветами самую длинную простую цепь и простые циклы.

2.Отметьте две наиболее удаленные вершины G и найдите диаметр

графа.

3.Определите число ребер, степень каждой вершины. Проверьте выполнение теоремы Эйлера о сумме степеней вершин.

4.Укажите другие характеристики графа G , которые можно отметить.

III

Что означает каждый из полученных Вами результатов для пассажиров?

13

Варианты выбора начальных станций:

1.Краснопресненская, Охотный ряд.

2.Белорусская, Библиотека имени Ленина.

3.Новослободская, Тургеневская.

4.Проспект Мира, Пушкинская.

5.Комсомольская, Площадь Ильича.

6.Курская, Пролетарская.

7.Таганская, Каширская.

8.Павелецкая, Лубянка.

9.Парк Культуры, Китай-город.

10.Киевская, Третьяковская.

Задание 8 Двухцветная раскраска ребер графа

1.Раскрасьте 3 ребра графа K4 в один цвет, а оставшиеся 3 – в другой так, чтобы получились следующие конфигурации: а) K3 и его дополнение, б) Р4

иего дополнение. Что собой представляют дополнения? Есть ли еще какие-либо двухцветные раскраски K4 ?

2.Раскрасьте 5 ребер графа K5 в один цвет, оставшиеся ребра – в дру-

гой так, чтобы а) получились одноцветные треугольники, б) одноцветных треугольников не было.

В случае (а) подсчитайте число одноцветных циклов C3 и C4 , число висячих вершин в графе каждого цвета. В случае (б) определите вид каждого одноцветного графа.

Докажите теорему: «Если ни в подграфе G1 графа K5 с 5 ребрами, ни в его дополнении G1 нет C3 , то и G1 , и G1 являются цикламиC5 ».

14

3.Раскрасьте 8 случайно выбранных ребер графа K6 в один цвет, ос-

тавшиеся ребра – в другой. Сосчитайте, сколько получилось одноцветных треугольников каждого цвета, одноцветных K4 и C5 .

Повторите это упражнение 10 раз. Отметьте, сколько раз получилось только 2 одноцветных треугольника

а) одного цвета с общей вершиной, б) одного цвета с общей стороной, в) без общих элементов, г) разных цветов с общей вершиной,

д) разных цветов без общей вершин.

Какие из этих случаев невозможны? Осуществите раскраску возможных случаев.

4. 5 городов соединены 5 дорогами так, что в любой тройке городов есть 2 города, соединенных дорогой, и 2 города, которые дорогой не соединены. Докажите, что все дороги образуют цикл C5 .

Справедливо ли аналогичное утверждение для 6 городов, соединенных 6 дорогами?

Как связаны эти задачи с двухцветной раскраской полных графов?

5.Приведите примеры других интерпретаций задачи о реберной раскраске графов.

6.Попробуйте раскрасить ребра графа K7 , каждое либо синей, либо

красной краской так, чтобы в нем было только 4 одноцветных треугольника, причем одного цвета.

15

Задание 9 Головоломка с кубиками

Каждая грань любого из четырех пронумерованных кубиков окрашена в один из четырех цветов: синий (с), красный (к), желтый (ж) и зеленый (з). Требуется поставить кубики друг на друга так, чтобы на каждой боковой грани полученной призмы встречались все четыре цвета.

В вариантах задания раскраска кубиков задана цветами противоположных граней.

Например, запись с 4 з означает, что 4-й кубик имеет развертку

ж к

ск

С

ЖС К

З

К

Ответ должен быть представлен в виде двух последовательностей четырех пар цветов, в которые раскрашены квадраты на противоположных боковых гранях призмы. Например:

ск жз зс кж

. Здесь первые буквы пар с – ж – з – к – цвета на одной

жз зс кж ск

грани призмы 1-го, 2-го, 3-го и 4-го кубиков и вторые буквы к – з – с – ж – на противоположной. Вторая строчка дает расположение цветов на других двух противоположных гранях.

Склейте кубики с заданной раскраской граней, сложите из них столбик с требуемым расположением цветов на боковых гранях и покажите преподавателю полученное решение головоломки.

16

17

Задание 10 Поиск в графах эйлеровых циклов и эйлеровых цепей

I. Определите какие из данных графов являются эйлеровыми и найдите в них эйлеров цикл, нумеруя ребра в порядке их прохода. Если же граф не является эйлеровым, найдите минимальное число эйлеровых цепей, на которые он распадается.

II.На данных рисунках схематично изображены река, острова, полуострова

имосты. Найдите маршрут обхода всех частей суши, который начинался бы и кончался в одном и том же месте и проходил ровно один раз по каждому мосту,

18

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

Задание 11 Обход лабиринта

В каждом варианте даны схемы двух лабиринтов. Требуется обойти их, используя известный алгоритм. При построении обхода направление пути в каждом коридоре указывайте стрелкой, а сам путь рисуйте красным цветом при первом проходе и зеленым при возврате. Переходы нумеруйте в порядке ихвстречивпути.

19

Отмечайте двойными стрелками конец пройденного перехода при первой встрече перекрестка, чтобы возврат по нему проходил лишь в случае отсутствия другого возможного пути из данного перекрестка.

Постройте по заданной Вам упрощенной схеме лабиринта его крупный рисунок с коридорами, перекрестками, поворотами и тупиками и проведите непрерывную кривую-траекторию обхода лабиринта.

При обходе лабиринта помечайте порядковым номером проход каждого коридора. В конце обхода все коридоры окажутся помеченными двумя числами.

20