Тема графов — это интересная, полезная и пугающая тема. Теория графов — "Ужас студента". Алгоритмы на графах — потрясающий ум людей их открывших.

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

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

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

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

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

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

В литературе, в интернете и вообще везде, где что-то написано о графах, вы будете встречать такие понятия, как дуги и ребра. На этом рисунке изображены ребра графа. Т.е. это три ребра Е1, Е2 и Е3.

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

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

Вы часто будете встречать понятия смежности и инцендентности. На рисунке красным цветом отмечены два ребра, которые идут в одну точку. Такие ребра, как и вышеописанные вершины, тоже называются смежными.

Многое не описано, но эта часть информации может быть кому-то поможет.

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

РЕФЕРАТ

«ТЕОРИЯ ГРАФОВ»

Выполнила:

Зудина Т.В.

Владимир 2001

1. Введение

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

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

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

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

6. Применение теории графов в школьном курсе математики

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

8. Последние достижения теории графов

§1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.

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

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

(РИСУНОК 1.1)

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

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

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

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

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

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

История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?

(РИСУНОК 1.2)

Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F , чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A .

В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ

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

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

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

(РИСУНОК 2.1)

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

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

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

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

(РИСУНОК 2.2)

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

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

(РИСУНОК 2.3)

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

Обозначение: p (A ) – степень вершины A . Например, на рисунке 2.1: p (A )=2, p (B )=2, p (C )=2, p (D )=1, p (E )=1.

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

На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.

(РИСУНОК 2.4 и 2.5)

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

На рисунке 2.6 изображен исходный граф G , состоящий из четырех вершин и трех отрезков, а на рисунке 2.7 – дополнение данного графа – граф G " .

(РИСУНОК 2.6 и 2.7)

Мы видим, что на рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах (этот вопрос будет рассмотрен подробно далее, в параграфе 5).

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

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

(РИСУНОК 2.8)

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

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 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. Сделать вывод.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение 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

риложение

Приложение

Назад Вперёд

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

Цели урока:

познакомить учащихся с понятием “Граф”, основными принципами его построения;

формировать умение выделять отношения, связывающие объекты;

развивать внимание, способность к логическому рассуждению;

воспитывать взаимопомощь, умение работать в коллективе

закрепление полученных знаний на практике

развитие памяти, внимания;

развитие самостоятельности;

воспитание познавательной активности.

Оборудование:

компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
оборудование доски (тема урока, новые термины). Раздаточный материал.

План урока.

II. Изложение нового материала. (10 мин.)

III. Закрепление материала. Практическая работа. (15-20 мин.)

IV. Подведение итога урока.(2 мин)

V. Домашнее задание.

I. Организационный момент. Актуализация знаний.

Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.

II Изложение нового материала.

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)

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

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

Граф – это некоторая информационная модель

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

Примеры графов (Слайд 4, 5, 6)

Задание 1 (Слайд 7):

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса?

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

Теперь сразу видно, что долететь с Земли до Марса нельзя.

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

Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?

Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?

Представление графов (Слайд 12)

Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.

Списки дуг

Графическая форма

Табличная форма

(АВ; 7),

	А	В	С
А			3
В			4
С	3	4

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

Задание 2 (Слайд 13)

IV. Итог урока

Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)

Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

Что обозначают ребра графа (Пути, движения, направления)

Приведите пример, где в жизни мы можем с ними встретиться?

Как изображаются графы?

V. Домашнее задание. (Слайд 15)

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

Что такое граф

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

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

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

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

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

Чаще всего рассматривают графы, ребра которых имеют один тип - являются ориентированными или нет.

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

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

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

Каждая вершина орграфа характеризуется:

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

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

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

Вершина со степенью 0 называется изолированной.

Висячей вершиной является вершина со степенью 1.

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

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

Графы: изоморфизм

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

Пути и циклы

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

Теория графов в программировании используется для построения граф-схем алгоритмов.

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

РЕФЕРАТ

Владимир 2001

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

Что такое граф

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

Графы: изоморфизм

Пути и циклы