Урок по теме "Теория графов в нашей жизни"

Тема: «Теория графов
в нашей жизни»


Составила:
учитель математики
Позднякова Н.Э.

Содержание
Введение
Глава 1. «Графы»
1.1 История возникновения теории графов
1.2 Теория графов: основные понятия и виды графов.
Глава 2. «Применение теории графов»
2.1 Применение графов при решении задач
2.2 Применение теории графов в научной деятельности
2.3 Применение графов в других областях
Заключение
Список литературы
Приложения

Глава 1. Графы
1.1 История возникновения теории графов


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

рис1.

Леонард Эйлер писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведёт нечётное число мостов. Во время Второй мировой войны Кенигсбергские мосты были разрушены, но эта история положила начало теории графов. Задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов.
Над графами работали Кениг (1774-1833), Гамильтон (1805-1865). Термин «граф» впервые ввёл венгерский математик Денеш Кениг в 1936 году. С 50-тых годов XX века теория графов получила невероятное развитие, она нашла применения в задачах планирования, архитектуры, инженерии, а особенно в информатике и телекоммуникациях. Из современных математиков над данной теорией графов работали: К.Берж, О.Оре, А.Зыков. Появились новые алгоритмы, в которых используются механизмы, напоминающие биологическую революцию. Графы в них используют как способ визуализации процессов. Моделирование нейронов человеческого мозга и принципах действия легло в основу новой теории – теории нейронных сетей.

1.2Теория графов, основные понятия и виды графов
Граф – это конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.
(Примеры графов - рис.2)

В графе вершины связанны линиями: линия направленная ( со стрелкой) называется дугой; линия не направленная ( без стрелки) называется ребром.
Вершины: А, В, С, Д, Е (рис.3). Рёбра: АС, АВ, АД, ВД (рис.3)
Степень вершины – количество рёбер, выходящих из вершины графа. .


Рис. 2
рис.3
Е
а
В
с
Д
Е

Степень вершины А= 3 ; степень вершины В= 2; степень вершины С= 1; степень вершины Д= 2 (рис.3)
Нечётная вершина, если имеет нечётную степень. Вершины: А, С (рис.3)
Четная вершина, если её степень чётная. Вершины: В, Д (рис.3)
Изолированная вершина – это вершина, которая имеет степень нуль. Вершина: Е (рис.3)
Висячая вершина – это вершины из которой выходит ровно одно ребро.
Нулевой граф – это схема графа, состоящая из изолированных вершин. ( рис.4)
M• •N
•P
рис. 4
Неполный граф – это граф, в котором не построены все возможные рёбра. (рис.6)
Полный граф – это граф, в котором построены все возможные рёбра. (рис 5) рис 5

рис.6

Направленный граф– это граф, у которого на рёбрах нанесены стрелочки, указывающие направление рёбер. (рис7)
Однородный граф (регулярный граф)– это граф, у которого степени всех вершин равны. (рис.5)
Изоморфные графы – это одинаковые графы, но по-разному нарисованные. (рис.8)

рис 7
рис 8

Двудольный граф – это граф, у которого множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества. (рис. 9)
Связный граф – это граф, у которого две любые вершины соединены путём.
Неориентированный связный граф- это граф, у которого из любой вершины доступна любая другая вершина. (рис.5)
Ориентированный граф (орграф) – это связный граф, у которого нет условия доступности любой вершины из любой. (рис.10)
рис 9
рис.10

Смешанные графы – это графы,
которые имеют как направленные ребра. Так и ненаправленные. (рис.11)
Взвешенный граф – это граф, у которого каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра. ( В качестве веса может быть: длина, цены, маршруты и многое другое).
Планарный (плоский) граф – это граф, который можно изобразить на плоскости так, чтобы его рёбра не имели общих точек кроме вершин.
Эйлеров граф – это граф, в котором можно обойти все вершины и при этом каждое ребро пройти только один раз. (рис.12)
рис.11
рис.12

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

Цикл – это путь, у которого первая и последняя вершины совпадают.
Длина пути – это количество составляющих данный путь рёбер.
Длина цикла – это число рёбер в этом цикле.
Простой цикл (или путь) , если рёбра в нём не повторяются.
Подграф – это граф все вершины и рёбра которого содержатся среди вершин и рёбер исходного графа. (это путь на рисунке 8.а , состоящий из последовательности
[ (е), (а), (b), (с) ])
Компонента связности графа – это связный подграф, удовлетворяющий условиям:
если две вершины компоненты связности соединены ребром в первоначальном графе, то они соединены ребром и в компоненте связности;
не существует ребра, соединяющего вершину из компоненты связности с вершиной не из компоненты связности.

Дерево – это связный граф без циклов.
Любые две вершины соединены только
одним маршрутом. (рис.13)


Лес – это граф, состоящий из компонент дерева.
Эйлеров путь- это путь, проходящий по каждому ребру графа ровно один раз.
Основные обозначения:
G=(V, E), здесь G – граф, V – его вершины, а
E – ребра;
|V| – порядок (число вершин);
|E| – размер графа (число рёбер).

рис.13

Основные утверждения.
Утверждение 1: Количество рёбер в графе равно половине суммы степеней всех его вершин.
Утверждение 2: Сумма степеней всех вершин одной доли двудольного графа равна сумме степеней вершин другой его доли и равна общему числу рёбер в двудольном графе.
Утверждение 3: Связный граф с n- вершинами содержит хотя бы n-1 ребро.
Лемма о рукопожатии: В любом графе сумма степеней всех вершин равна удвоенному числу рёбер.

Формула Эйлера: В связном планарном графе, где V-вершины, Е – рёбра, G – грани.
V – Е + G = 2
 
Теорема: Число нечётных вершин любого графа чётно.
Вывод: для успешного применения теории графов при решении задач и практического применения графов в жизни человека мы разобрались в истории возникновения теории графов и самих графа. Изучили основные определения данной теории, виды графов, формулы, утверждения всё то, без чего не возможно успешное применение данной теории графов.

Глава 2. Применения теории графов.
2.1 Применение графов при решении задач.

С помощью теории графов и самих графов гораздо упрощаются решения многих задач: олимпиадных, конкурсных, задач теории вероятности.
Задача 1: В футбольном матче участвуют шесть команд. Четыре команды сыграли по два матча, две команды по одному матчу. Сколько всего матчей было сыграно?
Решение: будем считать команды – вершинами графа, их шесть. А сыгранные матчи – рёбрами. По утверждению 1, количество матчей будем искать следующим образом:
=5( рёбер), т.е. матчей.Ответ:5матчей.

Задача 2: На балу каждый мальчик потанцевал с тремя девочками, а каждая девочка потанцевала с четырьмя мальчиками. Сколько мальчиков было на балу, если девочек было девять?
Решение: Представим себе количество мальчиков на балу, как одну долю двудольного графа ( где мальчики – это вершины, а количество приглашений каждого, как степень вершин). Пусть количество мальчиков – х. Вторая доля двудольного графа – это девочки.
По утверждению 2: сумма степеней одной доли равно сумме степеней другой доли и равно общему числу рёбер в двудольном графе

Х 9



М Д
3х =4•9
3х=36
х= 12
Ответ: 12 мальчиков.

Задача 3: Десять хулиганов кидали снежки в окна школы. Один – в 1 окно, второй – в 2 окна, третий – в 3 окна, …, десятый – в 10 окон. В каждое окно попали 5 раз снежком, либо не попали вовсе. Сколько окон пострадали?
Решение: Хулиганы - Х Окна- О





Х О

по 5 раз

0
10
1+2+3+…+10 = 5х
55 = 5х
х = 11
Ответ: 11

Задача 4: В графе 7 вершин и 7 рёбер. Известно, что у каких-то двух его вершин степень 2, а у каких-то трёх – степень 3. Докажите, что в этом графе есть изолированная вершина.
Решение: По условию: 7- вершин, 7 – рёбер всего; 2 вершины имеют 2 степень; 3 вершины имеют 3 степень; 1 вершина – х степень; 1вершина – у степень. По утверждению 1 :
= 7(рёбер)

13 +х +у = 14
х + у = 1, следовательно,
х = 1, а у = 0- изолированная вершина,
что и требовалось доказать.

Задача 5: В государстве 21 город. 10 малых городов, 10 средних и столица. Между городами построено 25 дорог. Из каждого малого построено ровно по одной дороге, из каждого среднего - ровно по две дороги. Сколько дорог может выходить из столицы?
Решение: По условию 21 вершина – всего; 25 рёбер всего. 10 малых городов – имеют степень 1; 10 средних – степени 2. Одна столица – степень х.
По утверждению 1 :
= 25 (рёбер)
30 + х = 50
х = 20
Ответ: 20 дорог выходит из столицы.

Задача 6: Дядька Черномор и 33 богатыря в течение 50 дней каждый день отправляли двух человек патрулировать берег моря ( либо двух богатырей, либо дядьку Черномора и богатыря). Известно, что никакая пара не дежурит дважды. Могло ли так оказаться, что каждый богатырь дежурил ровно 2 раза?
Решение: Всего 34 человека – вершины графа, патрули по 2 следовательно 50 рёбер ( 50 пар), 33 богатыря – 2, дядька Черномор – х.
= 50
66 + х = 100
х = 100 - 66
х = 34 Ответ: нет

Х Г



5х = 4• г ( г – количество гимнасток)
Из данного равенства следует, что левая часть
равенства должна делиться на 4.
Хоккеистов должно быть: 4, 8, 12,…
4 не подходит. Необходимо наименьшее значение. Г =10
В сумме 8 хоккеистов и 10 гимнасток – это 18 спортсменов.
Ответ: наименьшее число спортсменов 18.

Задача 7: В школе олимпийского резерва каждый хоккеист дружит с пятью гимнастками и пятью хоккеистами. Каждая гимнастка дружит с четырьмя гимнастками и четырьмя хоккеистами. Какое наименьшее количество хоккеистов и гимнасток в сумме могут быть?
Решение: Хоккеисты Гимнастки По утверждению 2:

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

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



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

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

рис. 14

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

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

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

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



рис.17

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

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

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

Рис.19 План

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

Рис.20
Рис.21
Рис.22

Графы в информатике.
На рисунке 23 изображены различные схемы соединения компьютеров между собой. Чаще всего встречаются три способа объединения компьютеров в локальную сеть: "общая шина", "звезда", и "кольцо". Каждой схеме соответствует граф, поэтому применяется термин «Сетевая топология». Сетевая топология - это конфигурация графа, вершины которого: компьютеры и маршрутизаторы, а рёбра – линии связи (кабель) между ними.

Схемы соединения компьютеров. Блок – схемы программ для ЭВМ рис. 23

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

Рис. 24 Графы на примере карты дорог.

Графы в авиации

Схемы авиалиний представлены в виде графов

Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов».
Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.

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

Генеалогическое древо

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

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

Схема цепей дежурного освещения
Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.

Участки Метрополитенов.
Один из участков московского Метрополитена и Санкт-Петербургского метро.

Социограммы
Социограммы (в психологии при исследовании межличностных отношений в группах).

Схема железных дорог
Вершины – железнодорожные станции, а рёбра – железнодорожные пути.

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

Список литературы
1. Оре О. Теория графов. М.: Наука, 1968.
2. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977.
3. Анализ поэтического текста: Структура стиха // Лотман Ю. М. О поэтах и поэзии. СПб., 1996. [Электронный ресурс.]
4. Малахова Л.Т. Использование структурно-логических схем на уроках литературы. Материалы международных педагогических чтений.
 

5. Берж К. "Теория графов и ее применение", М.,ИЛ, 1962г.
6. Гарднер М., Оре О. "Графы и их применения", М. "Мир", 1965г.
7. Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 1969г.
8. Ю. Нестеренко, С. Олехник, М. Потапов “Лучшие задачи на смекалку”.
9. Ресурсы сети Интернет.