Теория графов.Реферат. Презентация.

Муниципальное бюджетное общеобразовательное учреждение
«Средняя общеобразовательная школа №31»
Октябрьского района г. Барнаула

Теория графов

Реферат

                                                            Выполнил: Насретдинов Рауф

                                         ученик 10 А класса

                                                                          МБОУ «СОШ №31»  
г. Барнаула

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

Полева Ирина Александровна

учитель математики МБОУ «СОШ №31»

 Барнаул - 2013

Содержание

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

2. Определение графа……………………………………………………….4

3. Вводные задачи…………………………………………………………...5

4. Основные теоремы теории графов………………………………………6

5. Задачи на применение теории графов…………………………………...8

6. Приложение теории графов в различных областях науки  и техники...11

7. Маршрутизация…………………………………………………………..13

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

9. Список используемой литературы……………………………………...14

Введение

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

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

Леонард Эйлер  — швейцарский, немецкий и российский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук.

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

 На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

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

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

           Определение графа

Граф G – упорядоченная пара (V,E), где V – множество и E семейство неупорядоченных пар элементов из V. Элементы множества V называются вершинами графа G, а элементы Е   – его рёбрами. Вершины а, b ∈ V ребра α= a,b ∈ E называются его концами. Говорят, что α инцидентно своим концам, а концы, в свою очередь, инцидентны ребру  α.

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

Мы будем рассматривать графы, у которых число вершин и число рёбер конечно. Пусть G=(V,E)  – граф и α∈ V. Число рёбер, инцидентных вершине α, называется степенью вершины α и обозначается p(α). Пусть p – число всех рёбер, b – число всех вершин и Г – число всех граней графа G=(V,E) .

Вводные задачи

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:            Земля – Меркурий;  Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

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

Решение: Занумеруем последовательно клетки доски:

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

Задача 3. В Тридевятом царстве только один вид  транспорта  –
ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний  – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Основные теоремы теории графов

Предложение 1. 2p= ∑ p(α) , α ∈ V.

Доказательство. Сумма  ∑ p(α) , α ∈ V,учитывает каждое ребро α=b,c два раза: первый раз при вычислении p(b), второй раз при вычислении p(c).

Следствие 1. Пусть G=(V,E) – однородный граф, т.е. степени всех вершин равны между собой (и равны, например, числу k). Тогда p =  k b2 . В частности, если k – нечётное число, то число вершин является чётным. Вершина α ∈ V называется нечетной, если p(α) – нечётное число.

Следствие 2. Число нечётных  вершин графа является чётным.

Доказательство следует из равенства ∑ p(α) =2 p, α ∈ V и того, что сумма нечетного числа нечетных слагаемых является нечетным числом.

Упражнение 1. Число студентов в АГУ, имеющих нечетное число знакомых в АГУ, является четным.

Упражнение 2. (городская олимпиада, Барнаул, 1997 г., 8 класс). Можно ли соединить между собой проводами 7 телефонов так, чтобы каждый был соединен ровно с тремя другими?

Теорема (Л. Эйлер, 1752 г.). Пусть G = (V,E) – плоский связный граф. Тогда p + 2 = Г + b (в число граней включена одна неограниченная грань).

Например, рассмотрим граф куба:

Для него b = 8, p = 12, Г = 6 и p + 2 = 14 = b + Г.

Доказательство теоремы проведем индукцией по числу ребер p. Если p = 0, то b = 1 и Г = 1. Если p = 1, то граф имеет один из следующих видов (рис. 3):

В первом случае  -- p = 1, b = 2 и Г = 1; во втором  - p = 1, b = 1 и Г = 2. Ясно, что в каждом из этих случаев справедливо равенство p + 2 = b + Г. Если G содержит вершину α ∈ V степени 1, то удаляя α и инцидентное с ним ребро, мы получим опять связанный планарный граф G' = (V', E'), в котором
p' = p – 1, b'= b – 1, Г' = Г. По предположению индукции p' + 2 = (p – 1) + 2 = b' + Г' = (b-1) + Г или p + 2 = b + Г. Итак, можно считать, что для любой вершины α ∈ V p (α) ≥ 2. Докажем, что G содержит цикл. Пусть v1∈V и v2 - смежная вершина с v1. Если v1= v2, то получаем петлю.

Если v1≠ v2, то из неравенства p (v2) ≥2 следует, что существует вершина v3∈V, смежная с v2. Рассуждая аналогично, мы получим последовательность инцидентных вершин v1,  v2, v3, … Так как V <∞, то в этой последовательности встретится вершина vk, которая встречалась раньше. Выбирая k минимальным с этим свойством, мы получим цикл. Удалим в этом цикле одно ребро. Мы получим новый связный планарный граф G' = (V', E'), в котором  p' = p – 1, b'= b, Г' = Г – 1. По предположению индукции p' + 2 = (p – 1) + 2 = b' + Г' = b + (Г – 1) или p + 2 = b + Г. Теорема доказана.

Задача 1. Доказать, что для «хорошего» графа p = 3b – 6.

Указание. В «хорошем» графе все грани являются треугольными. Поэтому 3Г = 2p и Г = 23 p. Подставим это выражение в формулу Эйлера p + 2 = b + 23 p. Получим, что p3 = b – 2.

Задача 2. Внутри  треугольника взято m точек, которые соединены друг с другом и вершинами исходного треугольника так, что исходный треугольник разбился на меньшие треугольники с непересекающимися сторонами. Доказать, что число маленьких треугольников равно (2m + 1), т.е. не зависит от способа соединения.

Указание. Согласно предыдущей задаче p = 3b – 6 = 3(m + 3) – 6 = 3m + 3 и Г = (p + 2) – b = 3m + 5 – (m+3) = 2m +2. В нашем графе одна грань – внешняя. Поэтому искомое число треугольников равно (2m + 1).

Задачи на применение теории графов

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

Задача 1. Необходимо составить фрагмент расписания для одного дня с

учетом следующих обстоятельств:

1. учитель истории может дать либо первый, либо второй,
либо третий уроки, но только один урок;

2.      учитель литературы может дать один, либо второй, либо третий урок;

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

4.      преподаватель физкультуры согласен дать только последний урок.

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

Задача 2.  В составе экспедиции должно быть 6 специалистов: биолог,

врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A, B, C, D, E, F, G и  H. 

Обязанности биолога могут исполнять E и G,

врача – A и D, синоптика – F и G, гидролога – B и F, 

радиста – С и D, механика – C и H.

Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедиции, если F не может ехать без B, D – без  H и C,

C не может ехать вместе с G, A – вместе с B? 

 Решение Вершины графа могут соединяться не только линиями, но и стрелками. Такие члены экспедиции, которые не могут ехать без других, причем в определенном графе ребра называются ориентированными. В данном графе черными стрелками указаны члены, которые не могут ехать друг без друга, а розовыми стрелками(A-B, C-G) – члены экспедиции, которые не могут ехать совместно

В результате решения задачи получили следующий состав экспедиции:

Радист – С, врач – D, гидролог – В, синоптик – F, биолог – Е, механик – Н.

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

Решение. Пусть A и B –  данные города. Докажем сначала,

что из A в B можно было проехать до закрытия на ремонт двух

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

Пусть A' и  B' – проекции точек A и B, а M' и N' – крайние точки проекции многогранника (в точки  M' и N'  проецируются вершины M и N). Если идти из  вершины A так, что в проекции движение будет происходить по направлению от M' к N' , то, в конце концов, мы обязательно попадем в вершину N. Аналогично из вершины B можно пройти в  N. Таким образом, можно проехать из A в B (через N).

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

Приложение теории графов
в различных областях науки и техники 

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

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

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

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

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

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

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

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

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

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

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

Маршрутизация

Маршрутизация (англ. Routing) — процесс определения маршрута следования информации в сетях связи.

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

Статическими маршрутами могут быть:

• маршруты, не изменяющиеся во времени;
• маршруты, изменяющиеся по расписанию;
• маршруты, изменяющиеся по ситуации — административно в момент возникновения стандартной ситуации.

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

                Заключение

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

Список использованной литературы

1. Оре О. Теория графов : учеб. пособие / О. Оре. М.: Наука, 1968.
2. Ю.Н.Мальцев: «Реши, если силён».
3. Уилсон Р.: Введение в теорию графов: учеб. пособие / Р. Уилсон.
4. Хакари Ф.: Теория графов: / Ф. Хакари.  М.: Мир, 1973. 
5. Кормен Т. М.и др.: Часть VI. Алгоритмы для работы с графами: / Т. М. Кормен и др.
6. Салий В. Н., Богомолов А. М.: Алгебраические основы теории дискретных систем/  Салий В. Н., Богомолов А. М.
7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.

 Лекции по теории графов/  Емеличев В.А., Мельников О.И. и др.

8. Кирсанов М. Н. Графы в Maple/ Кирсанов М. Н. 
9. Википедия. [Электронный ресурс]  /http://ru.wikipedia.org/        
10.  Google. [Электронный ресурс] /http://www.google.ru/