Графы и их построения

Графы и их применение

Содержание

Введение…………………………………………………………………………3-4

I.Теория графов………………………………………………………………..5-20

1.1 Задача о кенигсбергских мостах ………………………………6-7

1.2.1 Графы изоморфные ………………………………………………7-9

1.2.2.Плоские графы. Эйлеровы графы. Деревья……………………..9-13

1.2.3. Ориентированные графы ……………………………………………..13-15

1.3. Классические задачи теории графов…………………………….15-20

1.3.1. Графы игр…………………………………………………….....15-17

1.3.2. Задача коммивояжера и обратная задача……………………..17-19

1.3.3. Задача о четырёх красках. Теория Рамсея ……………………19-20

II. Применение теории графов при решении задач………………………...20-28

2.1. Подсчет числа ребер……………………………………………...20-21

2.2. Эйлеровы графы…………………………………………………..21-23

2.3. Деревья………………………………………………………….....23-24

2.4. Плоские графы ……………………………………………………24-25

2.5. Ориентированные графы…………………………………………25-27

2.6 Знакомства, теория Рамсея……………………………………...27-28

III. Применение теории графов в транспортной сфере …………………...29-31

3.1 Маршруты школьного автобуса .…………………………….29-31

Описание…………………………………………………………………..32

Заключение………………………………………………………………..33

Список используемой литературы………………………………………34

Введение

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

Что же такое граф? Графом в математике называется конечная совокупность точек изображенных на плоскости, некоторые пары из которых соединены линиями. Точки называются вершинами графа, линии - ребрами. Основами теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кенигсбергских мостах: через город Кенигсберг протекает река Прегель. В пределах города она омывает два острова. С берегов острова были перекинуты мосты. Кенигсбергцы задумались: «Можно ли пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка».

Решая эту задачу, Эйлер сформулировал свойства графа:

• Если все вершины графа четные, то можно одним росчерком (т.е не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.

• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины и заканчивать на другой нечетной вершине.

• Граф более чем с двумя нечетными вершинами невозможно начертить одним росчерком.

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

Актуальность темы:

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

Цель проекта:

Создание различных схем маршрута школьного автобуса.

Задачи:

1. Разработать оптимальный маршрут следования школьного автобуса.

2. Изучение теории, применение ее при решении задач.

Объект исследования:

Территория вокруг школы№3г. Джанкоя.

1. ТЕОРИЯ ГРАФОВ

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии - рёбрами.

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

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

( ЗАДАЧА О КЕНИГСБЕРГСКИХ МОСТАХ)

Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

рис.3

Кенигсбергцы рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось известному математику Леонардо Эйлеру. Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты « вытянул» в линии, как показано на рисунке 3 а, б.

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

Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:

• Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.

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

• Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

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

1.2.1. ГРАФЫ ИЗОМОРФНЫЕ

В 1859 г. английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр(12-гранник), в вершинах которого вбиты гвоздики (рис. 4). Каждая из 20 вершин была помечена названием одного из крупных городов мира - Дели, Брюссель, Кантон и т.д. Требовалось найти замкнутый путь, проходящий по ребрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики.

рис.4

Игрушка не имела такой популярности, какой еще недавно пользовался «кубик Рубика», но оставила след в математике. Кубик Рубика стал необыкновенно популярной головоломкой, изобретенной в 1975 году преподавателем архитектуры Будапешта Эрне Рубиком для развития пространственного воображения у студентов. Кубик Рубика - это куб, как бы разрезанный на 27 одинаковых кубичков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубичков, примыкающих к одной грани куба, вокруг ее центра; при этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение.

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

Записывать последовательность ходов (операции) будем, пользуясь обозначениями, рисунок 5; например, это ФП'- это последовательность из двух воротов: фасадной (передней) грани на 90 по часовой стрелке и правой - на 90 против часовой. Весь процесс сборки основан на операции F= ПВФВ'Ф'П'Ф и обратно к ней операции F'=Ф'ПФВФ'В'П'.

1-й этап. Сборка реберных кубичков.

1. Для расстановки реберных кубичков применяется операция F(или F'), меняющая местами ровно два из них. (Действие операции на реберных кубичках показано на рисунке).

2. Для разворачивания применяется операция; в результате на своих местах поворачиваются два кубичка (а и b на рисунке 6)

рис.5 рис.6

2-й этап. Сборка угловых кубичков.

1. Для расстановки угловых кубичков применяется операция FВ'F'В, действие которой показано стрелками на рисунке 7, и обратная операция В'FВF',переставляющая те же кубички в обратном порядке.

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

рис.7 рис.8

Указанные операции можно использовать и в рамках других общих схем. Например, нетрудно правильно собрать все реберные кубички, кроме четырех, лежащих в одной грани, после чего можно перейти к выполнению первого этапа алгоритма. Общее число ходов при этом заметно сокращается, но остается все еще большим. Дальнейшее сокращение можно получить, в частности, за счет расширения набора стандартных операций. Имеются и принципиально другие схемы сборки. Лучшие из них позволяют обойтись примерно 50 ходами - поворотами, но теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода.

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

1.2.2.ПЛОСКИЕ ГРАФЫ. ЭЙЛЕРОВЫ ГРАФЫ. ДЕРЕВЬЯ.

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

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

рис.9

А всегда ли можно так, изобразить любой граф на плоскости, чтобы его ребра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как ее описывает Льюис Кэрролл. В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант, изображенный на рисунке 10, по этой причине их не устраивал. На рисунке 11 изображена очередная попытка проложить тропинки, на которых осталась непроведенной только одна тропинка. Графы, которые можно изобразить на плоскости без пересечения их ребер, принято называть плоскими. Если немного подумать, то можно доказать, что граф «домики-колодцы» с шестью вершинами не является плоским. Не плоский и граф с пятью вершинами, каждые из которых соединены ребром (рисунок 12).

рис.10 рис.11

Эти два графа, как, оказалось, играют очень важную роль в определении того - является ли данный граф плоским. Оказывается, что если граф не плоский, то в нем «сидит» или граф «домики- колодцы» или «полный пятивершинник» (рис. 12) Эту теорему независимо друг от друга доказали польский математик К. Куратовский и наш академик Л.С.Понтрягин.

рис.12

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

В - Р - Г =1

Если же к странам отнести и внешность графа - бесконечную страну, то формула будет иметь вид:

В - Р + Г = 2

Эта формула будет верна для любого выпуклого многогранника, где В, Р, и Г - количество его вершин ребер и граней. Например, у куба В =8, Р = 12, Г = 6 и мы имеем:

8 - 12 + 6 = 2

рис.13

Вершины и ребра многогранников, очевидно, образуют графы, причем для выпуклых многогранников (и не только для них) эти графы будут плоскими. На рисунке 13 изображены графы, соответствующие правильным многогранникам. На них вы можете проверить справедливость формулы. Она была открыта Леонардом Эйлером, но выяснилось, что для многогранников она была известна еще Рене Декарту.

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

Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Связный граф имеет одну компоненту связности.

Деревья.

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.10)

рис.9а;б

Свойство 1.

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

Свойство 2.

Всякое ребро в дереве является мостом.
Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

рис.10 (кружком обведены висячие вершины)

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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

*Дерево - это граф, в котором две любые вершины соединены ровно одним простым путём.

ЛЕММА (о висячей вершине)

В каждом дереве есть висячая вершина.

Доказательство:

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

ТЕОРЕМА.

В дереве число вершин на одну больше числа ребер.

1.2.3. ОРИЕНТИРОВАННЫЕ ГРАФЫ

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

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

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

Графы, в которых все ребра имеют направления, называются орграфами. На них удобно рассматривать различные транспортные задачи. Например, между городами А и В имеется сеть дорог, и на некоторых из них движение одностороннее (рис.25). Кроме того, задана пропускная способность каждой дороги, скажем в тысячах машин в час. Попробуем ответить на вопрос: какой максимальный поток машин возможен из А в В и из В в А?

Как видим, хотя из А может выезжать в час 7 тыс. машин, но въехать в В в час смогут лишь 4 тыс. из них. Несложно проверить, что 4 тыс. машин в час остальные дороги в состоянии пропустить.

С другой стороны, из В в А могут выехать 3 тыс. машин в час, однако въехать в А за час смогут лишь 2 тыс. Поток в 2 тыс. машин из В в А остальные дороги, как нетрудно убедиться, также смогут пропустить.

рис.25

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

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

рис.26

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

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

1.3 КЛАССИЧЕСКИЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ

1.3.1. ГРАФЫ ИГР

На шахматной мини-доске (рис.14) размером 3х3 расположены четыре коня - два белых и два черных. Задача - переставить фигуры так, чтобы одинаковые кони оказались в противоположных углах доски (рис.15). Перемешать их можно только ходом шахматного коня и нельзя ставить фигуру на уже занятое поле.

рис.14 рис.15 рис.16

Все попытки совершить такую перестановку терпят неудачу. Почему?

Давайте начертим граф возможных ходов коней на доске (рис.16). Затем построим изоморфный ему граф без самопересечений в двух вариантах: на одном отметим первоначальное положение коней, а на другом - требуемое (рис.17,а, б). Вот теперь понятно, почему задача не решается. Движение коней по графу означает переходы в соседние вершины, и перейти из первой позиции во вторую невозможно без «перескока» через коня другого цвета.

Этот же граф помогает решить и еще одну задачу. В ней требуется из положение, показанного на рис.14 , за наименьшее количество ходов перевести коней в положение, изображенное на рис.18, т.е. поменять местами черных и белых. На рис.17,а ясно видно, что фигуры должны двигаться по этому графу в одном и том же направлении, и каждому коню придется сделать ровно 4 хода, т.е. всего понадобится 16 ходов.

рис.17 рис.18

Вообще, граф игры - это граф, вершины которого - ситуации, возникающие в процессе игры, а ребра связывают вершину с теми вершинами-ситуациями, которые могут сложиться после очередного хода. Так, в шахматах из начальной позиции первым ходом можно получить 20 позиций: каждая пешка может пойти на одну или две клетки вперед, и каждый конь может пойти на одно из двух полей. После хода черных число возможных позиций становится равным 20х20=400 и в дальнейшем быстро увеличивается. Это обстоятельство и стало основной трудностью при создании шахматных программ.

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

Нарисуем граф всевозможных продолжений игры (рис.19). Видно, что после первого хода на столе остается 3 или 4 спички. Если тот, кто начинает, оставит на столе 3 спички, то он выиграет: ведь его партнер вынужден будет оставить 1 или 2 спички, которые начинавший и заберет на следующем ходу. Если же начинающий игру оставит 4 спички, то он проиграет, так как партнер, взяв 1 спичку, оставит ему 3, что, как мы уже видели, ведет к проигрышу игрока, делающего очередной ход. Конечно же, второй игрок может оставить 2 спички и тут же проиграть, но это маловероятно. Можно сделать вывод: начинающий проигрывает, если исходное число спичек делится на 3, и выиграет в остальных случаях, оставляя партнеру всякий раз количество спичек, которое делится на три.

рис.19

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

1.3.2. ЗАДАЧА КОММИВОЯЖЕРА И ОБРАТНАЯ ЗАДАЧА

Одна из классических задач теории графов называется «задачей коммивояжера» или

« задачей о бродячем торговце».

Представим себе торгового агента, который должен побывать в нескольких городах и вернуться обратно. Известно, какие дороги соединяют эти города, и каковы расстояния между ними по этим дорогам (рисунок 20). Нужно выбрать самый короткий маршрут. Это уже не «игрушечная» задача. Например, водитель почтового автомобиля, вынимающий письма из ящиков, очень хотел бы знать кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам. А решить эту задачу очень не просто, особенно когда число вершин графа велико.

рис.20

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

Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах теории графов).Продемонстрируем его на примере дороги, соединяющий пять городов: А, В, С, Д и Е. Стоимость прокладки пути между каждой парой городов указана в таблице, а расположение городов - а карте (рисунок 23).

рис.21

А

В

С

Д

Е

А

1,5

1

2

2,5

В

1,5

1,2

3

0,8

С

1

1,2

1,1

0,9

Д

2

3

1,1

2,7

Е

2,5

0,8

0,9

2,7

Сначала строим ту дорогу, которая имеет наименьшую стоимость. В нашем случае это маршрут В-Е. Теперь найдем самую дешевую линию, соединяющую город В или Е с каким-то из остальных городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично - ищем самый дешевый из путей, соединяющий один из городов В, С, Е с одним из оставшихся - А или Д. Это дорога между С и А. Осталось подключить к железнодорожной сети город Д. Дешевле всего соединить его с С. Получим, сеть, изображенную на рисунке 22.

А В

С Е

Д рис.22

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

1.3.3. ЗАДАЧА О ЧЕТЫРЕХ КРАСКАХ. ТЕОРИЯ РАМСЕЯ.

Внимательно рассматривая географическую карту, можно заметить, что кроме графов, изображающих железные или шоссейные дороги, есть еще один - граф, состоящий из границ между странами (областями, районами) (рис.23).

рис.23 рис.24

Эта задача ведет свою историю с 1852 г. Однажды английский студент Френсис Гутри раскрашивал карту Великобритании. Каждое графство он выделял цветом. К сожалению, выбор красок у него был невелик, и приходилось их использовать повторно. Гутри старался, чтобы два графства, имеющие общий участок границы, были окрашены в разные цвета. Это занятие заставило его задуматься о том, какого наименьшего числа красок достаточно для раскрашивания любой карты. Гутри считал, что четырех красок всегда хватит, но доказать это не мог. Проблема некоторое время активно обсуждалась среди лондонских студентов, а потом о ней забыли. В 1879г. известный английский математик Артур Кэли опубликовал эту задачу в первом томе «Трудов Королевского географического общества», и она получила широкую известность.

Со временем интерес к «проблеме четырех красок» рос, но она не поддавалась усилиям даже выдающихся математиков. В 1890 английский математик Перси Хивуд доказал, что пяти красок хватит для раскрашивания любой карты. В 1968г. было доказано, что карту, на которой обозначено меньше 40 стран, всегда можно раскрасить с помощью четырех красок.

Наконец, в 1976г. американские математики Кеннет Аппель и Вольфгант Хакен решили эту задачу с помощью компьютера. Они разбили все карты на 2000 типов. Компьютер по составленной ими программе исследовал, может ли в рассматриваемом типе карт найтись такая, для которой недостаточно четырех красок. С тремя типами карт компьютер не справился, и над ними пришлось потрудиться самим математикам. Получив ответ «нет» для всех 2000 типов, исследователи объявили. Что проблема четырех красок решена. Почтовое отделение при университете, в котором работали Аппель и Хакен, в тот день гасило марки на письмах штемпелем со словами: «Четырех красок достаточно».

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

ТЕОРЕМА РАМСЕЯ

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

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

2.1 ПОДСЧЕТ ЧИСЛА РЕБЕР

Задача 1.

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение:

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

Ответ: нельзя.

Задача 2.

В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего дорог в государстве?

Решение

50х 8/2=50х4=200.

Ответ: 200 дорог.

Задача 3

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

Решение

Для решения этой задачи используется теорема, которая гласит:

Число нечетных вершин любого графа четно. (1)

Следовательно, нет, такого быть не может. Не существует графа с 15 нечетными (т.к. степень 7 - нечетная) вершинами.

Ответ: нет.

Задача 4

В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы четно.

Решение

В графе с 953 вершинами должно быть четное число нечетных вершин (по теореме 1), поэтому у нечетного числа из них число знакомых - четно.

Ответ: что и требовалось доказать.

Задача 5

У царя Гвидона было 5 детей. Из всех его потомков (детей, внуков, правнуков и т.д.) 57 имели ровно трех сыновей, а остальные умерли бездетными. Сколько потомков было у царя Гвидона?

Решение

57х3+5=176. число потомков равно количеству ребер в графе - родословном дереве царя Гвидона.

Ответ: 176 потомков.

Задача 6

Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и черных пятиугольников. Каждый черный лоскут граничит только с белыми, а каждый белый - с тремя черными и тремя белыми. Сколько лоскутов белого цвета?

Решение

Пусть на мяче х белых лоскутов, тогда (32-х) - черных. Следовательно, границ белых с черными - 5(32-х)=3х, отсюда х=20.

Ответ: 20 белых лоскутов.

2.2 ЭЙЛЕРОВЫ ГРАФЫ

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

Несвязный граф состоит из нескольких «кусков». Эти

Задача 1

В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с семью другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города), т.е. граф дорог связен.

Решение

Рассмотрим два города и пусть они не соединены путем. Так как каждый соединен не менее, чем с 7 другими, при этом города различны (если 2 совпадают, то есть путь, соединяющий исходные города), то мы указали не менее 16 городов.

Ответ: что и требовалось доказать.

Задача 2

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

Решение

Допустим, что это возможно. Пусть на шоссе n городов, тогда всего 2n-1 дорог. Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n. Противоречие. Следовательно: не смогут.

Ответ: не смогут.

Задача 3.

Как соединить 50 городов наименьшим числом авиалиний так, чтобы из любого города можно было попасть в любой другой, сделав не более двух пересадок?

Решение

Ровно один город должен быть пересадочным, а так как в связном графе с 50 вершинами ребер не меньше 49, то 49 - наименьшее число авиалиний.

Задача 4

В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе - каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис - с Андреем, Галиной; Виктор - с Галиной, Дмитрием, Еленой; Галина - с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение:

Построим граф (рис.1).

Сыграно 7 игр.

На рис. 2 граф имеет 8 ребер, следовательно, осталось провести 8 игр.

Задача 5

Можно ли составить решетку на рис. 1 из пяти ломаных линий длины 8?

Рис.1

Решение

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

Ответ: нельзя.

2.3. ДЕРЕВЬЯ

Задача 1

В графе все вершины имеют степень 3. докажите, что в нем есть цикл.

Решение

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

Задача 2

В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

Решение

30х 29/2 - 29=406

Ответ: 406 дорог.

Задача 3

Волейбольная сетка - прямоугольник 50 х 600 клеток. Какое наибольшее число веревочек можно перерезать, чтобы сетка не распалась?

Решение

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами - веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Заметим, что пока в графе есть цикл, возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Изначально в графе было 601 х 50 + 600 х 51 = 60650 ребер и 51 х 601 = 30651 вершин, т.е. дерево будет иметь 30650 ребер. Таким образом, разрезать можно 60650 - 30650 = 30000 веревочек.

Ответ: 30000 веревочек.

Задача 4

В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.

- Ляпкиным-Тяпкиным буду я! - решительно заявил Дима. - С раннего детства я мечтал воплотить этот образ на сцене.

- Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- …А мне - Осипа, - не уступил ему в великодушии Дима.

- Хочу быть Земляникой или Городничим, - сказал Вова.

- Нет, Городничим буду я, - хором закричали Алик и Боря. - Или Хлестаковым, - добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение:

Построим граф для ситуации, описанной в задаче (рис.1).

Граф с 10 вершинами и 10 ребрами. Надо выбрать из десяти пять ребер, не имеющих общих вершин: Дима - Осип, Вова - Земляника, Гена - Ляпкин - Тяпкин. Остается два случая: Алик - Хлестаков, Боря - Городничий или Алик - Городничий, Боря - Хлестаков. Как показывает граф, других решений нет.

Задача 5

В стране Древляндии n городов и некоторые из них соединены дорогами. При этом любые два города соединяют ровно один путь. Сколько в этой стране дорог?

Решение

Из условия граф Древляндии - дерево. У него есть висячая вершина. Удалим ее и выходящее из нее ребро. Оставшийся граф также дерево. У него есть висячая вершина, которую также удалим и т.д. Проделав эту операцию n-1 раз, получим граф, состоящий из одной вершины. Так как удалялось по одному ребру, вначале их было n-1. Следовательно, в этой стране n-1 дорог.

Ответ: n-1.

2.4. ПЛОСКИЕ ГРАФЫ

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

Задача 1

В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

Ответ: 4 острова.

Задача 2

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

Решение

Пусть отмеченные точки и вершины квадрата - вершины, и соединяющие их отрезки и стороны квадрата - ребра плоского графа. Для каждого куска, на которые граф разбивает плоскость, посчитаем число ограничивающих ребер, и все полученные числа сложим. Поскольку каждое ребро разделяет два куска, то в итоге получим удвоенное число ребер. Так как все куски, кроме внешнего - треугольники, а внешний кусок ограничен 4 ребрами, то получаем 3 (F-1)+4=2F, т.е. Е=3(F-1)/2+2. (где F - число граней, а Е - число ребер) Заметим, что число вершин нашего графа равно 24 и подставим количества вершин ребер в формулу Эйлера 24-(3(F-1)/2+2) +F=2. отсюда F=43. итак, число треугольников - 42.

Ответ: 42 треугольника.

Задача 3

Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

Решение

Нельзя. Если бы такой граф был плоским, то так как каждый кусок должен быть ограничен, по меньшей мере, 4 ребрами, получим Е(где Е - число ребер, а F - число граней). В задаче Е=9, поэтому F. А из формулы Эйлера имеем F=2-6+9=5.

Ответ: нельзя.

Задача 4

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

Решение

Расположим 6 точек (ЭВМ) в вершинах правильного шестиугольника. Его стороны закрасим через одну цветами 1 и 2, а диагонали - цветами 3, 4, 5 (одним цветом закрасим две параллельные малые диагонали и перпендикулярную к ним большую).

Ответ: можно.

Задача 5

Каждые две из 15 ЭВМ соединены проводом. Можно ли все эти провода раскрасить в один из 14 цветов так, чтобы из каждой ЭВМ выходило 14 проводов разного цвета?

Решение

Нельзя, так как число проводов каждого цвета должно быть равным 15/2.

Ответ: нельзя.

2.5 ОРИЕНТИРОВАННЫЕ ГРАФЫ

Граф, на ребрах которого расставлены стрелки, называется ориентированным.

Задача 1

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

Решение

Количество (общее) «втекающих» рек должно быть равно общему количеству «вытекающих» рек

Ответ: что и требовалось доказать.

Задача 2

В стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

Решение

Пусть в столицу входит, а дорог. Тогда общее число «входящих» дорог равно 21х+а, а общее количество «выходящих» дорог не больше 20х100+(100-а). Поэтому 21х100+а 20х100+(100-а), то есть 2а0. таким образом, а=0.

Ответ: количество дорог равно 0.

Задача 3

Город Зурбаган ограничен кольцевой дорогой. Все улицы начинаются и кончаются на этой дороге и никакие две улицы не имеют двух различных пересечений. Части, на которые улицы разбивают город, называются микрорайонами. В городе ввели одностороннее движение по всем улицам и кольцевой дороге. Докажите, что хотя бы один микрорайон можно объехать вокруг, не нарушив правил движения.

Решение

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

Задача 4

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

Решение

Назовем «соседями» города N те города, из которых можно попасть в N , проезжая не более, чем через один промежуточный город. Докажем методом математической индукции. Что найдется город N , к которому остальные близки. Для стран, в которых всего 2 города, утверждение очевидно. Пусть это доказано для стран с n городами. Нанесем на схему дороги, соединяющие какие-нибудь n городов. Тогда по предположению индукции найдется такой город А, что остальные n-1 городов близки к А, т.е. каждый из них является соседом А или соседом одного из соседей А. Если (n + 1)-й город В тоже близок к А, то все города страны близки к А. Если же это не так, то, из условия задачи, город А и все его соседи являются соседями В. Каждый из остальных городов является соседом одного из соседей А и, значит, близок к В т.е. все города страны близки к В.

Задача 5

В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д - третьего. Пронумеруйте каждую корзину так, чтобы в корзине № 1 были яблоки первого сорта (хотя бы одно); в корзине № 2 - второго и т.д.

Решение:

Составим граф

1 сорт

2 сорт

3 сорт

4 сорт

5 сорт

Ответ: №1 - Г; №2 - А или №2 - Б; №3 - Д; №4 - В; №5 - Б или №5 - А.

Задача 6

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В, С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Решение

Пусть А и В набрали одинаковое число очков, причем В выиграла у А. Тогда если для любой команды С, у которой выиграла А, выиграла и В, то у В должно быть очков больше, чем у А. Значит, есть команда С такая, что А выиграла у С, а С выиграла у В.

2.6. ЗНАКОМСТВА, ТЕОРИЯ РАМСЕЯ

Задача 1

В купе поезда ехали четыре человека. Среди них не было троих, прежде знакомых друг с другом, но один был знаком с тремя остальными. Докажите, что эти три последних пассажира не были знакомы друг с другом.

Решение

Если среди этих трех двое будут знакомы, то есть три знакомых пассажира.

Задача 2

В Цветочном городе каждый коротышка знаком с 6 малышками, а каждая малышка - с 6 коротышками. Докажите, что в этом городе число малышек равно числу коротышек.

Решение

Если знакомство вида «коротышка - малышка» - это ребро графа, n - число мартышек, m- число малышек, то всех знакомств (ребер) коротышек 6n, а малышек - 6m. Но 6n = 6m.

Задача 3

Докажите, что среди 102 учеников одной школы, знаком не менее чем с 68 другими, их найдутся четверо, имеющие одинаковое число знакомых.

Решение

Предположим противное. Тогда для каждого числа от 68 до 101 есть ровно 3 человека, имеющие такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Задача 4

На конгресс приехало 1000 делегатов из разных стран. Любые трое могут разговаривать между собой без помощи остальных. Доказать, что всех делегатов можно расселить в 500 комнатах так, чтобы в каждой комнате было два делегата, которые могут поговорить между собой.

Решение

Предположим противное. Тогда для каждого числа от 68 до 101 есть ровно три человека, имеющие такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Задача 5

В математическом кружке участвуют 100 школьников. Известно, что среди любых четырех участников кружка найдется, по меньшей мере, один, знакомый с остальными тремя. Докажите, что найдется участник, знакомый со всеми 99 остальными участниками. Каково минимальное число школьников, знакомых со всеми остальными 99 участниками?

Решение

Докажем, что есть, по крайней мере, 97 школьников, каждый из которых знаком с 90 остальными участниками кружка. Пусть не все 100 школьников знакомы между собой. Тогда найдутся двое, А и В, которые не знают друг друга. Рассмотрим любую четверку школьников, в которую входят А и В, скажем, А, В, Х, У. По условию, один из четырех знаком с остальными тремя. Это может быть Х или У, так как А В незнакомы. Пусть, например, Х знаком с А, В, и У. Применив то же рассуждение к любой группе А, В, Х, Z, в которую входят А, В, и Х, видим, что либо Х знаком с А, В и Z, либо Z знаком с А, В и Х.. Так или иначе, Х и Z знакомы. Следовательно, Х знаком со всеми участниками кружка. Нетрудно видеть, что кроме А и В найдется самое большее один школьник, знакомый не со всеми участниками кружка.

Задача 6

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

Решение

Допустим, что никакие трое из математиков не говорят на одном и том же языке. Рассмотрим произвольного математика А. Он говорит не более чем на трех языках, причем на каждом из эти языков говорит еще не более чем один из математиков ( иначе мы получили бы противоречие с допущением). Поэтому найдутся 5 математиков, с которыми А не говорит на одном языке. Пусть один из этих пяти - математик В. По той же причине, что и А, математик В может говорить на одном языке не более чем с тремя математиками. Поэтому среди остальных четырех математиков. Не говорящих на одном языке с А, найдется математик С. Не говорящий на одном языке с В. Таким образом, в тройке А. В, С никакие двое говорят на одном языке, что противоречит условию задачи.

Задача 1

Каждое из ребер полного графа с 6 вершинами покрашено в один из двух цветов. Докажите, что есть три вершины, все ребра между которыми - одного цвета.

Решение

Рассмотрим какую-нибудь точку и выходящие из нее пять отрезков. Очевидно, хотя бы три из них одного цвета. Вторые концы этих трех отрезков образуют треугольник. Если его стороны одного цвета, то все доказано; если же разных цветов, то одна из его сторон окрашена в тот же цвет, что и рассматриваемые три отрезка, и , значит, образует с двумя из этих отрезков «одноцветный» треугольник

Ш. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ТРАНСПОРТНОЙ СФЕРЕ

3.2Маршруты школьного автобуса

Вариант 1:

Вариант 2:

Вариант 3:

Описание

У каждого графа все вершины четные т.е. из каждой вершины выходит четное количество ребер (степень вершин - 2). Все эти графы являются направленными, также их можно назвать деревьями. Дерево-это граф, в котором любые две вершины соединены ровно одним простым путем. Они являются плоскими или планарными, так как их можно нарисовать так, чтобы их ребра не пересекались нигде, кроме вершин.

Наиболее оптимальным маршрутом является граф №2, потому что этот маршрут охватывает наиболее густо заселенные районы, окружающие школу№3 г. Джанкоя.

Заключение

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

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

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

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

Приобретение и эксплуатация автобуса решит некоторые проблемы:

1. Уменьшит детский травматизм.

2. Даст возможность выезжать учащимся нашей гимназии:

а). В туристические поездки

b). На соревнования

с). На олимпиады и т.д.

Список литературы

1. Графы и их применение. Л. Ю. Березина. - М.: Просвещение, 1979г.

2. Квант №6, 1994г.

3. Я познаю мир. Математика. - М.: АСТ, 1998г.

4. Внеклассная работа. Обучение элементам теории графов в 4-6 классах. О.И.Мельников, В.В.Куприянович. - М.: Просвещение, 2000г.

5. Сборник олимпиадных задач. А.Горбачев. - М.: МЦНМО, 2005г.

6. Теория графов. Белов. - М.: Наука, 1968г

7. Интернет ресурсы

34