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

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ .

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

Виды графов:

1. Ориентированный граф (кратко орграф ) - рёбрам которого присвоено направление.

2. Неориентированный граф - это граф , в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Решение задач с помощью графов:

Задача 1.

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

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Решение:

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

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Решение:

Ниже представлен разбор задач.

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 2

Подготовил

Легкоконец Владислав, ученик 10А класса

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

Руководитель

Л.И. Носкова, учитель математики

ст.Брюховецкая

2011 г.

1.Введение………………………………………………………………………….………….3

2.История возникновения теории графов………………………………………….………..4

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

4.Задачи,решаемые при помощи графов……………………………..……………………..8

4.1 Знаменитые задачи………………………………….………………………...8

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

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

6.Решение задач……………………………………………………………………………...12

7. Заключение………………….…………………………………………………………….13

8. Список литературы………….……………………………………………………………14

9.Приложение…………………………………………………………………….…………15

Введение

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

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

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

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

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

1.Изучить литературу и ресурсы сети Интернет по данной проблеме.

2.Проверить эффективность метода графов при решении практических задач.

3. Сделать вывод.

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

В работе используются следующие методы: наблюдение, поиск, отбор, анализ.

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

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

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

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

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:

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

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

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

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

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

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

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

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B , C , D . Иногда граф в целом будем обозначать одной заглавной буквой.

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

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

Обозначение: O "– граф с вершинами, не имеющий ребер

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

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

Определение 5. Степеньювершиныназывается число ребер, которым принадлежит вершина.

Определение 6. Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепениk .

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

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

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

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

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

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

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

Определение 13. Длиной пути, проложенного на цикле, называется число ребер этого пути.

Определение 14. Две вершины A и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из A в B .

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

Определение 16. Деревомназывается связный граф, не содержащий циклов.

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

Определение 17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Определение 18. Дерево, все n вершин которого имеют номера от 1 до n , называют деревом с перенумерованными вершинами.

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

Задачи решаемые при помощи графов

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

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

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

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

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

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

Задача о Кенигсбергских мостах.

Задача формулируется следующим образом.
Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту.
Мосты через реку Прегель расположены как на рисунке [приложение Рис.1].

Рассмотрим граф, соответствующий схеме мостов [приложение рис.2].

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

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

1. "Маршруты".

Задача 1

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

Решение :

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

Задача 2

На рисунке изображена схема местности [приложение рис.6].

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

Решение :

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

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

Задача 1

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

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

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

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

Решение:

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

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

Задача 2

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

Решение:

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

[ приложение рис.9]

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

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

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

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

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

Молекулярные графы и деревья: [приложение рис.10] а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

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

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

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

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

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

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

Пример генеалогического дерева моей семьи [приложение рис.12].

Еще один пример. На рисунке показано библейское генеалогическое дерево [приложение рис.13].

Решение задач

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

Решение:

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

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

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

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

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

Решение:

Ситуацию в каждый момент можно описать тремя числами [приложение рис.16].

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Заключение

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

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

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

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

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

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

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

Литература

Берж К. Теория графов и ее применения. -M.: ИИЛ, 1962.

Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. -M.: ИИЛ, 1963.

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

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

Зыков А.А. Теория конечных графов. -Новосибирск: Наука, 1969.

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

"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

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

Приложение

Приложение

П

Рис. 6

Рис. 7

Рис. 8

риложение

Приложение

Приложение

Приложение

П

Рис. 14

риложение

Приложение

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

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

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

Предметом исследования в данной работе является решение логических задач при помощи графов.

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

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

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

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

научиться переводить задачи на язык графов;

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

В 1736 году великий математик Леонард Эйлер нашел решение головоломки, носящей название «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом) омывает два острова (рис. Рисунок 1Рисунок 1). Берега реки с островами были во времена Эйлера связаны мостами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать.

Рисунок 1

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

Рисунок 2

Схема, приведенная на рисунке Рисунок 2 не является, строго говоря графом: на ней имеются кратные ребра. Тем не менее 1736 год, когда эта головоломка была решена, принято считать годом рождения теории графов.

Спустя сто с лишним лет, в 1874 году немецкий ученый Г. Кирхгоф разработал эффективную методику определения значения силы тока в электрической цепи, используя методы и понятия, получившие позднее права гражданства в теории графов. Еще 10 лет спустя английский математик А. Кели (мать его была русской, он владел русским языком и следил за русской математической литературой; он оказался среди тех немногих математиков, которые с самого начала поняли и поддержали идеи Н.И. Лобачевского) разработал теорию деревьев для подсчета числа изомеров насыщенных углеводородов с данным числом n атомов углерода.

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

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

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

Рисунок 3

Граф на рис.Рисунок 3 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф, на котором легко увидеть возможные маршруты. Вершина М вверху- начало маршрутов. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4321  24 способа.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G 1 (рис.Рисунок 4).

Рисунок 4

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

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

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

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

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

Задача 1. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Приведем подробное решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому вначале должен возникнуть граф, изображенный на рисунке Рисунок 5.

Рисунок 5

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

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

Рисунок 7

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров - рыжий, Чернов - белокурый, Ры­жов – брюнет. Таким же приемом решаются, например, задачи 2 и 3.

Задача 2. Для Вани, Коли и Миши испечены пи­роги: один с капустой, другой с рисом, третий – с яблоками. Миша не любит пирог с яблоками и не ест с капустой. Ваня не любит пирог с капустой. Кто какой пирог ест?

Задача 3. На одном заводе работают три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Ива­нов и Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назовите фамилии сле­саря, токаря и сварщика.

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

Задача 4. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

Решение. Выделим три множества: множество имен, множество предметов и множество городов. Эле­мент каждого из множеств на рисунке 4 задан своей точкой (буквы на этом рисунке - первые буквы соот­ветствующих слов). Если две точки из разных множеств характеризуют признаки разных людей, то будем сое­динять такие точки штриховой линией. Если же две точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попар­но сплошными линиями. Существенно, что по условию задачи для каждой точки любого множества в каждом из остальных множеств найдется одна и только одна точка, ей соответствующая.

Рисунок 8

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

Рассмотрим граф на рисунке 8. Напрашивается штри­ховой отрезок ХД, Действительно, Л соответствует X и, одновременно, Л не соответствует Д, т. е. X не может соответствовать Д. Итак, используется типичная для такого рода задач операция на графе: если у тре­угольника с вершинами в трех разных множествах одна сторона сплошная, вторая - штриховая, то третья должна быть штриховой. Из условия задачи следует равномерность еще одной операции на графе: если какая-то точка соединена штриховыми отрезками с двумя точками во втором множестве, то ее следует со­единить с третьей точкой этого множества сплош­ным отрезком. Так проводится сплошной отрезок ДФ. Далее проводится штриховой отрезок ДМ (в тре­угольнике ДФМ сторона ДФ сплошная, а ФМ - штри­ховая), ДК сплошным (ДМ и ДЛ штриховые), Теперь соединим точки Ф и К сплошным отрезком. Если в треугольнике с вершинами в разных множествах две стороны сплошные, то третья тоже будет сплошной. Найден первый «сплошной» треугольник ДФК. Так, не возвращаясь к тексту задачи, руководствуясь лишь естественными операциями на графе, описанными выше, мы находим решение (рис. 9).

Рисунок 9

Отметим последователь­ность, в которой проводились отрезки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподает химию в Ленинграде, Дмитрий - физику в Киеве и Степан - биологию в Москве.

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

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, француз­ским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 10

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 11

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечи­вают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

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

Задача 6. В шахматном турнире принимали уча­стие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер. Известно:

1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;

2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;

3. в третьем туре Евдокимов играл с инженером;

4. по окончании турнира места распределились так - Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.

Какие профессии имели Григорьев, Дмитриев и Евдо­кимов?

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

ВВЕДЕНИЕ

«В математике следует помнить не формулы, а процесс мышления…»

Е. И. Игнатьев

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

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

Цель определила следующие задачи:

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

изучить основные понятия теории графов и основные характеристики графов;

показать практическое применение теории графов в различных областях знаний;

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

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

Предмет исследования: раздел математики «Теория графов».

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

Методы исследовательской работы:

В ходе нашего исследования были использованы такие методы, как:

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

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

ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ

1. Теория графов. Основные понятия

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

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

Термин «граф» в математике определяется следующим образом:

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

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

Рис. 1 Примеры графов

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

Рис. 2 Вершина графа

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

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

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

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

Если граф связанный, но не содержит циклов, то такой граф называетсядеревом .

1. Характеристики графов

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

Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.

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

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

Раскраска графов и применение.

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

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

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

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Можно представить задачу о четырех красках несколько иначе.

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

Эйлеровы и Гамильтоновы графы

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

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

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

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

При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.

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

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

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

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

Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом . Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.

ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ

2.1. Этапы проведения исследования

Для проверки гипотезы исследование включало три этапа (таблица 1):

Этапы исследования

Таблица 1.

		Используемые методы
Теоретическое исследование проблемы	Изучить и проанализировать познавательную и научную литературу.	 самостоятельное размышление;  изучение информационных источников;  поиск необходимой литературы.
Практическое исследование проблемы	Рассмотреть и проанализировать области практического применения графов;	 наблюдение;  анализ;  сравнение;  анкетирование.
3 этап. Практическое использование результатов	Обобщить изученную информацию;	 систематизация;  отчет (устный, письменный, с демонстрацией материалов)	сентябрь 2017 г.

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

Графы и информация

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

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

Графы и химия

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

CnH 2n+2

Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.

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

Графы и биология

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

Графы и физика

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

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

Математика интернета

Интернет - всемирная система объединенных компьютерных сетей для хранения и передачи информации.

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

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

Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин.

Несмотря на разреженность, интернет очень тесен. От одного сайта до другого по ссылкам, можно перейти за 5 - 6 кликов (знаменитая теория «шести рукопожатий»).

Как мы знаем, степень графа - это число ребер, которым принадлежит вершина. Степени вершин веб-графа распределены по определенному закону: доля сайтов (вершин) с большим количеством ссылок (ребер) мала, а сайтов с малым количеством ссылок - велика. Математически это можно записать так:

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

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

Интернет как целое устойчив к случайным атакам на сайты.

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

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

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

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

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

г. Мурманск с помощью графа.

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

В качестве примера рассмотрим типичный случай прибытия в Мурманск из аэропорта в первый раз. Планируется посетить следующие достопримечательности:

1. Морской православный храм Спас-на-водах;

2. Свято-Никольский собор;

3. Океанариум;

4. Памятник коту Семену;

5. Атомный ледокол Ленин;

6. Парк Огни Мурманска;

7. Парк Долина Уюта;

8. Кольский мост;

9. Музей истории Мурманского морского пароходства;

10. Площадь Пяти углов;

11. Морской торговый порт

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

Достопримечательности на карте (слева) и полученный граф (справа) показаны на соответствующем рисунке ПРИЛОЖЕНИЯ №1. Таким образом, новоприбывший вначале проедет около Кольского моста(и, при желании может пересечь его туда - обратно); затем отдохнет в Парке Огни Мурманска и Долине Уюта и отправится дальше. В итоге оптимальный маршрут составит:

С помощью графа можно также визуализировать схему проведения соцопросов. Примеры представлены в ПРИЛОЖЕНИИ №2. В зависимости от данных ответов опрашиваемому задают разные вопросы. Например, если в социологическом опросе №1 опрашиваемый считает математику важнейшей из наук, у него спросят, уверенно ли он чувствует себя на уроках физики; если же он считает иначе, второй вопрос будет касаться востребованности гуманитарных наук. Вершинами такого графа являются вопросы, а ребрами - варианты ответов.

2.3. Применение теории графов при решении задач

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

Задача №1.

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

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

Ответ: 10 рукопожатий (каждая линия означает одно рукопожатие).

Задача №2.

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

Решение:

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

Ответ: клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача №3.

У Мамы есть 2 конверта: обычный и авиа, и 3 марки: квадратная, прямоугольная и треугольная. Сколькими способами Мама может выбрать конверт и марку, чтобы отправить письмо Папе?

Ответ: 6 способов

Задача №4.

Между населенными пунктами A, B, C, D, E построены дороги. Нужно определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, длина которых указана на рисунке.

Задача №5.

Тремя одноклассника - Максим, Кирилл и Вова решили заняться спортом и прошли отбор спортивные секции. Известно, что в баскетбольную секцию претендовал 1 мальчик, а в хоккей хотели играть трое. Максим пробовался только в 1 секцию, Кирилл отбирался во все три секции, а Вова в 2. Кого из мальчиков в какую спортивную секцию отобрали?

Решение: Для решения задачи применим графы

Баскетбол Максим

Футбол Кирилл

Хоккей Вова

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

Задача №6.

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

1. Преподаватель ОБЖ согласен дать только последний урок;

2. Преподаватель географии может дать либо второй, либо третий урок;

3. Математик готов дать либо только первый, либо только второй урок;

4. Преподаватель физики может дать либо первый, либо второй, либо третий уроки, но только в одном классе.

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

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

1. 1) физика 2. 1) математика 3. 1) математика

2) математика 2) физика 2) география

3) география 3) география 3) физика

4) ОБЖ 4) ОБЖ 4) ОБЖ

Заключение

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

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

Гарднер М. «Математические досуги», М. «Мир», 1972

Гарднер М. «Математические головоломки и развлечения», М. «Мир», 1971

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

Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664

Касаткин В. Н. «Необычные задачи математики», Киев, «Радяньска школа», 1987

Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюшкин. - М.: Фонд «Математические этюды» 2015 г. - 151 с.

Мельников О. И. «Занимательные задачи по теории графов», Мн. «ТетраСистемс»,2001

Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.

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

Оре О. «Графы и их применения», М. «Мир», 1965

Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.

ПРИЛОЖЕНИЕ №1

Составление оптимального маршрута посещения главных достопримечательностей

г. Мурманск с помощью графа.

Оптимальный маршрут составит:

8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.

ПУТЕВОДИТЕЛЬ ПО ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ МУРМАНСКА

ПРИЛОЖЕНИЕ №2

Социологические опросы № 1, 2

Учебное издание

Ююкин Николай Алексеевич

ЛР № . Подписано в печать

Уч. Изд. л.. , .

Воронежский государственный технический университет

394026 Воронеж, Московский просп. 14

СПРАВОЧНИК МАГНИТНОГО ДИСКА

Кафедра высшей математики и физико-математического моделирования

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Воронеж 2004

ВВЕДЕНИЕ

Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;

090106 - Информационная безопасность телекоммуникационных систем.

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

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

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

в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла

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

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

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

Достижению данной цели служат следующие задачи:

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

получить навыки решения учебных и практических задач;

овладеть методами оптимизации;

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

Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении общепрофессиональных и специальных дисциплин.

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

1.1. Задачи теории графов.

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

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

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

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

Вторая задача . Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

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

решена Понтрягиным и независимо от него Куратовским в

Третья задача . О четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.

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

1.2. Основные определения.

Графом G= (V,E ) называется совокупность двух множеств - непустого множества вершин V и множества неупорядоченных и упорядоченных пар вершин E . В дальнейшем будут рассматриваться конечные графы , т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называется ребром , а упорядоченная - дугой .

Обычно граф изображается диаграммой : вершины - точками (или кружками), ребра – линиями произвольной конфигурации. На дуге дополнительно стрелкой указывается её направление. Отметим, что при изображении графа несуще-

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

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

Говорят, что ребро (u,v ) соединяет вершины u и v , а дуга (u,v) начинается в вершине u и заканчивается в вершине v , при этом u называется началом , а v – концом этой дуги.

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

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

Граф, состоящий из одной изолированной вершины (K 1 ), называется тривиальным .

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

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

1.3. Степени вершин графа.

Степенью (валентностью) (обозначение d (v ) или deg (v )) вершины v простого графа G называется число ребер или дуг инцидентных данной вершине v . При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равны k , то граф называется регулярным (однородным) степени k . Если степень вершины равна 0 , то она является изолированной . Если степень вершины равна 1 , то вершина называется концевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v назы-

вается полустепенью исхода										(v ), а входящих – полустепе-
нью захода d							(v ), При этом справедливо соотношение d (v )=
		(v )+			(v ).

Теорема Эйлера : Сумма степеней вершин графа равна

удвоенному количеству ребер, т.е.

d (vi )

			(v )

Где n – число вершин; m – число

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

1.4. Изоморфизм графов.

Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими либо по-

метками (номерами). Граф считается полностью заданным в строгом смысле , если нумерация его вершин и ребер фиксирована. При этом графы G 1 и G 2 называются равными (обозначение G 1 = G 2 ) , , если их множества вершин и ребер совпадают. Два графа или псевдографа G 1 = (V 1 ,E 1 ) и G 2 = (V 2 ,E 2 ) называют-

	изоморфными (обозначение G				если существуют
	взаимно однозначных отображения: 1)				: V 1 V 2
: E 1 E 2 такие, что для любых двух вершин u , v в графе
	справедливо соотношение ((u , v )) ((u ), (v )) .
	Два простых графа (без петель и кратных ребер) G 1					и G 2

оказываются изоморфными, если существуют взаимно одно-

значное отображение

: V 1 V 2

Такое что

(u , v ) ((u ), (v )) .

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

Рефлексивности -

G 1 ,

причем биекция

ставляет собой тождественную функцию.

Симметричности.

с биекцией

с биекцией

Транзитивности.

G 1 G 2

биекцией

1 ,а

с биекцией

то G G

с биекцией

2 (1 ) .