Реферат: Теория графов

Теорема 3.8. Если данный граф является связ­ным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу.

Теорема 3.9. Различных деревьев с n перенумерованными вершинами можно построить n^{n -2} .

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Се­годня двоичные деревья используются не только ма­тематиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).

Теорема 3.10. Полный граф с пятью верши­нами не является плоским.

Доказательство . Воспользуемся формулой Эйлера: В-Р+Г =2, где В — число вершин плоского графа, Р — число его ре­бер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого. На рисунке 3.2, а изображен граф, к которому формула не применима — заштрихованный много­угольник находится внутри другого. Справа приведено изображение графа, к которому формула применима.

(РИСУНОК 3.2)

Эту формулу можно доказать методом математиче­ской индукции. Это доказательство мы опускаем. За­метим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с дру­гом (рис. 3.2). Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если че­рез φ₁ обозначить число таких граней, то φ₂ =0. Далее рассуждаем от противного, а именно: пред­положим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В =5, число ребер Р =10, тогда число граней Г =2-В +Р =2-5+10=7.

Это число можно представить в виде суммы: Г =φ₁ +φ₂ +φ₃ + …, где φ₃ – число граней, ограниченных тремя ребрами, φ₄ — число граней, ограниченных че­тырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р =20=3φ₃ + 4φ₄ +... . Умножив равенство Г =7=φ₃ + φ₄ + φ₅ + … на три, получим ЗГ =21=3( φ₃ + φ₄ + φ₅ + …).

Ясно, что (3φ₃ + 3φ₄ +3φ₅ +…) < (3φ₃ + 4φ₄ + 5φ₅ + …) или 3Г <2Р , но по условию, 2Р =20, а ЗГ =21; поэтому вывод, полученный при введенном нами предположе­нии (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским. ‡

Теорема 3.11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.

В заключение этого параграфа, на наш взгляд, следует упомянуть то, что в нем объяснялись только основные теоремы теории графов. Их практическое применение будет рассмотрено в следующих параграфах реферата.

§4. ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.

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

Задача 4.1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств:

1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;

2. учитель литературы может дать один, либо второй, либо третий урок;

3. математик готов дать либо только первый, либо только второй урок;

4. преподаватель физкультуры согласен дать только последний урок.

Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?

Решение. Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф в виде дерева. Требуемый граф изображен на рисунке 4.1. На нем выделены три возможных варианта расписания уроков.

(РИСУНОК 4.1)

Данная задача является классическим примером удачного использования теории графов. В настоящее время существует программа "Расписание 3.0" компьютерной фирмы ЛинTex, в которой она решена с использованием современных технологий.

Рассмотрим еще одну задачу, решением которой также является граф.

Задача 4.2. В составе экспедиции должно быть 6 специалистов: биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A , B , C , D , E , F , G иH . Обязанности биолога могут исполнять E иG , врача – A иD , синоптика – F иG , гидролога – B иF , радиста – С иD , механика – C иH . Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B ,D – без H и C , C не может ехать вместе с G , A – вместе с B ?

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

Применительно к задаче об экспедиции одна группа вершин есть группа из 8 кандидатов, а вторая – из 6 должностей. Решение задачи изображено на четном графе (рис 4.2).

(РИСУНОК 4.2)

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

Решение. Пусть A и B – данные города. Докажем сначала, что из A в B можно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую, не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются).