Реферат: Теория графов
ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
РЕФЕРАТ
«ТЕОРИЯ ГРАФОВ»
Выполнила:
Зудина Т.В.
Владимир 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).
Страницы: 1, 2
| 
