Применение теории графов Работу выполнила ученица 8 класса Гончарова Дарья

«Чтоб мудро жизнь прожить Знать надобно немало…» О.Хайям Цель: Познакомиться с одним из разделов дискретной математики Познакомиться с одним из разделов дискретной математики Задачи: Создать мотивационную базу для изучения самого молодого раздела современной математики; Создать мотивационную базу для изучения самого молодого раздела современной математики; познакомиться с интенсивно развивающимся разделом дискретной математики; познакомиться с интенсивно развивающимся разделом дискретной математики; помочь учащимся отойти от математических штампов; помочь учащимся отойти от математических штампов; показать красоту этого метода. показать красоту этого метода.

История вопроса Есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя, она делится на два рукава и огибает остров. В 18 веке в городе было семь мостов, расположенных так, как показано на рисунке сверху. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка? Многие горожане заинтересовались этой задачей. Однако, придумать решение никто не смог. Потом этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач.

Основные понятия При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ. Точки А, В, С, D называют ВЕРШИНАМИ графа, а линии, которые соединяют вершины, - РЕБРАМИ графа. Точки А, В, С, D называют ВЕРШИНАМИ графа, а линии, которые соединяют вершины, - РЕБРАМИ графа. На нашем рисунке из вершин В, С и D выходит по три ребра, а из вершины А - пять ребер. Вершины, из которых выходит нечетное число ребер, называются НЕЧЕТНЫМИ вершинами, а вершины, из которых выходит четное число ребер, называются ЧЕТНЫМИ. На нашем рисунке из вершин В, С и D выходит по три ребра, а из вершины А - пять ребер. Вершины, из которых выходит нечетное число ребер, называются НЕЧЕТНЫМИ вершинами, а вершины, из которых выходит четное число ребер, называются ЧЕТНЫМИ.

Свойства графов Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие три СВОЙСТВА графа: 1) Если все вершины графа четные, то можно одним росчерком (то есть рисуя непрерывно и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. 1) Если все вершины графа четные, то можно одним росчерком (то есть рисуя непрерывно и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. 2) Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. 2) Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. 3) Граф с более, чем двумя нечетными вершинами, невозможно начертить одним росчерком. 3) Граф с более, чем двумя нечетными вершинами, невозможно начертить одним росчерком. В задаче о семи Кенигсбергских мостах все четыре вершины соответствующего графа - нечетные, т.е. нельзя пройти по всем мостам ровно один раз и закончить путь там, где он был начат.

Свойства графов Кроме трех свойств графа, которые установил Эйлер, решая задачу про Кенигсбергские мосты, он вывел еще два СВОЙСТВА: 4) Число нечетных вершин графа всегда четно. 4) Число нечетных вершин графа всегда четно. 5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа. 5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа. Например, если фигура имеет четыре нечетные вершины, то ее можно начертить самое меньшее двумя росчерками.

Мирон Елизавета Анна Тимофей Домна Елена Иван Валентина Иван Татьяна Александр Дарья Екатерина Моя родословная

Другие примеры графов Изображение железных дорог на географических картах; Схемы авиалиний Схемы метро Иерархия объектов (например структура школы) Файлы системы компьютера

Схема метро Схема железнодорожных станций

Файловая система компьютера

В городе проводилось совещание врачей. От каждой поликлиники были приглашены 4 врача. Каждый из приглашенных работал в 2 поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание? В городе проводилось совещание врачей. От каждой поликлиники были приглашены 4 врача. Каждый из приглашенных работал в 2 поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание? Задача Ответ: 5 поликлиник; 10 врачей.

Спасибо за внимание!