Практическое применение теории графов

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ГАПОУ НСО «НОВОСИБИРСКИЙ ПЕДАГОГИЧЕСКИЙ КОЛЛЕДЖ №2»

Практическое применение теории графов

исследовательская работа

Выполнила:

Макарова Анжелика

Студентка 1 курса 103 группы

Специальность 44.02.02

Преподавание в начальных классах

Научный руководитель:

Тимченко Галина Владимировна

Новосибирск, 2016

СОДЕРЖАНИЕ

Эйлер вычислял без всякого видимого усилия,

как человек дышит или как орёл парит над землёй.

Доминик Араго

ВВЕДЕНИЕ

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

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

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

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

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

Объект исследования: сфера деятельности человека на предмет применения метода графов.

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

Задачи исследования:

познакомиться с историей возникновения графов;

изучить различные виды графов и их элементы;

рассмотреть примеры применения графов в современном мире;

рассмотреть решение задач при помощи графов;

сравнить традиционные методы решения задач с методами теории графов.

Методы изучения и исследования: знакомство с уже известными научными фактами, применение полученных знаний для решения задач.

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

ГЛАВА 1. ИСТОРИЧЕСКИЕ АСПЕКТЫ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ

История возникновения теории графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

«Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов». [22, 34]

Возникший в XIII веке город Кёнигсберг (ныне Калининград) состоял из трёх формально независимых городских поселений и ещё нескольких «слобод» и «посёлков». Расположены они были на островах и берегах реки Прегель, делящей город на четыре главные части: А) Альтштадт, Б) Кнайпхоф, В) Ломзе, Г) Форштанд. Для связи между городскими частями уже в XIV веке стали строить мосты. В связи с постоянной военной опасностью мосты имели оборонные качества. Мосты были местом шествий, религиозных и праздничных процессий, по мостам проходили православные крестные ходы (рис.1).

Старинная карта Кёнигсберга

1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный,6 — Высокий, 7 — Медовый

рис.1

С прашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке (рис. 2,3), где вершины графа соответствуют определённому району города, а ребра – мостам через реку, 
на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки.

рис.3

рис.2

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони: «Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать» [14, 28].

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

Основные определения и теоремы теории графов

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

Рис. 4

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

Примерами графов могут служить схемы авиалиний, дорог, электросхемы, чертежи многоугольников. Хорошо знакомый всем образец графа – схема новосибирского метро. Вершины – конечные станции и станции пересадок, ребра – пути, соединяющие эти станции [Приложение 1].

Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности. В качестве примера генеалогическое дерево великого русского поэта А.С.Пушкина [Приложение 2].

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), где он описывал решения головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Схема графа на рисунке 5, состоящая из «изолированных» вершин, называется нулевым графом.

Графы, в которых не построены все возможные ребра, называются неполными графами (рис.6).

Графы, в которых построены все возможные ребра, называются полными графами. Этому определению соответствует граф на рисунке 7.

рис. 5 рис. 6 рис. 7

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

Г раф называется несвязным, если первое условие не выполняется (рис.9).

рис.9

Если, например, между вершинами Д и Е провести ребро, то граф станет связным. Такое ребро в теории графов (после удаления, которого граф из связного превращается в несвязный) называется мостом.

Г раф, в котором две любые вершины соединены ровно одним простым путём, является деревом (рис.10). Чаще всего они встречаются при составлении родословных. Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли.

рис.10

После удаления любого ребра дерева, оно «распадается» на два дерева. Кружком обведены висячие вершины.

Свойства деревьев:

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

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

рис.11

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

В–Р+Г=2.

В качестве примера можно рассмотреть следующую задачу:

В стране «Озерной» - 7 озер,

Каналы их соединяют.

А между ними – острова,

И сколько их – никто не знает. [13, 276]

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

П онятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт.

Большой интерес вызывают графы, которые можно нарисовать, не отрывая карандаша от бумаги. Их называют эйлеровыми в честь учёного Леонарда Эйлера (рис.12).

рис.12

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

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

Н а рисунке 13: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

В графе сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро

рис.13

участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Число нечетных вершин любого графа четно. Во всяком графе с вершинами, где, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями. [20, 146]

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный. Соединив А с Б и А с Д получим полный, однородный граф.

В Приложении 3 подготовлен материал с эйлеровыми графами для решения в группе.

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

ГЛАВА 2. ЗАДАЧИ, РЕШАЕМЫЕ ПРИ ПОМОЩИ ГРАФОВ

2.1. Знаменитые задачи

Задача коммивояжера

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

Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Метод решения задачи коммивояжера

Ж адный алгоритм “иди в ближайший (в который еще не входил) город”.
“Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Рассмотрим для примера сеть на рисунке, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Проблема четырёх красок

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

К. Аппель и В. Хакен (используя компьютер) доказали в 1976 г., что так можно раскрасить любую карту.

Задача о трёх домиках и трёх колодцах

Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

Для решения этой задачи воспользуемся теоремой, доказанной Леонардом Эйлером в 1752 г. Если многоугольник разбит на конечное число многоуголь­ников так, что любые два многоугольника разбиения или не имеют об­щих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство : В- Р + Г=1, где В — общее число вершин, Р — общее число ребер, Г — число много­угольников (граней).

Р ешение. Предположим, что это можно сделать. Отметим домики точками Д,, Д2, Д3, а колодцы — точками К1, К2, К3. Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются. Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г = 1. Добавим к рассматриваемым граням еще одну — внешнюю часть плоскости. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В — 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку по условию задачи ни одна из дорожек не должна непосред­ственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше 5*4:2=10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.

2.2. Несколько интересных задач

" Маршруты"

Задача 1

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза.

Решение:

П о схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D- Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву.

З адача 2

На рисунке изображена схема местности.

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой — самый длинный.

Решение:

П оследовательно "расслаиваем" схему в дерево, начиная с вершины 1. Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

"Группы, знакомства"

Задача 1

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

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Р ешение: Пусть участники фестиваля А1, А2, А3 . . . , Аn – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами.

Решение:

а) степень каждой вершины Аi показывает число конвертов, которое передал участник Аi своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn , N=2p, где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.

Задача 2

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

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д. Это первые буквы имён. Соединим те точки, которые соответствуют именам созвонившихся ребят.

Из рисунка видно, что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

2.3. Применение графов в различных областях жизни людей

Кроме приведенных примеров, графы широко используются в строительстве, электротехнике, менеджменте, логистике, географии, машиностроении, социологии, программировании, автоматизации технологических процессов и производств, психологии, рекламе. [3, 7-18] Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного исследования.

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

М олекулярные графы, применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул. Вершины и ребра этих графов отвечают соответственным атомам и химическим связям между ними.
Молекулярные графы и деревья: (рис. 14 а, б) - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

рис. 14

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

Белковые сети

Б елковые сети - группы физически взаимодействующих белков, которые функционируют в клетке совместно и скоординированно, контролируя взаимосвязанные процессы, происходящие в организме (рис. 15).

рис. 15

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

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

рис. 16. Участок сети причинно-следственных связей

Известно, что у разных людей кровь отличается по группе. Существуют четыре группы крови. Оказывается, что при переливании  крови от одного человека к другому не все группы совместимы. Граф показывает возможные варианты переливания крови. Группы крови – это в ершины  графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, кровь первой группы можно переливать любому человеку, а человек  с первой группой крови воспринимает только кровь своей группы (рис.17).

рис.17

В медицине: обыкновенное дерево классификации болезней (рис. 18).

Дерево административной структуры РФ (рис. 18).

Иерархическая структура системы административного управления (граф в виде дерева), между элементами которых установлены отношения подчиненности.

рис. 18

При решении задач по информатике, можно использовать теорию графов для наглядного получения ответа. Например, решая задачу по ЕГЭ: (рис. 19).

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

Решение:

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

2) теперь по схемам определяем кратчайшие маршруты для каждой таблицы:

условие «не больше 6» выполняется только для таблицы 3

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

«Живой» лабиринт

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

Чтобы выделить отдельные созвездия из общего «звездного хаоса», первые астрономы условно соединили наиболее яркие звёзды линиями (построили графы). Всё множество видимых звёзд разделилось на отдельные группы – созвездия. Если граф ассоциировался с каким-либо знакомым объектом, то созвездию давалось соответствующее название.

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

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

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

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

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

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

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

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

Мы, ведь, знаем то , что звезды

Группируются в созвездья

Волопаса, Девы, Рака,

Скорпиона и Стрельца.

А отрезки между ними –

Это просто ребра графа,

От начала до конца.

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

Заключение

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

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

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

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

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

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

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

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

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

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

Березина Л.Ю. Графы и их применение. -M., Просвещение,1999. -144 c.

Галушкина Ю.И. Конспекты лекций по дискретной математике. – М., Айрис – пресс, 2012. – 174 с.

Гусев В.А., А.И. Орлов, А.Л. Розенталь. Внеклассная работа по математике в 6-8 классах. - М., Просвещение, 2003. – 288 с.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М., Наука, 2009. - 392с.

Зыков А.А. Теория конечных графов. – Новосибирск, Наука, 1999. – 554 с.

Савин А. Графы // Журнал Квант. – 1994. - №6 – с.32

Кириллов В. И. Логика: учебник для средних специальных учебных заведений. – М., НОРМА, 2011 – 249 с.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М., МЦНМО, 2001 – 960 с.

Лавров И.А. Математическая логика: учеб. пособие: Доп. Минобрнауки России / Под ред. Л.Л.Максимовой, 2011 - 240 с.

Смыкалова Е. В. Математика (дополнительные главы). - Санкт-Петербург, СМИО Пресс, 2006 – 48 с.

Игнатьев Е. И. Математическая смекалка. – Москва, 1994г. – 185 с.

Когаловский С.Р. Роль комбинаторных задач в обучении математике // журнал Математика в школе. -2004. - №7 –с.18

Новиков Ф.А. Дискретная математика. - Издательство СПб, Пи­тер, 2000. – 304 с.

Носов В.А. Комбинаторика и теория графов. – М., МГТУ, 1999. – 116 с.

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988

Оре О. Графы и их применение. -M., Мир, 1965. - 175 с.

Перельман Я. И. Весёлые задачи. - Астрель, АСТ, 2003. – 287 с.  

Савин А. Графы //Физико-математический журнал «Квант», - 1994. -№6- с.35

Спирина М.С., Спирин П.А. Дискретная математика. - М., Академия, 2012. – 368 с.

Сборник олимпиадных задач по математике /Под ред. В. Г. Горбачева. - М., МЦНМО, 2004. – 564 с.

Уилсон Р. Введение в теорию графов. - М., Мир. - 1977. - 208с.

Харари Ф. Теория графов. -M., Мир, 1973. – 301 с.

Энциклопедический словарь юного математика /Сост. А.П.Савин.- М., Педагогика, 1989.

ПРИЛОЖЕНИЕ

Приложение 1

Схема 1. «Новосибирское метро»

Приложение 2

С хема 2. «Генеалогическое дерево великого русского поэта А.С.Пушкина»

Приложение 3

Задачи

Задача 1

Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

Р ешение:

Составим схему-граф маршрутов:

Мы видим, что от З до М добраться нельзя.

Задача 2

При встрече каждый из друзей пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо.

Решение:

Задача решается с помощью полных графов.

1)Встретились трое:

1

2 3

Количество рукопожатий равно количеству рёбер, т.е.3.

2)Встретились четверо:

1 2

3 4

Количество рёбер 6; возможно 6 рукопожатий.

Ответ: 1)3; 2)6.

Задача 3

Нарисовать плоский граф, имеющий 6 вершин, степень каждой из которых равна а)3; б)4.

Р ешение:

Задача 4

Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной линии дважды пятиугольник с диагоналями?

Решение:

Если пятиугольник – граф и все вершины его четные – то это выполнить можно.

Задача 5 (ЕГЭ)

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

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

Решение:

(15 + 25) : 16 = 2часа 30мин – время в пути ABE

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

(11 + 34) : 20 = 2часа 15мин – время в пути AСE

2ч < 2ч 15мин < 2ч 30мин

2 (ч) = 120 (мин) Граф, соответствующий условию задачи

Задача 6 (ЕГЭ)

Ц епочка из трех бусин формируется по следующему правилу:на 3-м месте в цепочке стоит одна из бусин А, В, Г. На 2-м месте – одна из бусин А, Б, В. На 1-м месте – одна из бусин Б, В, Г, не стоящая в цепочке на втором или третьем месте. Сколько существует различных цепочек, соответствующих этому правилу?

Задача 7

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

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

Решение:

М ожно составить 16 вариантов. Например:

Математика Математиа Математика

Русский язык Русский язык История

Математика Математика Математика

История История Русский язык

Биология География Биология

География Биология География

Задача 8

Задача 9 (транспортная задача)

Пусть в городе Краснодаре находится база с сырьём, которое нужно развести по городам Крымск, Темрюк, Славянск-на-Кубани и Тимашевск одним заездом, затратив при этом как можно меньше времени и топлива и вернувшись обратно в Краснодар.

Р ешение:

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

Для удобства решения обозначаем города цифрами: Краснодар – 1, Крымск – 2, Темрюк – 3, Славянск – 4, Тимашевск – 5.

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

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

Задача 10 (логическая задача на переливание)

В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

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

Задача 11

Какие буквы русского алфавита можно нарисовать одним росчерком пера? (Б, В, Г, З, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я)

Задача 12

Если фигура имеет четыре нечётные вершины, то сколькими росчерками, самое меньшее, её можно начертить?

Задача 12

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

Задача 13

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими; 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединён с пятью другими? (Нельзя. Примените теорему о числе нечётных вершин)

Задача 14

В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог, и города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве. (Сложим количество дорог, выходящих из всех городов: 98*2+2+1+102. Это число-количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 101)