Инфоурок / Математика / Другие методич. материалы / Теория графов
Обращаем Ваше внимание: Министерство образования и науки рекомендует в 2017/2018 учебном году включать в программы воспитания и социализации образовательные события, приуроченные к году экологии (2017 год объявлен годом экологии и особо охраняемых природных территорий в Российской Федерации).

Учителям 1-11 классов и воспитателям дошкольных ОУ вместе с ребятами рекомендуем принять участие в международном конкурсе «Я люблю природу», приуроченном к году экологии. Участники конкурса проверят свои знания правил поведения на природе, узнают интересные факты о животных и растениях, занесённых в Красную книгу России. Все ученики будут награждены красочными наградными материалами, а учителя получат бесплатные свидетельства о подготовке участников и призёров международного конкурса.

ПРИЁМ ЗАЯВОК ТОЛЬКО ДО 15 ДЕКАБРЯ!

Конкурс "Я люблю природу"

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

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

Только сейчас действует СКИДКА 50% для всех педагогов на все 111 курсов профессиональной переподготовки! Доступна рассрочка с первым взносом всего 10%, при этом цена курса не увеличивается из-за использования рассрочки!

ВЫБРАТЬ КУРС И ПОДАТЬ ЗАЯВКУ
библиотека
материалов


Федеральное Государственное образовательное учреждение высшего профессионального образования

«Мордовский государственный педагогический институт имени М.Е. Евсевьева»



Физико-математический факультет









Реферат

по теме:

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






Выполнила: студентка

группы МДМ-109

Добрынкина О.А.

Проверила: Лапина И.Э.








Саранск 2014


Содержание

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

1. Основные понятия теории графов………………………………………… 4

2. Примеры графов……………………………………………………………. 8

3. Эйлеровы графы…………………………………………………………… 13

4. Примеры приложений теории графов……………………………………. 16

5. Задача о кратчайшем пути………………………………………………… 18

6. Алгоритм нахождения максимального потока………………………….. 27

Заключение…………………………………………………………………… 38

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



Введение


В последнее время наблюдается неуклонное вторжение математических методов в различные отрасли науки и техники. Процесс математизации затронул и экономическую науку.

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

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

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

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



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


Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1).


hello_html_m78bd20f.png


Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).

Опр. 1. Задано конечное множество X, состоящее из n элементов (X = {1, 2,…, n}), называемых вершинами графа, и подмножество V декартова произведения X ×X, то есть hello_html_me242acc.gif, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V).

Опр. 2. Неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X.

Дугу между вершинами i и j, hello_html_m3c1169e8.gif, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (hello_html_m51e7a7a5.gif)).

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

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

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

Опр. 5.1. Простой путь – путь, в котором ни одна дуга не встречается дважды.

Опр. 5.2. Элементарный путь – путь, в котором ни одна вершина не встречается дважды.

Опр. 5.3. Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Опр. 5.4 Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Опр.6. Граф, для которого из (i, j) hello_html_m4030b337.gifV следует (j, i) hello_html_m4030b337.gif V называется симметрическим.

Опр. 7. Если из (i, j) hello_html_m4030b337.gifV следует, что (j, i) hello_html_m3fa72678.gifV, то соответствующий граф называется антисимметрическим.

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

Опр. 8.2. Цепь – последовательность смежных вершин.

Опр. 9. Замкнутая цепь называется циклом.

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

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

Опр. 11. Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.

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

Опр. 13. В неориентированном графе степенью вершины i называется число hello_html_36ccb852.gifинцидентных ей ребер. Очевидно,hello_html_m19912d3c.gif. Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Опр. 14. Вершина, для которой не существует инцидентных ей ребер (hello_html_36ccb852.gif= 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро (hello_html_36ccb852.gif = 1) называется висячей.

Опр. 15. Определим матрицу смежности графа как квадратную матрицу n ×n, элемент hello_html_m95a6b4c.gif которой равен единице, если (i, j)hello_html_m4030b337.gif V, и нулю, если (i, j)hello_html_m3fa72678.gif V, i, jhello_html_m4030b337.gifX. Для неориентированного графа матрица смежности всегда симметрическая.

Опр. 16. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n×m, элемент hello_html_1072425c.gif которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = 1, n, j = 1, m.

Опр. 17. Матрица инциденций для дуг графа – прямоугольная матрицу m xn, элемент rij которой равен плюс единице, если дуга hello_html_m3a4e90d8.gifисходит из вершины i, минус единице, если дуга hello_html_m3a4e90d8.gif заходит в вершину i, и нулю в остальных случаях, i = 1, n, j = 1, m

Опр. 18. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно hello_html_697655d7.gif Легко показать, что в дереве любые две вершины связаны единственной цепью.

Опр. 19. Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице.

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

Опр. 21. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).

Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G*, определяемый следующим образом: каждой грани графа G соответствует вершина графа G*, каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V* графа G*, соединяющее соответствующие граням z1 и z2 вершины.













2. Примеры графов


Вполне несвязные графы. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через Nn; N4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.



hello_html_6acf3b6c.png


Полные графы. Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через hello_html_53b92307.gif. Графы hello_html_6b4135b8.gif и hello_html_m3c341967.gif изображены на рис. 2 и 3. hello_html_53b92307.gifимеет ровно n (n – 1)/2 ребер.


hello_html_40e3495a.png


Регулярные графы. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф Кn – регулярным степени n – 1.



hello_html_49402d3a.pnghello_html_m60fd6f71.png


Платоновы графы. Среди регулярных графов особенно интересны так называемые Платоновы графы – графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф hello_html_6b4135b8.gif соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;


hello_html_m38e5dce7.png


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


hello_html_m1c01101e.png


тогда G называется двудольным графом. Такие графы иногда обозначают G(V1,V2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому – в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой – синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается hello_html_m6a56f648.gifhello_html_41671615.gifгде m, n – число вершин соответственно в V1 и V2. Например, на рис. 8 изображен граф K4,3. Заметим, что граф hello_html_m6a56f648.gif имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида hello_html_4d7f3379.gif называется звездным графом; на рис. 9 изображен звездный граф hello_html_m4a0db72b.gif.


hello_html_64fdc395.pnghello_html_m195e2823.png


Связные графы. Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности) графа G. (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

hello_html_m5202fa0d.png


Циклические графы и колеса. Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф. с п вершинами обозначается через Сn. Соединение графов hello_html_6437539b.gifи hello_html_41671615.gif (п ≥ 3) называется колесом с п вершинами и обозначается Wn. На рис. 11 изображены С6 и W6; граф W4 уже появлялся на рис. 2.


hello_html_m5f23cb0b.png















3. Эйлеровы графы


Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На рис. 13,14,15 изображены соответственно не эйлеров, полуэилеров и эйлеров графы.



hello_html_m7ed4ff0.pnghello_html_m30e2d8aa.png


Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рис. 15, эйлерову цепь (не имеет). Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым

Докажем простую лемму.

Лемма 1. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G; построим по индукции маршрут hello_html_m6b38d8e9.gifhello_html_m6b38d8e9.gif, выбирая вершину v1 смежной вершине v, а для i≥1 – выбирая vi+1 смежной vi и отличной от vi-1 (существование такой вершины vi+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая уже была выбрана раньше. Предположим, что vk – первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями vh, и является требуемым циклом.


hello_html_7a4956fa.png


Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четную степень.

Доказательство. hello_html_300113d7.gif Предположим, что Р является эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Р через любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Р ровно один раз, то каждая вершина должна иметь четную степень.


hello_html_m51bcf463.png


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

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

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




















4. Примеры приложений теории графов


1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

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

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

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

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

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












5. Задача о кратчайшем пути


Пример 1. Задача о волке, козе и капусте. Коза, капуста и волк находятся на берегу реки; перевозчику надо переправить их через реку, но его лодка так мала, что он может взять с собой не более одною из этих трех «пассажиров». По очевидным причинам нельзя оставлять без надзора волка с козой, а козу с капустой. Как должен поступить перевозчик?

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


hello_html_m245db5bc.png


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

Задача о кратчайшем пути

Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг

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

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

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. Легко показать, что в сети без контуров всегда существует правильная нумерация.

Обозначим hello_html_4378c3a6.gifhello_html_mec66d94.gif – длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

Шаг 0: Помечаем нулевую вершину индексом hello_html_38fbc454.gif;

Шаг k: помечаем вершину k индексом hello_html_67c85190.gifi<k;

Индекс выхода hello_html_4378c3a6.gif будет равен длине кратчайшего пути. (Алгоритм 1 для задач динамического программирования отражает принцип оптимальности Беллмана: если ищется кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути также должна быть минимальна.) На рисунке 2 приведен пример применения алгоритма 1 для определения кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).

Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь hello_html_m6132bd78.gif, такой, что hello_html_7bddf67e.gifи т.д.


hello_html_mf3eed42.png

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом hello_html_38fbc454.gif, все остальные вершины индексами hello_html_26851765.gif, i = 1, n;

Шаг k: Рассматриваем все дуги. Если для дуги (i; j) hello_html_34d63227.gif>hello_html_mec66d94.gif, то вычисляем новое значение hello_html_a4fcb75.gif;

Индексы устанавливаются за конечное число шагов. Обозначим hello_html_m6af92f91.gif- установившиеся значения индексов, которые обладают следующим свойством: величина hello_html_32690b6a.gif равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

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

Алгоритм 3.

Шаг 0: Помечаем нулевую вершину индексом hello_html_38fbc454.gif;

Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q – множество непомеченных вершин, смежных с помеченными. Для каждой вершины hello_html_43b011b9.gif вычисляем величину hello_html_a8bef3f.gif где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина hello_html_61e8dec4.gif минимальна, индексом hello_html_11434354.gif.

Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n. Длина кратчайшего пути равна hello_html_4378c3a6.gif, а сам кратчайший путь определяется так, как это было описано выше.

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

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

Пример 1.


hello_html_m39bc50f8.png

Рис. 3. Исходные данные к задаче о кратчайшем пути.


Ситуацию можно описать не только ориентированным графом, но и таблицей (табл. 1).


Табл.1. Исходные данные к задаче о кратчайшем пути

Начало дуги

Конец дуги

Время в пути

1

2

7

1

3

1

2

4

4

2

6

1

3

2

5

3

5

2

3

6

3

5

2

2

5

4

5

6

5

3


Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С (Т) – длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С (4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис. 3 и в табл. 1, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3)=1. Кроме того, очевидно, что С(1)=0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена реструктуризация задачи – нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) – положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4): С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков: 1 → 3 → 5 → 4.

Задача о кратчайшем пути для конкретных исходных данных (рис. 3и табл. 1) полностью решена.

Пример 2.

Найти кратчайший путь (длина пути) из Академгородка (остановка Цветной проезд) до железнодорожного вокзала.

Остановки:

  1. цветной проезд

  2. дом быта

3,3'- институт ядерной физики

4 Баня №22

5 Речной вокзал

6 – Сеятель

7 – кафе «Огонек»

8 – Мост

9 – Главный Вокзал

Найти кратчайший путь из вершины 1 в вершины 9.

Исходные данные:



hello_html_m2b947568.png

Рис. 4


Табл. 2

Начало дуги

Конец дуги

Длина пути (км.)

1

2

3

1

3

1,7

1

3'

3,06

1

4

10,9

1

5

26,78

2

6

0,5

3

7

7,6

3'

7

7,6

4

8

21,57

5

8

4,26

5

9

4,35

6

9

25

7

5

19

8

9

2,55


Решение: С (Т) – длина кратчайшего пути из вершины 1 в вершину Т. Нам необходимо найти С(9).

С(1)=0, С(2)=3 (в вершину 2 входит только одна стрелка, ее длина равна 3).

В вершину 9 можно попасть из вершины 5, пройдя путь 4,35, из вершины 6, пройдя путь 25 и из вершины 8, пройдя путь 2,55.

Следовательно, С(9) = min {С(5) + 4,35; С(6) + 25; С(8) + 2,55}

Таким образом необходимо найти С(5), С(6), С(8).

В вершину 5 можно попасть из вершины 1, пройдя путь 26,78, либо из вершины 7, пройдя путь 19

С(5) = min {С(1) + 26,78; С(7) + 19}

Необходимо найти С(7). В вершину 7 можно попасть из вершины 3, пройдя путь 7,6 и из 3' пройдя 7,6.

С(7) = min {С(3) + 7,6; С(3') + 7,6}= min {1,7+7,6; 3,06+7,6}=9,3

С(5) = min {26,78; 9,3+ 19}=26,78

В вершину 6 можно попасть из вершины 2, пройдя путь равный 0,5

С(6)=С(2)+0,5=3+0,5=3,5

В вершину 8 можно попасть из вершины 4, пройдя путь 21,57 и из вершины 5, пройдя путь 4,62.

С(8) = min {С(4) + 21,57; С(5) + 4,26}

С(4)=10,9 (из условия).

С(8) = min {10,09+ 21,57; 26,78 + 4,26}=31,4

Следовательно

С(9)= min {26,78+4,35; 3,5+25; 31,4+2,55}= min {31,13; 28,5; 33,95}=28,5

Таким образом, длина кратчайшего пути равна 28,5 км.

Кратчайший путь: 1 → 2 → 6 → 9.











6. Алгоритм нахождения максимального потока


Идея этого алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро (i, j) с (начальной) пропускной способностью hello_html_m7ec4bf8f.gif. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись hello_html_m1973a1c4.gif- остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j, получающего поток из узла i, определим меткуhello_html_m766f88cb.gif, где hello_html_m1fb7b816.gif- величина потока, протекающего от j узла к узлу i. Чтобы найти максимальный поток, выполняем следующие действия.

Этап 1.

Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем hello_html_m7ec4bf8f.gif=hello_html_m1973a1c4.gif. Назначим hello_html_m1e56ee34.gif и пометим узел 1 меткой. Полагаем i=1.

Этап 2.

hello_html_m6d49c4a6.gif- множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью hello_html_m68abfbcf.gif>0 для всех jhello_html_m4030b337.gifhello_html_m6d49c4a6.gif. Если hello_html_m26056e02.gif, выполняем 3 этап, в противном случае переходим к 4.

Этап 3.

В hello_html_m6d49c4a6.gif находим узел k, такой, что hello_html_m71925beb.gif. Положим hello_html_m76094a22.gifhello_html_m71eeb77a.gif и пометим узел k меткой hello_html_51f7679.gif. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.

Этап 4.

Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если hello_html_178e0b03.gif, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.

Этап 5.

Определение остаточной сетиhello_html_m74c74c8b.gif. Обозначим через множество узлов, через которые проходит p й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n).тогда максимальный поток, проходящий по этому пути hello_html_m2e6fd70f.gif

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

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

1) hello_html_30531057.gif, если поток идет от узла i к j,

2) hello_html_m4e698942.gif, если поток идет от узла j к i.

Далее восстанавливаем все узлы, удаленные в 4 п. полагаем i=1 и возвращаемся ко второму этапу для поиска нового сквозного пути.

Этап 6.

Решение.

а) при m найденных сквозных путях максимальный поток выражается

hello_html_m1cd2ef99.gif

б) Имея значения начальных hello_html_m7ec4bf8f.gif и конечных hello_html_m1973a1c4.gif пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим hello_html_57950238.gif. Если hello_html_m42a4bdb1.gif>0, поток, проходящий через ребро (i, j) равен hello_html_m42a4bdb1.gif. Если hello_html_m166d899e.gif>0, тогда поток равен hello_html_m166d899e.gif. (случай, когда одновременно hello_html_m42a4bdb1.gif>0 и hello_html_m166d899e.gif>0, невозможен).

Пример 1. Найти максимальный поток в сети рис. 1


hello_html_m5497d0b1.png


Итерация 1. hello_html_m7ec4bf8f.gif=hello_html_m1973a1c4.gif

1) hello_html_m1e56ee34.gif и помечаем узел 1 меткой hello_html_m518888f2.gif. i=1

2) hello_html_2f710dde.gifhello_html_m18c42267.gif

3) k=3, так как hello_html_m73492280.gif. Назначаем hello_html_7de1ca1c.gif и помечаем узел 3 меткой hello_html_m623eb772.gif. i=3 и возвращаемся к 2)

4) hello_html_m150898be.gif

5) k=5 и hello_html_m25269d87.gif. Помечаем узел 5 меткой hello_html_4a07421d.gif. Получаем сквозной путь.

6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: hello_html_m2da783f6.gif. hello_html_m6f1c5b28.gif и hello_html_m6c475fcb.gif. Вычисляем остаточные пропускные способности вдоль пути hello_html_6437539b.gif:

hello_html_m4554b69b.gif

hello_html_361f1be7.gif

Итерация 2.

1) hello_html_m1e56ee34.gif и помечаем узел 1 меткой hello_html_m518888f2.gif. i=1

2)hello_html_8673492.gif

3) k=2, hello_html_31c62ec1.gif и помечаем узел 2 меткой hello_html_mc4adbfa.gif. i=2 и возвращаемся к 2)

2') hello_html_mcc44a28.gif

3') k=3 и hello_html_40044070.gif. Помечаем узел 3 меткой hello_html_m3d1e032e.gif. i=3 и возвращаемся к 2)

2») hello_html_m6f3c02b7.gif(hello_html_m4d41c514.gif, поэтому узел 5 не включается в hello_html_284c0df0.gif

3») k=4, hello_html_m6ccfddb0.gif и помечаем узел 4 меткой hello_html_m63344d20.gif. i=4 и возвращаемся к 2)

2''') hello_html_m5d5d9795.gif(так как узлы 1 и 3 помечены, они не включаются в hello_html_50563996.gif)

3''') k=5 и hello_html_ea7ea4d.gif. Помечаем узел 5 меткой hello_html_eb38a01.gif. Получен сквозной путь. Переходим к 5)

5)hello_html_6e8075f.gif и hello_html_m739beae0.gif. Вычисляем остаточные пропускные способности вдоль пути hello_html_m3d05f0cd.gif:

hello_html_5055aaf3.gif

hello_html_m4779626e.gif

hello_html_70b3a0fd.gif

hello_html_2f710dde.gif

Итерация 3.

1) hello_html_m1e56ee34.gif и помечаем узел 1 меткой hello_html_m518888f2.gif. i=1

2) hello_html_8673492.gif

3) k=2, hello_html_m400ddc15.gifhello_html_358a00d8.gif и помечаем узел 2 меткойhello_html_m751df014.gif. i=2 и возвращаемся к 2)

2') hello_html_mcc44a28.gif

3') k=3 и hello_html_m367aaae1.gif. Помечаем узел 3 меткой hello_html_3e6723ad.gif. i=3 и возвращаемся к 2)

2») hello_html_m686e9923.gif(так как hello_html_m3500a889.gif) переходим к 4)

4) метка hello_html_3e6723ad.gif узла 3 показывает номер предшествующего узла hello_html_5141918f.gif. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. hello_html_41415f64.gifи возвращаемся к 2)

2''') hello_html_m5d5d9795.gif (так как узел 3 удален из возможного сквозного пути)

3''') hello_html_33986e48.gif и hello_html_6441e7f.gif. Помечаем узел 5 меткой hello_html_3e6723ad.gif. Получен сквозной путь. Переходим к 5)

5) hello_html_m26753c5d.gif и hello_html_mbefbd5d.gif. Вычисляем остаточные пропускные способности вдоль пути hello_html_290a10d4.gif:

hello_html_m3b12dc55.gif

hello_html_3e875cef.gif

Итерация 4. на этой итерации получен путь hello_html_m28deae42.gif с hello_html_274e7569.gif

Итерация 5. на этой итерации получен путь hello_html_m10fd91e6.gif с hello_html_3e2e6b80.gif

Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения

6) максимальный объем потока в сети равен hello_html_6345035a.gif единиц.

Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей hello_html_m1973a1c4.gif из первоначальных значений пропускных способностей hello_html_m7ec4bf8f.gif.

Результаты вычислений: табл. 1


ребро

hello_html_m7ec4bf8f.gif-hello_html_m1973a1c4.gif

Величина потока

направление

(1,2)

(20,0) – (0,20)=(20, – 20)

20

1hello_html_m400ddc15.gif2

(1,3)

(30,0) – (0,30)=(30, – 30)

30

1hello_html_m400ddc15.gif3

(1,4)

(10,0) – (0,10)=(10, – 10)

10

1hello_html_m400ddc15.gif4

(2,3)

(40,0) – (40,0)=(0,0)

0

-

(2,5)

(30,0) – (10,20)=(20, – 20)

20

2hello_html_m400ddc15.gif5

(3,4)

(10,5) – (0,15)=(10, – 10)

10

3hello_html_m400ddc15.gif4

(3,5)

(20,0) – (0,20)=(20, – 20)

20

3hello_html_m400ddc15.gif5

(4,5)

(20,0) – (0,20)=(20, – 20)

20

4hello_html_m400ddc15.gif5


Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)


hello_html_52319922.gifhello_html_m6bcf34bc.gif

а) hello_html_3e2e6b80.gifhello_html_m46af0ea9.gif б) hello_html_m340c02de.gif


hello_html_1848a9e7.gifhello_html_m388403d6.gif


в) hello_html_m4654f015.gif г) hello_html_274e7569.gif


hello_html_m24c35b52.gifhello_html_4b29f976.gif


д) hello_html_3e2e6b80.gif е) Сквозных путей нет

Пример 2.


hello_html_96b9cfc.png

Рис. 2. Исходные данные к примеру 2


Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).


Табл.2. Исходные данные к задаче о максимальном потоке

Пункт отправления

Пункт назначения

Пропускная способность

0

1

2

0

2

3

0

3

1

1

2

4

1

3

1

1

4

3

2

3

1

2

4

2

3

4

2


Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу – в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы – 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 – по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)

Табл.3. Решение задачи о максимальном потоке

Пункт отправления

Пункт назначения

План перевозок

Пропускная способность

0

1

2

2

0

2

3

3

0

3

1

1

1

2

0

4

1

3

0

1

1

4

2

3

2

3

1

1

2

4

2

2

3

4

2

2


Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM, а именно, Х01, Х02, Х03, Х12, Х13, Х14, Х23, Х24, Х34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max,

Х01 + Х02 + Х03 = F (0)

– Х01 + Х12 + Х13 + Х14 = 0 (1)

– Х02 - Х12 + Х23 + Х24 = 0 (2)

– Х03 - Х13 - Х23 + Х34 = 0 (3)

– Х14 - Х24 - Х34 = – F (4)

Х01 ≤ 2

Х02 ≤ 3

Х03 ≤ 1

Х12 ≤ 4

Х13 ≤ 1

Х14 ≤ 3

Х23 ≤ 1

Х24 ≤ 2

Х34 ≤ 2

ХКМ ≥ 0, К, М = 0, 1, 2, 3, 4

F ≥ 0.

Здесь F – целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) – (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) – это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию – через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).



Заключение


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

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

Так же была составлен и решен пример о кратчайшем пути непосредственно, касающийся нашей повседневной жизни. Задача состояла в отыскании кратчайшего пути (длинны дороги в км.) от Академгородка (остановка Цветной проезд) до Вокзала Главного.



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

  1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

  2. «В помощь учителю математики», Йошкар-Ола, 1972 ст. "Изучение элементов теории графов"

  3. Берж, К.С .Теория графов и ее применение./К. С. Берж.- М.: ИЛ, 2007.-178с.

  4. Бурков, В.Н. Элементы теории графов./В. Н. Бурков. – М.: Просвещение,2010.-352с.

  5. Гарднер, М. С"Математические досуги". / М. С. Гарднер.- М. :"Мир",2004.-347с.

  6. Гарднер , М. С."Математические головоломки и развлечения"./ М С гарднер .-М. :"Мир",2005.-221с.

  7. Зыков, А. А. Теория конечных графов./ А. А. Зыков.- Новосибирск: "Наука",2006.-257с.

  8. Касаткин, В. Н. "Необычные задачи математики"./ В. Н. Касаткин .-Киев: "Радяньска школа", 2007.-232с.

  9. Олехник, С. Н. "Старинные занимательные задачи"./ C.Н. Олехник.- М. "Наука",2008.-431с.

  10. . Оре, О. С."Графы и их применения"./О. С. Оре.- М.:"Мир", 2005-269с.

  11. Реньи, А . Н."Трилогия о математике"./ А. Н. Реньи.- М.:"Мир",2010-198с.

  12. http://ru.wikipedia.org

  13. http://www.xumuk.ru

  14. http://www.seznaika.ru

  15. http://lib.repetitors.eu




Краткое описание документа:

Опр. 4. Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам. Опр.5. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Опр. 5.1. Простой путь – путь, в котором ни одна дуга не встречается дважды. Опр. 5.2. Элементарный путь – путь, в котором ни одна вершина не встречается дважды. Опр. 5.3. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Опр. 5.4 Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы). Опр.6. Граф, для которого из (i, j) V следует (j, i)  V называется симметрическим. Опр. 7. Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметрическим. Опр. 8.1. Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Опр. 8.2. Цепь – последовательность смежных вершин. Опр. 9. Замкнутая цепь называется циклом. Опр. 10.1. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно – циклом, путем, контуром). Опр. 10.2. Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно – циклом, путем, контуром). Опр. 11. Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Опр. 12. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом. Опр. 13. В неориентированном графе степенью вершины i называется число инцидентных ей ребер. Очевидно,. Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которого равны, называется однородным. Опр. 14. Вершина, для которой не существует инцидентных ей ребер (= 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро ( = 1) называется висячей. Опр. 15. Определим матрицу смежности графа как квадратную матрицу n ×n, элемент  которой равен единице, если (i, j) V, и нулю, если (i, j) V, i, jX. Для неориентированного графа матрица смежности всегда симметрическая. Опр. 16. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n×m, элемент  которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = 1, n, j = 1, m. Опр. 17. Матрица инциденций для дуг графа – прямоугольная матрицу m xn, элемент rij которой равен плюс единице, если дуга исходит из вершины i, минус единице, если дуга  заходит в вершину i, и нулю в остальных случаях, i = 1, n, j = 1, m Опр. 18. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно  Легко показать, что в дереве любые две вершины связаны единственной цепью. Опр. 19. Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице. Опр. 20. Плоским (планарным) называется граф, который можно изобразить на плоскости так, что различным вершинам соответствуют различные кружки и никакие два ребра не имеют общих точек, отличных от их границ (не пересекаются). Для плоского графа существует понятие грани – части плоскости, ограниченной ребрами и не содержащей внутри себя ни вершин, ни ребер. Опр. 21. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды). Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G*, определяемый следующим образом: каждой грани графа G соответствует вершина графа G*, каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V* графа G*, соединяющее соответствующие граням z1 и z2 вершины.  

Общая информация

Номер материала: 103107051304

Похожие материалы