V региональная научно-практическая конференция школьников «Эврика» Секция математика графы и их применение - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
2. 1 Научно-практическая конференция проводится в рамках подготовки... 1 36.4kb.
Конференция: XI научно-практическая конференция «Лекарства и дети. 1 41.87kb.
Научно-практическая конференция по оени 1 13.03kb.
Организация, становление и развитие Государственной санитарно-эпидемиологической... 1 22.34kb.
Научная конференция профессорско 11 2468.87kb.
Отчет о работе конференции международная научно-практическая конференция... 1 26.25kb.
Международная научно-практическая конференция Посвященные 20 летию... 1 25.64kb.
Iii межрегиональная научно-практическая конференция 1 39.84kb.
Отчет о проведении исследовательской научно-практической конференции 1 22.05kb.
Семинара «Лингвистический компонент обучения и исследовательская... 1 13.16kb.
Научно-практическая конференция студентов и аспирантов 1 25.2kb.
Предложения немецких фирм за март, апрель 2005 года 1 108.56kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

V региональная научно-практическая конференция школьников «Эврика» Секция математика - страница №1/1

V региональная научно-практическая конференция школьников «Эврика»
Секция МАТЕМАТИКА



Графы и их применение






Автор проекта: Потапов Сергей, ученик 11 класса

МОУ «Георгиевская СОШ»


Научный руководител: Зырянова Людмила Кузьминична,

учитель математики и информатики

МОУ «Георгиевская СОШ»
Почтовый адрес:

646974 Омская область, Кормиловский район,

с. Георгиевка, ул. Ленина 9,

МОУ«Георгиевская СОШ»,

телефон: 8-38170-35142

Адрес электронной почты: georgievschool@mail.ru
2010 год


Содержание
1.Введение 3

2.Основное содержание:

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

-Определения графа; 5

-Способы представления графа; 7

-Некоторые задачи теории графов; 8

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

3. .Вывод 11

4 . Заключение 11

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



Введение
Я занялся подробным изучением темы «Графы» после того, как однажды в разговоре с учителем, при решении задачи из тестов ЕГЭ по информатике стал чертить схему в виде палочек и кружочков, изображая условие задачи, услышал, что данная схема называется графом. Затем, изучая домашнее задание, в учебниках я стал находить похожие или немного видоизменённые рисунки (в виде схем), которые учитель назвал графами различных видов. Тогда я принял решение более подробно познакомиться с данной темой.

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

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

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

Основной метод, который я использовал в своей работе, - это метод систематизации и обработки данных.

Цель работы :


  • воспользовавшись различной литературой, справочными материалами изучить раздел дискретной математики, связанной с понятием «графа», которая приобретает сегодня всё большее значение в связи с развитием математической логики, информационных технологий;

  • рассмотреть применение графов в реальных жизненных процессах.

Задачи:

  • Ознакомиться с основными положениями теории графов;

  • Рассмотреть некоторые задачи на применение графов;

  • Найти применение графов в реальных жизненных процессах;


История возникновения теории графов
Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов.

Дискре́тная матема́тика — область математики, занимающаяся изучением дискретных (состоящих из отдельных частей) структур, которые возникают как в пределах самой математики, так и в её приложениях.



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





Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Родоначальником теории графов считается Леонард Эйлер. «Мне была предложена задача об острове, в городе Кёнигсберге и окружённой рекой, через которую перекинуто 7 мостов. Спрашивается может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост…» (Из письма Л. Эйлера итальянскому математику и инженеру Маринони от 13 марта 1736 г.) Впоследствии эта задача стала одной из классических задач теории графов.





История семи мостов Кёнигсберга

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





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

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







Существуют различные семейства графов:

цепи, циклы, звезды и колеса.






Определения

Граф или неориентированный граф G  — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия: 1. V это множество вершин или узлов,; 2. E это множество (неупорядоченных) пар различных вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концами ребра e = {u,v}, которое соединяет эти вершины.





Ориентированный граф (орграф)G— это упорядоченная пара G: = (V,A), для которой выполнены следующие условия: 1) V это множество вершин или узлов, ;2) A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги.




Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными.

Записывается упорядоченной тройкой G: = (V,E,A). 1. V это множество вершин или узлов, ; 2. E это множество (неупорядоченных) пар различных вершин, называемых рёбрами,; 3. A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Ориентированный и неориентированный графы являются частными случаями смешанного.






Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром. Последовательности дуг: а6, а5, а9, а8, а4. (1); а1, а6, а5, а9. (2); а1, а6, а5, а9, а10, а6, а4. (3) являются путями.



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

Пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а6 в нем используется дважды.

а6, а5, а9, а8, а4. (1); а1, а6, а5, а9. (2) ; а1, а6, а5, а9, а10, а6, а4. (3)




Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Путь (2) является простой орцепью, а пути (1) и (3) – нет. а6, а5, а9, а8, а4. (1) а1, а6, а5, а9. (2) а1, а6, а5, а9, а10, а6, а4. (3)




Граф называется: связным, если для любых вершин u,v есть путь из u в v (т. е. если любая вершина достижима из любой другой вершины). Сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь. Граф называется несвязным, если любая вершина не достижима из любой другой вершины

связный граф с петлей

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

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


3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.




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

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





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



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


Два ребра называются смежными, если они имеют общую концевую вершину. Два конца одного и того же ребра называются соседними. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}. Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.



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

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

Матрица инцидентности. Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается 1 в случае если связь j «выходит» из вершины i, −1 если связь «входит» в вершину, любое число отличное от 0,1,-1 если связь является петлей, и 0 во всех остальных случаях. Данный способ является самым емким (размер пропорционален | E | | V | ) и неудобным для хранения, но облегчает нахождение циклов в графе

Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
 Матрица примыканий AdjMat графа G = (V, E) с числом вершин |V| = N записывается в виде двумерного массива размером N x N. В каждой ячейке [i, j] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины vi в вершину vj ведет ребро, и тогда в ячейке записано значение 1.



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

а – эйлеров граф, б – полуэйлеров граф и в – граф, не являющийся ни эйлеровым, ни полуэйлеровым




Задача о мостах, Леонард Эйлер

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



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

Упрощённая схема мостов Кёнигсберга.


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

  1. Какие буквы русского алфавита можно нарисовать одним росчерком пера?

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

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

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

  5. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог, и города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве.

Ответы:

  1. Б,В, Г, З, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я.

2.
3. Граф связан, степени всех его вершин чётны.

4. Нельзя. Примените теорему о числе нечётных вершин.

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

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

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

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




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

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



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

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





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

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

Теория графов в информатике и программировании (блок – схемы программ для ЭВМ).

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

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

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

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

Дерево административной структуры РФ ( Приложение, рис. 6)

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

Я хочу представить иллюстративный материал, собранный мной из различных учебников за 10 класс. А так же генеалогическое родовое дерево моей семьи. Оно заполнено не до конца. Но я планирую с родителями посетить летом дальних родственников и завершить работу по заполнению. ( Приложение, рис. 8)



ВЫВОД


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

  • Язык графов прост, понятен и нагляден.

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

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

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

Заключение:


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

  • Показал применение графов в реальных жизненных процессах с применением иллюстраций.

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

  • Но я не буду останавливаться на достигнутом и планирую в дальнейшем расширить работу по теме «Графы», пополняя её как теоретическими, так и практическими знаниями. Мне предстоит до конца заполнить генеалогическое родовое дерево.

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




  • Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu

  • Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu

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

  • Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)

  • Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. – 168 c.

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

  • Квант №6 1994г.


ПРИЛОЖЕНИЕ

Рисунок 1:
Использование теории графов в оценке транспортной доступности транспортных узлов
На рис.1 приведен граф (схема), отражающий транспортную сеть Архангельской области


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



Рисунок 3:

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





Рисунок 4:


Рисунок 5:


Рисунок 6:

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




Рисунок 7:

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





Решение:

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



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



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


Рисунок 8:

Кристаллическая решетка Атом вещества Молекула уксусной кислоты

поваренной соли (Химия 10кл. О.С.Габриелян) (Химия 10кл. О.С. Габриелян)

(Физика 10кл. Г.Я. Мякишев)

(Химия 10кл. О.С.Габриелян)



Биология 10-11кл. В.И. Сивоглазов




(Информатика 10-11кл. Н. Угринович)


(География 10 кл. В.П. Максаковский)

СЕМЬЯ ПОТАПОВЫ










izumzum.ru