ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

РЕФЕРАТ

«ТЕОРИЯ ГРАФОВ»

Выполнила:

Зудина Т.В.

Владимир 2001

СОДЕРЖАНИЕ:

1. Введение

2. История возникновения теории графов

3. Основные определения теории графов

4. Основные теоремы теории графов

5. Задачи на применение теории графов

6. Применение теории графов в школьном курсе математики

7. Приложение теории графов в различных областях науки и техники

8. Последние достижения теории графов

9. Вывод

§1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.

Родоначальником теории графов принято считать математика Леонарда
Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. [5]стр. 41-42]:

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто- нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно.

Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

(РИСУНОК 1.1)

По поводу обнаруженного им способа решать задачи подобного рода
Эйлер писал [см. [5]стр. 102-104]:

"Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к
Маринони:

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

Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным.

Так, в нашем случае к участку A ведут пять мостов, а к остальным

– по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка.

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

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.

История с мостами города Кенигсберга имеет современное продолжение.
Откроем, например, школьный учебник по математике под редакцией Н.Я.
Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

Задача № 569. На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?

(РИСУНОК 1.2)

Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров
E или F, чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.

В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-
1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ

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

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

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

(РИСУНОК 2.1)

В дальнейшем вершины графа мы будем обозначать латинскими буквами A,
B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.

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

Определение 2.03. Граф, состоящий только из изолированных вершин, называется нуль-графом.

Обозначение: O' – граф с вершинами, не имеющий ребер (рис. 2.2).

(РИСУНОК 2.2)

Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным.

Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали (рис. 2.3).

(РИСУНОК 2.3)

Определение 2.05. Степенью вершины называется число ребер, которым принадлежит вершина.

Обозначение: p (A) – степень вершины A. Например, на рисунке 2.1: p(A)=2, p(B)=2, p(C)=2, p(D)=1, p(E)=1.

Определение 2.06. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.

На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.

(РИСУНОК 2.4 и 2.5)

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

На рисунке 2.6 изображен исходный граф G, состоящий из четырех вершин и трех отрезков, а на рисунке 2.7 – дополнение данного графа – граф G'.

(РИСУНОК 2.6 и 2.7)

Мы видим, что на рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах (этот вопрос будет рассмотрен подробно далее, в параграфе 5).

Определение 2.08. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.

Например, на рисунке 2.8 показан плоский граф, изоморфный (равный) графу на рисунке 2.5. Однако, заметим, что не каждый граф является плоским, хотя обратное утверждение верно, т. е. любой плоский граф можно представить в обычном виде.

(РИСУНОК 2.8)

Определение 2.09. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

Понятия плоского графа и грани графа применяется при решении задач на
"правильное" раскрашивание различных карт (подробнее об этом – в §4).

Определение 2.10. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Например, на рисунке 2.9 дан граф G', на котором проложен путь от C до
H: (C, F); (F, B); (B, A); (A, H) или (C, D); (D, E); (E, A); (A, H).

(РИСУНОК 2.9)

Определение 2.11. Циклом называется путь, в котором совпадают начальная и конечная точка.

Вот пример цикла, проложенного на графе G (рис. 2.9): (A, B); (B, F);
(F, C); (C, D); (D, E); (E, A).

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

Определение 2.13. Длиной пути, проложенного на цикле, называется число ребер этого пути.

Пример: на графе G (рис. 2.9) проложен простой цикл (A, B); (B, F);
(F, C); (C, D); (D, E); (E, A) длина пути этого цикла равна 6.

Определение 2.14. Две вершины A и B в графе называются связными
(несвязными), если в нем существует (не существует) путь, ведущий из A в B.

Определение 2.15. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

(РИСУНОК 2.10 и 2.11)

На рисунке 2.10 изображен связный граф; на рисунке 2.11 – несвязный
(т. к. существует минимум одна пара несвязных вершин – A и D).

Определение 2.16. Деревом называется связный граф, не содержащий циклов.

Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли (рис.2.12).

(РИСУНОК 2.12)

Определение 2.17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Пример: на рисунке 2.13 изображен лес, состоящий из трех деревьев.

(РИСУНОК 2.13)

Определение 2.13. Дерево, все n вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.

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

§3. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ.

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

Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу его ребер.

Доказательство. Пусть А1, А2, А3, ..., An — вершины данного графа, a p(A1), р(А2), ..., p(An) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A1)+р(А2)+ ... +p(An)=0,5N, или 2(p(A1)+р(А2)+ ...
+p(An))=N , где N — число ребер. (

Теорема 3.2. Число нечетных вершин любого графа четно.

Доказательство. Пусть a1, a2, a3, …, ak — это степени четных вершин графа, а b1, b2, b3, …, bm — степени нечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bm ровно в два раза превышает число ребер графа.
Сумма a1+a2+a3+…+ak четная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать. (

Эта теорема имеет немало любопытных следствий.

Следствие 1. Нечетное число знакомых в любой компании всегда четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное число ребер, четно.

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

Теорема 3.3. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.

Доказательство. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, ..., (n-1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0 и (n-1). Это значит, что из n вершин найдутся две, имеющие одинаковые степени. (

Теорема 3.4. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Доказательство данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n школьников, обменивается фотографиями. В некоторый момент времени выясняется, что двое совершили одинаковое число обменов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершивший его.

Теорема 3.5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

Рисунок 3.1 поясняет условие теоремы. На изображенном графе все 5 простых циклов четные.

(РИСУНОК 3.1)

Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер.

Теорема 3.6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.

Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.

Доказательство этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как •использована при этом теорема 3.6). Для доказательства к исходному графу присоединяем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл ?. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ. (

На этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы 3.7.

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

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

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

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

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

(РИСУНОК 3.2)

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

Это число можно представить в виде суммы: Г=?1+?2+?3+…, где ?3 – число граней, ограниченных тремя ребрами, ?4 — число граней, ограниченных четырьмя ребрами и т. д.

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

Ясно, что (3?3+3?4+3?5+…) < (3?3+4?4+ 5?5+…) или 3Г