Элементы теории графов в мировой динамике

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ФАКУЛЬТЕТ МЕЖДУНАРОДНЫХ  ОТНОШЕНИЙ

КАФЕДРА МЕЖДУНАРОДНОГО ТУРИЗМА

 

 

 

 

 

 

 

 

 

Реферат

по дисциплине «Высшая математика»

 

 

 

«Элементы теории графов в мировой динамике»

 

 

 

 

 

Студенты 1-го курса

кафедры международного туризма

Романович М.А.

Герасимович Н.Н.

 

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

преподаватель

Яшкин В.И.

 

 

 

 

 

 

Минск

2012

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

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

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

Изучение прикладной математики способствует эстетическому воспитанию человека, развивает воображение.

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

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

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

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

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

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

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

 

Сведения из истории  графов. Граф и его элементы.

Исследование задачи о  мостах Кенигсберга Эйлер в 1736 г представил в Петербургскую Академию Наук. Работа начинается определением той области математики, к которой относятся подобные вопросы:

«Кроме той области  геометрии, которая рассматривает  величины, и способы измерения… Лейбниц первым упомянул о «геометрии положения», она занимается только расположением частей фигуры друг относительно друга, отвлекаясь от их размеров. Недавно  мне пришлось слышать об одной  задаче, относящейся к геометрии  положения, и я решил изложить здесь в виде примера найденный  мной способ решения этой задачи».

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

- Понятие графа и его  элементов. Примеры графов. Полный  граф. Четность вершины графа.  Основные теоремы теории графов.

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

 

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

 

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

 

Задача четырех  красок.

Учащиеся знакомятся с  задачей раскраски карты. Задача известна достаточно давно, но в качестве теоремы или задачи впервые была выдвинута Мебиусом в 1840 году. Суть задачи в следующем.

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

Прослеживается аналогия этой задачи с Эйлеровой задачей о мостах. Предположение о 4-х красках никто не доказал, но никто и не опроверг.

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

Тема 3. История лабиринтов.

Происхождение задач о  лабиринтах относится к глубокой древности и теряется во мраке  времен.

Слово «лабиринт» (греческое) означает «ходы в подземельях».

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

Возможен ли безвыходный  лабиринт?

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

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

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

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

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

Ø Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

Ø Второй метод – МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Не зачёркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

Ø Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

                            

 

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

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

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

 

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

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число  сообщений требуется закодировать в виде конечных последовательностей  различной длины, состоящих из нулей  и единиц. Если вероятности кодовых  слов заданы, то наилучшим считается  код, в котором средняя длина  слов минимальна по сравнению с прочими  распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана. Двоичные кодовые деревья допускают  интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно  либо "да", либо "нет". Утвердительному  и отрицательному ответу соответствуют  два ребра, выходящие из вершины. "Опрос «завершается, когда удается  установить то, что требовалось. Таким  образом, если кому-то понадобится взять  интервью у различных людей, и  ответ на очередной вопрос будет  зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного  дерева.

Графы и химия

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

CnH2n+2

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

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

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

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

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

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

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

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

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

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