Материалы к занятию «Элементы теории графов и их применения»

Приведём решения нескольких задач с помощью привлечения понятия и свойств графов.

Пример 1. На секретной базе 20 отделов, каждый из них связан прямой телефонной связью с 4 другими отделами базы. Сколько всего телефонных линий внутри этой базы?

Решение. Рассмотрим граф G, у которого вершинами будут отделы базы, рёбрами – телефонные линии от одного отдела до другого. Таким образом, этот граф имеет 20 вершин: В 20, а количество его рёбер необходимо найти.

В силу теоремы 1 из § 1 главы 3 удвоенное количество рёбер графа равно сумме степеней всех вершин этого графа.

Поскольку по условию задачи каждая вершина этого графа G имеет степень 4 (т. к. каждый отдел базы соединен ровно с 4 другими отделами отдельными телефонными линиями), то эту сумму степеней всех вершин легко можно найти: 4 20 80. Тогда . Следовательно, количество телефонных линий на базе равно 40.

Пример 2. Оболочка футбольного мяча представляет из себя многогранник, сшитый из 32 фрагментов кожи, 20 из которых – правильные шестиугольники, а 12 – правильные пятиугольники, причем длины сторон у них – одинаковые. Сколько вершин у такого многогранника?

Решение. Найдем сначала – общее число рёбер этого многогранника. Т. к. он имеет 12 пятиугольных и 20 шестиугольных граней, то количество его рёбер, сосчитанных дважды, равно 5 12 + 6 20 180. Получаем равенство 180 2 Р. Отсюда следует, что Р 90.

По условию многогранник имеет 12+20 32 грани, т. е. Г 32. По формуле Эйлера из § 4 главы 3: В+Г Р+2. Отсюда В Р–Г+2 90–32+2 60.

Пример 3. Определите хроматическое число графа на рисунке П.5. Сделайте правильную раскраску десяти вершин этого графа, используя минимальное количество красок.

2

Рис. П.5

Решение. Заметим, что данный граф имеет цикл нечётной длины (например, из рёбер любого треугольника). Следовательно, по теореме Д. Кёнига из § 5 главы 3 он не может быть бихроматическим: .

С другой стороны, ниже показан один из вариантов правильной раскраски его вершины тремя цветами, обозначенными как 1, 2, 3:

Рис. П.6.

Это доказывает, что . Из обоснованных двух неравенств получаем итоговый вывод: .

Задачи

№ 1. В небольшой роще под одним из деревьев заяц пережидал снегопад. Когда снегопад закончился, заяц выскочил из под дерева и бегал по снегу от дерева к дереву, оставляя каждый раз новые следы, и, наконец, спрятался под каким-то из этих деревьев (рис. П.7).

Где сейчас находится заяц? Из-под какого дерева он выскочил?

Рис. П.7. Граф задачи о зайце

№ 2. Можно ли утверждать, что число зрителей, пришедших на стадион смотреть футбольный матч и имеющих среди этих пришедших по нечётному числу знакомых, чётно?

№ 3. Может ли наступить такой момент, что число людей, когда-либо живших на земле и сделавших нечётное число рукопожатий, чётно?

№ 4. Может ли на острове, где из каждого населённого пункта выходит по 3 дороги в другие населённые пункты, быть 100 дорог?

№ 5. В классе 25 человек. Может ли быть так, что 9 из них имеют по 5 друзей каждый, 6 – по 4 друга и 10 – по 3 друга (во всех случаях – в этом же классе!)?

№ 6. В воображаемой стране есть девять городов с названиями «1», «2», …, «9». Путешественник обнаружил, что два города в ней соединяются авиарейсом в том и только том случае, если двузначное число, полученное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9, используя имеющиеся авиарейсы?

№ 7. Покажите, что графы правильных многогранников додекаэдра и икосаэдра:

Додекаэдр	Икосаэдр
Рис. П.8	Рис. П.9

являются планарными, т. е. имеют плоское изоморфное изображение.

№ 8. Можно ли, не отрывая карандаша от бумаги и не проводя линии дважды, нарисовать систему отрезков на рис. П.10?

Рис. П.10

№ 9. Выясните, какими являются изображенные на рис. П.11–П.14 графы: 1) эйлеровым; полуэйлеровым; ни тем и не другим; 2) гамильтоновым; полугамильтоновым; ни тем и не другим. Каждый ответ обосновать теоретически и показать на рисунке соответствующий маршрут (если он существует).

а )

Рис. П.11

б)

Рис. П.12

Рис. П.13 Рис. П.14

№ 10. Можно ли совершить прогулку по городу, план которого изображён на рис. П.15, пройдя в точности один раз по каждому из пятнадцати мостов? Возвращаться в начальную точку пути необязательно. Если такой обход существует, найти его, указав мосты в той последовательности, в которой вы их проходите. Если же такого обхода не существует, объясните, почему это так.

Рис. П.15

№ 11. Пусть m и k – любые целые числа от 0 до 9.

1. Можно ли на плоскости нарисовать правильный -угольник с числом вершин , в котором из половины всех вершин исходит по одной диагонали, из третьей части – по три диагонали, а из остальных вершин – по две диагонали?

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

Ответы обоснуйте с помощью теорем теории графов.

№ 12. В телефонной сети 30 телефонов, причём каждый из них был соединен прямой линией с каждым другим телефоном. После усовершенствования телефонных аппаратов они стали способны передавать входной сигнал по имеющимся линиям далее. Какое наибольшее число линий связи можно ликвидировать, чтобы при этом сигнал от каждого телефона мог дойти до любого из остальных?

№ 13. Определите хроматическое число графов на рисунках: П.11–П.14. Ответы обоснуйте. Сделайте правильную раскраску вершин этих графов, используя минимальное количество красок.

№ 14. Схема линий метрополитена делит лист бумаги, на котором она изображена, на 7 областей (граней). Определите, сколько станций имеет это метро, если число отрезков путей между станциями равно 77.

Ответы

№ 1. Заяц либо выскочил из-под ёлки B и спрятался под ёлкой L, либо – наоборот. № 2. Да, так будет всегда. № 3. Это условие выполняется после любого очередного рукопожатия. № 4. Нет. № 5. Нет. № 6. Нет. № 7. Ответы показаны на рис. П.16 и П.17. № 8. Нет. № 9. а) полуэйлеровый и гамильтоновый; б) полуэйлеровый и гамильтоновый; в) эйлеровый и гамильтоновый; г) полуэйлеровый, не гамильтоновый и не полугамильтоновый. № 10. Граф этой задачи полуэйлеров. Одна из возможных прогулок: BACADCDEDFECFCBF. № 11.1. Нет. № 11.2. . № 12. 406. № 13. а) ; б) ; в) ; г) . № 14.  72.

Граф додекаэдра	Граф икосаэдра
Рис. П.16	Рис. П.17