Теория графов

Муниципальное бюджетное общеобразовательное учреждение

Хемчикская средняя общеобразовательная школа

села Хемчик муниципального района

«Бай-Тайгтнский кожуун Республики Тыва»

Теория графов

Выполнил: ученик 8 класса

Салчак Сайын Март-оолович

Руководитель: Манзырыкчы

Дензенмаа Хереловна.

Хемчик – 2015г

Содержание

Введение.

Глава 1. теория графов.

1. История возникновения теории графов на примере исторической задачи. Первое знакомство с графами. Основные законы и правила теории графов.

Глава 2. применение теории графов

2.1 Задачи о мостах. Применение свойств графов для рисования фигур одним росчерком пера. Понятие эйлеровы цикла.

2.2 Логические задачи

2.3 Теория расписаний

2.4 Заключение.

2.5Использованная литература

Введение

В настоящее время теория графов является разделом дискретной математики.

«В математике следует помнить не формулы, а процесс мышления» - эти слова русского математика Е.И Игнатьева подчеркивают полезность теории. Графов.

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

Совокупность вершин и соединяющих их ребер на плоскости называется графом. Примерами графов могут:

• Схемы метрополитена;
• Схемы железных и автомобильных дорог;
• Планы выставок;
• Структурные формулы молекул в химии.

Графы широко используются в

• Современной математике;
• Программировании;
• Приложение в теории планирования и управления;
• Теории расписаний;
• Социологии;
• Экономике;
• Биологии;
• Медицине и т.д

Основы теории графов как математической науки заложил в 1736г Леонард Эйлер.

Теория графов.

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

Задача 1: «Мне была предложена задача об острове, расположенном в городе Кенигсберга и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно прейти обойти их, проходя только по одному разу через каждый мост». (Это из письма Л.Эйлера итальянскому математику и инженеру Маринони в 1736г)

Правый берег

                       Левый берег

                                        Л

       А

                                                        П

Б

Задача 1. Это чертеж задачи.

                    Правый берег.

           Левый берег.

Через остров А перекинуто 5 мостов. Значит А=5. Через остров Б перекинуто 3 моста. Значит Б=3. На правом берегу 3 моста, на левом тоже 3 моста.

Составим граф по чертежу

Понятие индекса вершины – это число ребер, сходящихся в одной точке.

В точке Б-3 ребер,

В точке Л-3 ребер,

В точке П-3 ребер.

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

Основные правила и законы теории графов:

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

Например:

б)

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

        д)

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

а)

в)

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

г)        д)

        рис.3

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

Задача 2. Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребре. Подрыгивать и перелетать с места на место не разрешается.

Рис.4

Решение: ребра и вершины куба образуют граф, все 8 вершин которого кратность 3 и, следовательно, требуемый обход невозможен.

Задача 3. Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома ходил к «своему» колодцу по своей тропинке. Удается ли им это сделать?

Из вершины 3 ведет один отрезок к дому хозяину дома Д. Хозяин дома Д должен ходить к колодцу 3. Д->3.

Из вершины 4 ведет один отрезок к дому хозяину дома В. Хозяин дома В должен ходить к колодцу 4. В->4.

Из вершины 1 выходит 2 отрезка. Один к дому Д, другой к дому Г. Но хозяин дома Д ходит к колодцу 3. значит, хозяин дома Г должен ходить к колодцу 1. Г->1.

Хозяин дома А должен ходить к колодцу 5. А->5 т.к ближе к дому. Хозяин дома Б должен ходить к колодцу 2. Б->2

                                 А                                  В

                                               5                                                            4

             3                                                                                        Б

                                                                2

                                             Д

        Рис. 5

Начертим граф с десятью вершинами и десятью ребрами.

Числа колодцы, буквы дома.

        Б        В

        Г

А

        Д

        5

1

        2                3        4

Выберем из десяти ребер пять, не имеющих общих вершин. Заметим, что в вершины 3 и 4 ведет по одному из вершин Д и В. Это озночает, что хозяин дома должен ходить к колодцу №3, а хозяин дома В -  колодцу №4. Вершина 1 соединена ребрами с Г и Д.

Ребро 1-Д отпадает, остается реберо 1-Г (хозяин дома Г- к колодцу №1.)

Остается соединить вершины А и Б с вершинами 2 и 5. это сделаем двумя способами: либо выбрать ребра А-5 и Б-2, либо ребра А-2 и Б-5. других вариантов нет.

Логические задачи.

Задача 4. Орлан, Аяс, Кудер и Дозураш – друзья. Один из них – врач, другой -журналист, третий спортсмен, а четвертый строитель. Журналист написал статьи о б Орлане и Дозураше. Спортсмен и журналист вместе с Аясом ходили в поход. Орлан и Аяс были на приеме у врача. У кого какая профессия?

Решение: составим граф

Орлан                     Аяс                    Кудер                Дозураш

Врач                журналист        спортсмен        строитель

Комбинаторные задачи

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

Первое блюдо         второе блюдо            Третье блюдо            Варианты обеда.

Всего 12 вариантов.

Применение теории графов.

 Расписание нашей школы.

1 смена.

5              8                       9                                   10                        11

Русский       алгебра М/С    анг                                    физика          география

Ч/О                            ист.тувы                         тув. С/Х      

Заключение

Теория графов- наука сравнительно молодая: во времена Ньютона такой науки еще не было, хотя и были в ходу «генеалогические деревья», представляющие собой разновидности графов. В настоящее время почти в любой отрасли науки и техники встречаешься с графами: в электродинамике и физике – при построении электрических схем, в химии и биологии – при изучении молекул и их цепочек, в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта, истории, географии в математике; в географии – для составления карт. С теорией графов связаны не только математические развлечения и головоломки, но и такие серьезные науки, как теория групп. Приступая к данному исследованию, мы ставили перед собой задачу вызвать интерес к изучению предмета «математика и ее приложения» через язык графов и показали роль графов в различных областях науки и техники для улучшения логического мышления детей.

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

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

1. Н.Я Виленкин. Математика 5, Н.Я Виленикин, В.И Жохов, А.С Чесноков, С.И Швацбурд – 1997.
2. М.Гарднер «Математические головоломки и развлечения». М.Гарднер – М «Мир», 1971.
3. Н.Н Видеман. Математика 10-11 классы. Рефераты, Т.Н.Видеман, Е.В Алтухова, Н.И Мазурова, Н.А.Докучаева – Волгоград, 2009г.
4. Г.А Троякова. Элементы комбинаторики и теории вероятности, Г.А Троякова – Кызыл, 200.
5. Обучение элементам теории графов. Математика в школе  - 2004
6. С.А Литвинова. За страницами учебника математики, С.А.Литвинова, Л.В Куликова, С.В Шиловская, Г.Ю Тараева – панорама, ОО «Глобус», 2008.