Леонард Эйлер и теория графов

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

Примеры графов в окружающем мире.

Хорошо знакомый всем москвичам образец графа - схема московского метро.

Вершины - конечные станции и станции пересадок, ребра - пути, соединяющие эти станции.

Другой пример графа - генеалогическое дерево. В качестве примера продемонстрируем генеалогическое дерево великого русского поэта А. С. Пушкина.

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

Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.

Обитатели неба. Созвездия.

<<Путешествуя>> по небесным просторам среди бесчисленных звёзд и туманностей, немудрено и заблудиться, если нет под рукой надёжной карты. Чтобы составить её, нужно точно знать положение тысяч звёзд на небе.

В давние времена созвездиями называли характерные группы ярких звёзд, которым давали имена, заимствованные из мифологии (Андромеда, Геркулес) или из быта (Весы, Телега).

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

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

Наше наблюдение: чтобы выделить отдельные созвездия из общего <<звездного хаоса>>, первые астрономы условно соединили наиболее яркие звёзды линиями (построили графы). Всё множество видимых звёзд разделилось на отдельные группы - созвездия. Если граф ассоциировался с каким-либо знакомым объектом, то созвездию давалось соответствующее название.

Когда кругом густая тьма ,

А бездна звездами мерцает,

Струится с неба красота

И счастьем душу наполняет.

Какой порядок иль закон

Творит вселенское величье?

Но нам художник незнаком,

Скрывает тьма его обличье.

Пример из медицины

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

Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы.

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

Из графа видно, что кровь 1-й группы можно переливать любому человеку, а человек с 1-й группой крови воспринимает кровь только своей группы.

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

Леонард Эйлер и теория графов

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

Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.

Задача об эйлеровом пути

Задача: Найти путь по рёбрам графа, проходящий по каждому ребру ровно один раз.

Такой путь существует лишь в том случае, если граф - связный

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

Вершина с нечетным числом ребер

Вершина с четным числом ребер

Графы изоморфные и плоские

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

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

Мы провели такой опыт с многогранниками, которые изготовили самостоятельно.

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

Два графа, изображенные на рисунке 1 , в этом смысле одинаковы: у них одинаковое число вершин, и если две вершины одного графа соединены ребром, то вершины второго графа, имеющие те же номера, так же соединены ребром.

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

А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно, называются плоскими.

Рассмотрим два графа, которые <<не укладываются>> на плоскость без пересечения рёбер. Первый из них - граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным .

Второй граф, с шестью вершинами и девятью рёбрами , носит название <<домики - колодцы>>. Оно произошло от старинной задачи - головоломки.

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

Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (В), количеством ребер (Р) и количеством частей (Г), на которые граф разделяет плоскость:

В - Р+Г=2.

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

Проверим эту зависимость для сделанных нами многогранников: икосаэдра и додекаэдра.

Для икосаэдра: В = 12; Р = 25; Г = 15; 12 - 25 + 15 = 2.

Для додекаэдра: В = 20; Р = 30; Г = 12; 20 - 30 + 12 = 2.

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

Решение. Рассмотрим граф, в котором вершины соответствуют островам, а рёбра - каналам. Понятно, что полученный граф будет плоским и связным, значит, для него выполняется формула Эйлера: В - Р + Г = 2. Для нашего графа В = 7, Р = 10. Подставляя в формулу, получаем 7 - 10 + Г = 2. Отсюда следует, что Г = 5, то есть, рёбра графа разбивают плоскость на 5 частей. Островам соответствуют все грани, кроме внешней (она бесконечно большая во все стороны и острову соответствовать не может), значит, их 4.

Задачи, придуманные участниками проекта.

Задача о районе Митино.

Одна из классических задач теории графов называется <<задачей коммивояжера>> или <<задачей о бродячем торговце>>.

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

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

Решить эту задачу очень непросто, особенно когда число вершин графа велико.

В нашей работе мы решили мы решили привести пример задачи о районе Митино.

На карте нашего района Митино обозначены пункты, которые чаще всего посещаются учениками нашей школы.

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

Для решения этой задачи мы используем так называемый <<жадный алгоритм>>. Он заключается в том, что на каждом шаге будем выбирать самый короткий маршрут. Это будет означать , что выбран самый <<дешевый>> участок пути для озеленения.

Задача туриста.

(Автор: Бгатцев Алексей)

Составь туристический маршрут , посетив города: Варшава, Берлин, Париж, Лондон, начиная свой путь из Москвы.

Выбери самый короткий путь, если расстояние : от Москвы до Варшавы - 1100 км, от Москвы до Берлина - 1600 км, от Москвы до Парижа - 2500 км, от Москвы до Лондона - 2500км, от Варшавы до Берлина - 500км, от Варшавы до Парижа - 1300км, от Варшавы до Лондона - 1500км , от Берлина до Парижа - 900км, от Берлина до Лондона - 900км, от Парижа до Лондона - 300км.

Сколько вариантов маршрутов может быть?

Маршрут

Результат

М-В-Б-П-Л-М

1100+500+900+300+2500

М-В-Б-Л-П-М

1100+500+900+300+2500

М-В-П-Б-Л-М

1100+1300+900+900+2500

М-В-П-Л-Б-М

1100+1300+300+900+1600

М-В-Л-Б-П-М

1100+1500+900+900+2500

М-В-Л-П-Б-М

1100+1500+300+900+1600

М-Б-В-П-Л-М

1600+500+1300+300+2500

М-Б-В-Л-П-М

1600+500+1500+300+2500

М-Б-П-В-Л-М

1600+900+1300+1500+2500

М-Б-П-Л-В-М

1600+900+300+1500+1100

М-Б-Л-В-П-М

1600+900+1500+1300+2500

М-Б-Л-П-В-М

1600+900+300+1300+1100

М-П-В-Б-Л-М

2500+1300+500+900+2500

М-П-В-Л-Б-М

2500+1300+1500+900+1600

М-П-Б-В-Л-М

2500+900+500+1500+2500

М-П-Б-Л-В-М

2500+900+900+1500+1100

М-П-Л-В-Б-М

2500+300+1500+500+1600

М-П-Л-Б-В-М

2500+300+900+500+1100

М-Л-В-Б-П-М

2500+1500+500+900+2500

М-Л-В-П-Б-М

2500+1500+1300+900+1600

М-Л-Б-В-П-М

2500+900+500+1300+2500

М-Л-Б-П-В-М

2500+900+900+1300+1100

М-Л-П-В-Б-М

2500+300+1300+500+1600

М-Л-П-Б-В-М

2500+300+900+500+1100

Ответ: самый короткий путь -

Москва-Берлин-Варшава-Париж-Лондон-Москва

Его длина 4200 км и 24 варианта маршрутов.

Задача о рейсах самолетов

(Автор: Гончаревич Настя)

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

Можно ли удовлетворить пожеланиям летчиков? Если да, то перечислите возможные варианты вылетов.

Ответ: возможно 2 варианта.

1) первый рейс - в Варшаву, второй - в Лондон, третий - в Париж, четвертый - в Берлин.

2) первый рейс - в Берлин, второй - в Варшаву, третий - в Лондон, четвертый - в Париж.

Задача <<Расписание уроков>> (Автор: Азибекян Арен)

Для учащихся 7 "б" класса нужно составить расписание уроков на понедельник. Должны быть такие предметы: 2 урока математики, по 1 уроку русского языка, истории, биологии и географии. Учитель математики высказала пожелание, чтобы ее уроки были 1 и 3. Учителя русского языка и истории согласны заниматься с учащимися на 2 или 4 уроках. Учителя биологии и географии - на 5 или 6.

Сколько вариантов расписания можно составить?

Можно составить 16 вариантов расписания. Вот некоторые из них:

1) Математика

2) Русский язык

3) Математика

4) История

5) География

6) Биология

1) Математика

2) История

3) Математика

4) Русский язык

5) Биология

6) География

1) Математика

2) Русский язык

3) Математика

4) История

5) Биология

6) География

Задача <<Школьное меню>> (Автор: Демидова Ксения )

В школьной столовой на первое можно заказать борщ, щи, рыбный или гороховый суп , на второе - <<ёжики>>, рыбу или котлету , а на третье - сок, чай или компот.

Сколько вариантов обеда можно получить из указанных блюд ?

Всего 36 вариантов меню.

1. Борщ

2. Рыба

1. Рыбный Суп

2. Ёжики

3. Компот

1. Борщ

2. Ёжики

3. Компот

2. Котлета

Задача 1 из ЕГЭ по информатике.

Два игрока играют в следующую игру.

Перед ними лежат 2 кучки камней, в 1-й из которых 4, а во 2-й - 3 камня.

У каждого игрока неограниченно много камней.

Игроки ходят по очереди.

Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то кучке, или добавляет 3 камня в какую-то кучку.

Выигрывает игрок, после хода которого в одной из кучек становится не менее 24 камней.

1) Кто выигрывает при безошибочной игре: игрок, делающий 1-й ход, или игрок, делающий 2-й ход?

2) Каким Должен быть 1-й ход выигрывающего игрока?

Задача 2 из ЕГЭ по информатике.

Цепочка из трех бусин формируется по следующему правилу.

На 3-м месте в цепочке стоит одна из бусин А, В, Г. На 2-м месте - одна из бусин А, Б, В. На 1-м месте - одна из бусин Б, В, Г, не стоящая в цепочке на втором или третьем месте.

Сколько существует различных цепочек, соответствующих этому правилу.

Задача 3 из ЕГЭ по математике.

<<Транспортная задача>> Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет ровна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время.

Сколько минут он планирует пробыть в пути?

Граф, соответствующий условию задачи.

Решение

1) (15 + 25) : 16 = 2,5 (ч) - время в пути ABE

2) (19 + 17) : 18 = 2 (ч) - время в пути ADE

3) (11 + 34) : 20 = 2,25 (ч) - время в пути AСE

4) 2 < 2,25 < 2,5

5) 2 (ч) = 120 (мин)

Ответ : 120 минут он планирует пробыть в пути

Олимпиада <<Осенняя разминка>> для 7-х классов

2009-2010 учебный год

Три профессора (Иванов, Петров и Сидоров) преподают различные предметы (химию, биологию, историю) в университетах Москвы, Минска и Киева.

Известно что:

* Иванов никогда не был в Киеве, а Петров - в Минске;

* Киевлянин старше профессора истории;

* Петров играет в шахматы лучше, чем биолог;

* Минчанин преподает химию.

Вопрос: где и что преподает Сидоров?

Биология

История

История

Биология

Биология

История

Сидоров

1. Т. к. Иванов никогда не был в Киеве, а Петров в Минске Иванов не из Киева, а Петров не из Минска.

2. Петров играет в шахматы лучше, чем биолог Петров не биолог.

3. Минчанин преподает химию. Петров не преподает химию. Петров Историк.

Иванов не историк и Сидоров не историк.

4. Киевлянин старше профессора истории Петров не может быть киевлянином. Петров - москвич. Киевлянином может быть только Сидоров.

Сидоров не может быть москвичом или минчанином

Иванов - минчанин.

Заключение

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

Описание результатов работы

Мы научились решать задачи методом, который не изучается в нашей школьной программе. Эти задачи имеют повышенный уровень сложности. Большая часть из них относится к логическим задачам. Нам также удалось составить свои собственные задачи (их решения приводятся в проекте). Некоторые научные утверждения мы проверили в ходе экспериментов и убедились в их справедливости. Это было очень увлекательно!

Самоанализ

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

Практическая значимость работы.

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