Федеральное Государственное образовательное учреждение высшего профессионального образования
«Мордовский государственный педагогический институт имени М.Е. Евсевьева»
Физико-математический факультет
Реферат
по теме:
«Теория графов »
Выполнила: студентка
группы МДМ-109
Добрынкина О.А.
Проверила: Лапина И.Э.
Саранск 2014
Введение………………………………………………………………………. 3
1. Основные понятия теории графов………………………………………… 4
2. Примеры графов……………………………………………………………. 8
3. Эйлеровы графы…………………………………………………………… 13
4. Примеры приложений теории графов……………………………………. 16
5. Задача о кратчайшем пути………………………………………………… 18
6. Алгоритм нахождения максимального потока………………………….. 27
Заключение…………………………………………………………………… 38
Список литературы…………………………………………………………… 39
Введение
В последнее время наблюдается неуклонное вторжение математических методов в различные отрасли науки и техники. Процесс математизации затронул и экономическую науку.
Понятие графа, само по себе очень простое, оказалось весьма плодотворным в науке и часто употребляемым. Теория графов изучает графы как абстрактные математические образования, независимо от их конкретных истолкований, а полученные общие результаты затем прилагаются к самым различным дисциплинам.
Термин «граф» приобрел право гражданства и вошел в математический язык в 1936 г., после выхода в свет монографии Кёнига, в которой впервые графы изучаются как самостоятельные математические объекты независимо от их содержания.
Изучение графов актуально и на сегодняшний день. Найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут – все это примеры из нашей повседневной жизни. Эти и многие другие задачи могут быть решены при помощи графов.
В данной работе излагается ряд основных понятий, так же приведены примеры приложений теории графов и рассмотрены два подхода к решению экономических задач на основе теории графов.
1. Основные понятия теории графов
Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1).
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).
Опр. 1. Задано конечное множество X
, состоящее из n
элементов (X =
{1, 2,…, n
}), называемых вершинами графа, и подмножество V декартова произведения X ×X, то есть 
, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V).
Опр. 2. Неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X.
Дугу между вершинами i и j, 
, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (
)).
Опр. 3. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный граф.
Опр. 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 x
n, элемент 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 вершины.
2. Примеры графов
Вполне несвязные графы . Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через N n ; N 4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.
Полные графы
. Простой граф, в котором любые две вершины смежны, называется полным графом.
Полный граф с n
вершинами обычно обозначается через 
. Графы 
и 
изображены на рис. 2 и 3. имеет ровно n
(n
– 1)/2 ребер.
Регулярные графы . Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r , то граф называется регулярным степени r . Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф К n – регулярным степени n – 1.
Платоновы графы
. Среди регулярных графов особенно интересны так называемые Платоновы графы – графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;
Двудольные графы . Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V 1 и V 2 так, что каждое ребро в G соединяет какую-нибудь вершину из V 1 с какой-либо вершиной из V 2 (рис. 7);
тогда G
называется двудольным графом. Такие графы иногда обозначают G
(V
1, V
2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому – в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой – синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V
1 соединена с каждой вершиной из V
2 ; если же это так и если при этом граф G
простой, то он называется полным двудольным графом
и обычно обозначается 
где m
, n
– число вершин соответственно в V
1 и V
2 . Например, на рис. 8 изображен граф K
4 , 3 . Заметим, что граф имеет ровно m
+ n
вершин и mn
ребер. Полный двудольный граф вида 
называется звездным графом; на рис. 9 изображен звездный граф 
.
Связные графы . Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности) графа G . (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.
Циклические графы и колеса
. Связный регулярный граф степени 2 называется циклическим графом
(или циклом);
циклический граф. с п
вершинами обозначается через С n
. Соединение графов 
и (п
≥ 3) называется колесом
с п
вершинами и обозначается W
n
.
На рис. 11 изображены С
6
и W
6
;
граф W
4
уже появлялся на рис. 2.
3. Эйлеровы графы
Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На рис. 13,14,15 изображены соответственно не эйлеров, полуэилеров и эйлеров графы.
Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рис. 15, эйлерову цепь (не имеет). Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым
Докажем простую лемму.
Лемма 1. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.
Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G ; построим по индукции маршрут , выбирая вершину v 1 смежной вершине v , а для i ≥1 – выбирая v i +1 смежной v i и отличной от v i -1 (существование такой вершины v i +1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая уже была выбрана раньше. Предположим, что v k – первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями v h , и является требуемым циклом.
Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четную степень.
Доказательство. 
Предположим, что Р является эйлеровой цепью в графе G
. Тогда при всяком прохождении цепи Р через любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Р ровно один раз, то каждая вершина должна иметь четную степень.
Проведем доказательство индукцией по числу ребер в G . В силу связности G , степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл С. Если С проходит через каждое ребро графа G , то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф Н. Число ребер в Н меньше, чем в G , и любая вершина в Н по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G , каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа Н, затем следуем по эйлеровой цепи той компоненты в Н, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа Н, и т.д.; заканчивается процесс тогда, когда мы попадаем обратно в начальную вершину (рис. 17).
Следствие 1. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.
Следствие 2. Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.
4. Примеры приложений теории графов
1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.
2. «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.
3. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями
4. Управление проектами. (Управление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений.)). С точки зрения теории графов проект – совокупность операций и зависимостей между ними. Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени проекта, затрат, и др.).
5. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности, взаимодействия и др.
6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами – связи (информационные, управляющие, технологические и др.) между ними.
5. Задача о кратчайшем пути
Пример 1. Задача о волке, козе и капусте. Коза, капуста и волк находятся на берегу реки; перевозчику надо переправить их через реку, но его лодка так мала, что он может взять с собой не более одною из этих трех «пассажиров». По очевидным причинам нельзя оставлять без надзора волка с козой, а козу с капустой. Как должен поступить перевозчик?
Эта широко известная задача легко решается в уме благодаря малому числу вариантов, подлежащих рассмотрению, тем не менее перед нами типичный пример задачи, о нахождении кратчайшего пути: чертится граф изображенный на рис 1 и ищется путь, ведущий из положения а (когда коза К, капуста Кап, волк В и перевозчик П находятся на правом берегу) в положение b (когда все переправлены на левый берег), искомый путь показан на рисунке жирными линиями.
В более общем случае необходим систематический алгоритм, изложим несколько методов.
Задача о кратчайшем пути
Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг
(если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.
Для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.
Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. Легко показать, что в сети без контуров всегда существует правильная нумерация.
Обозначим 
– длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.
Алгоритм 1.
;
Шаг k: помечаем вершину k индексом Индекс выхода Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь Следующий алгоритм дает возможность определять кратчайший путь в общем случае (то есть при произвольной нумерации вершин).
Алгоритм 2 (алгоритм Форда).
Шаг 0: Помечаем нулевую вершину индексом Шаг k: Рассматриваем все дуги. Если для дуги (i; j) Индексы устанавливаются за конечное число шагов. Обозначим Если длины всех дуг неотрицательны, то для поиска кратчайшего пути применим следующий алгоритм.
Алгоритм 3.
Шаг 0: Помечаем нулевую вершину индексом Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q – множество непомеченных вершин, смежных с помеченными. Для каждой вершины Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n. Длина кратчайшего пути равна Аналогично задаче о кратчайшем пути формулируется и решается задача о максимальном (длиннейшем) пути – достаточно изменить знаки дуг на противоположные и решить задачу о кратчайшем пути. Для существования решения задачи о максимальном пути необходимо и достаточно отсутствия контуров положительной длины.
В задаче поиска пути максимальной надежности длины дуг интерпретируются, например, как вероятности того, что существует связь между соответствующими двумя пунктами. Заменяя длины дуг их логарифмами, взятыми с обратными знаками, получаем, что путь максимальной надежности в исходном графе будет соответствовать кратчайшему пути в новом графе.
Пример 1.
Рис. 3. Исходные данные к задаче о кратчайшем пути.
Ситуацию можно описать не только ориентированным графом, но и таблицей (табл. 1).
Табл.1. Исходные данные к задаче о кратчайшем пути
Начало дуги
Конец дуги
Время в пути
Спрашивается в задаче: как кратчайшим путем попасть из вершины 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.
Найти кратчайший путь (длина пути) из Академгородка (остановка Цветной проезд) до железнодорожного вокзала.
Остановки:
цветной проезд
дом быта
3,3"- институт ядерной физики
4 Баня №22
5 Речной вокзал
6 – Сеятель
7 – кафе «Огонек»
8 – Мост
9 – Главный Вокзал
Найти кратчайший путь из вершины 1 в вершины 9.
Исходные данные:
Рис. 4
Табл. 2
Начало дуги
Конец дуги
Длина пути (км.)
3,06
10,9
26,78
21,57
4,26
4,35
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
) с (начальной) пропускной способностью Для произвольного узла j
, получающего поток из узла i
, определим метку Этап 1.
Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем Этап 2.
Этап 3.
В Этап 4.
Откат назад. Если i
=1, сквозной путь не возможен, и переходим к 6. Если Этап 5.
Определение остаточной сети Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину Т.о. для ребра (i
, j
), входящего в сквозной путь, текущие остаточные пропускные способности изменяются:
1) 2) Этап 6.
Решение.
а) при m
найденных сквозных путях максимальный поток выражается
б) Имея значения начальных Пример 1. Найти максимальный поток в сети рис. 1
Итерация 1. 1) 2) 3) k
=3, так как . Назначаем 4) 5) k
=5 и . Помечаем узел 5 меткой 6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . Итерация 2.
1) 2) 3) k
=2, и помечаем узел 2 меткой 2") 3") k
=3 и 2») 3») k
=4, 2""") 3""") k
=5 и 5) Итерация 3.
1) 2) 3) k
=2, 2") Рис. 2. Исходные данные к примеру 2
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).
Табл.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. Решение задачи о максимальном потоке
Пункт отправления
Пункт назначения
План перевозок
Пропускная способность
Задача линейного программирования при максимизации потока.
Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х 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)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию – через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).
Заключение
В данной работе мы рассмотрели необходимый минимум понятий, которые позволяют нам продолжить изучение теории графов. Ведь мы затронули лишь вершину огромного айсберга, разобрав пару подходов к решению экономических задач. Теория графов не ограничивается изучением каких-то отдельных явлений или процессов, она находит применение в самых разнообразных областях науки и техники.
Были рассмотрены алгоритмы решения задачи о кратчайшем пути и нахождения максимального потока, разобраны примеры. На их примере была показана значимость теории графов для оптимизации экономических задач.
Так же была составлен и решен пример о кратчайшем пути непосредственно, касающийся нашей повседневной жизни. Задача состояла в отыскании кратчайшего пути (длинны дороги в км.) от Академгородка (остановка Цветной проезд) до Вокзала Главного.
Список литературы
"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");
«В помощь учителю математики», Йошкар-Ола, 1972 ст. "Изучение элементов теории графов"
Берж, К.С.Теория графов и ее применение./К. С. Берж.- М.: ИЛ, 2007.-178с.
Бурков, В.Н. Элементы теории графов./В. Н. Бурков. – М.: Просвещение,2010.-352с.
Гарднер, М. С"Математические досуги". / М. С. Гарднер.- М. :"Мир",2004.-347с.
Гарднер, М. С."Математические головоломки и развлечения"./ М С гарднер.-М. :"Мир",2005.-221с.
Зыков, А. А. Теория конечных графов./ А. А. Зыков.- Новосибирск: "Наука",2006.-257с.
Касаткин, В. Н. "Необычные задачи математики"./ В. Н. Касаткин.-Киев: "Радяньска школа", 2007.-232с.
Олехник, С. Н. "Старинные занимательные задачи"./ C
.Н. Олехник.- М. "Наука",2008.-431с.
Оре, О. С."Графы и их применения"./О. С. Оре.- М.:"Мир", 2005-269с.
Реньи, А. Н."Трилогия о математике"./ А. Н. Реньи.- М.:"Мир",2010-198с.
Помните задачу из детства - необходимо нарисовать открытый конверт, не отрывая карандаша от бумаги, и не проходя дважды по любой из сторон? Вариантов немного, поэтому, после небольшого числа попыток («2-3-4-2-1-5-4-1-ой?!», «4-2-1-5-4-3-5-ой?!») любой ребёнок находил верное решение. А нужно всего лишь начинать рисование либо с точки 1, либо с точки 5. После этого движение в любом направлении в итоге приводило к решению задачи. Что же особенного в этих двух точках, первой и пятой? Что позволяет им становиться гарантом успешного решения? Всего лишь «нужное» для решения задачи число сходящихся в каждой из этих особенных точек числе сторон, а именно - нечётное количество! Действительно, в точках 1 и 5 сходится по 3 стороны, в 2 и 4 - по 4, а во второй - 2. В терминах теории графов (именно эта дисциплина с лёгкость решает задачу) это требование к «открытому конверту» звучит так: Если необходимо найти путь в связанном графе, содержащий все его ребра по одному разу, в котором начальная и конечная вершины не совпадают, необходимо и достаточно, чтобы начальная и конечная вершины были единственными вершинами с нечетными степенями. Зная это, становится понятным, что нарисовать «закрытый конверт» при тех же требованиях задачи не представляется возможным-все вершины имеют нечётную степень. И любое подтрунивание над одноклассником - что, мол, слабо? - рассчитано на неосведомлённость последнего в теории графов! Теория графов является большим и хорошо проработанным разделом дискретной математики
.Кроме этого дискретная математика объединяет такие дисциплины как математическая логика, математическая кибернетика, теория функциональных систем и ещё около 30 теорий, включая такие экзотические как секвенциальная логика и λ-исчисление. Но вернёмся к графам. Итак, - множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется упорядоченная пара G=(V,E), где V - это непустое множество вершин или узлов, а E - это множество пар вершин, называемых рёбрами. Вершины и называются концевыми
вершинами (или просто концами) ребра Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Ребра могут быть смежными
(имеют общую концевую вершину) и кратными
(множества их концевых вершин совпадают). Если же концы одного ребра совпадают, то такое ребро называется петлей
. Степенью вершины
(помните «открытый конверт»?) называют количество инцидентных ей ребер (т.е. ребер, входящих в вершину). При этом петли считают дважды. Вершина называется изолированной
, если она не является концом ни для одного ребра; висячей
(или листом
), если она является концом ровно одного ребра. Одних только определений в теории графов великое множество. Граф может быть ориентированным
(все рёбра имеют ориентацию наподобие вектора), взвешенным
(каждому ребру поставлено в соответствие некоторое число, называемое весом ребра), связным
(любых вершин , есть путь из в ) и т.д. Как правило, к возникновению новых определений и понятий приводило расширение круга задач, решаемое посредством этой теории. Именно поэтому интерес представляют не столько сами многочисленные определения (с ними можно ознакомиться в любом учебнике), сколько решаемые ими задачи! Среди них такие классические как «Проблема семи мостов Кенигсберга»
(одна из первых задач теории графов, опубликован Эйлером в 1736), «Проблема четырёх красок»
(была сформулирована в 1852 году, но доказательство получено лишь в 1976 году), «Задача коммивояжёра»
, изоморфизм
графов, планарность
Остановимся предметно на «задаче коммивояжёра».Рассмотрим типичное лабораторное задание по дискретной математике: Решить задачу коммивояжёра для () городов «жадным алгоритмом». Города определить случайным образом. Задачу считать симметричной. Критерием выгодности считать расстояние между городами. Написать программу. Задача коммивояжёра
- одна из самых известных задач, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п). Маршрут должен проходить через каждый город только один раз (выбор осуществляется среди гамильтоновых
циклов). Поскольку коммивояжер в каждом из городов встает перед выбором следующего города из тех, что он ещё не посетил, существует маршрутов для симметричной задачи коммивояжера. Таким образом, для случаев соответствующее число маршрутов равно , , . Совершенно очевидно, что решить задачу методом прямого перебора (или «грубой силы») не поможет даже самый мощный компьютер! Не случайно в условии сделан акцент на приближённый алгоритм. «Жадный алгоритм», а именно «метод ближайшего соседа» - один из простейших методов решения задачи коммивояжёра. Формулируется следующим образом: Города последовательно включаются в маршрут, при этом каждый очередной включаемый город должен быть ближайшим к последнему выбранному городу среди всех остальных, ещё не включенных в состав маршрута. Пользователь задаёт количество городов – константа CITIES_COUNT. Расстояния между городами хранятся в квадратном массиве Distances. А оптимальный путь, представляющий собой оптимальную последовательность индексов городов, хранится в линейном массиве Path. Результат работы программы (скачать) для пяти городов (так нагляднее) представлен ниже: Начальный город (родной город коммивояжёра) помечается красным цветом, остальные - синим. Следует отметить, что решение зависит от начального города, из которого начинается обход. Поэтому при начале работы программы формируется список всех городов, чтобы пользователь мог выбрать начальный (iStart). При каждой смене начального города происходит пересчёт пути коммивояжера, давая следующие решения: Однако, вспомним требования задачи. Итак, для числа городов 10, 100, 300 решения могут быть следующими: Визуальный анализ найденных решений, особенно для трёхсот городов (длинная дорога, по которой коммивояжер возвращается в родной город из последнего пункта назначения), подтверждает тезис о том, что «жадный алгоритм» может давать результат, не более чем в два раза превышающий действительно оптимальный маршрут. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Рассмотренный алгоритм является эвристическим
. В большинстве эвристических методов (метод минимального остовного дерева
, метод имитации отжига
, метод ветвей и границ
) находится не самый эффективный маршрут, а приближённое решение. На практике это единственная возможность найти, хоть и приближённое, решение задачи. Безусловно, оптимальный маршрут может дать лишь полный перебор вариантов
, но разве реально это сделать хотя бы для 100 городов, где число этих вариантов выражается 156-значным числом?! Появились вопросы — задавайте в комментариях. Нужно решить задачи — заказывайте . Теория графов
- один из обширнейших разделов дискретной математики, широко применяется
в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических
цепей, коммуникации, психологии, психологии, социологии, лингвистике, других областях знаний. Теория графов
систематически
и последовательно изучает свойства графов, о которых можно сказать, что они состоят из множеств точек и
множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард
Эйлер (1707-1882), решивший в 1736 году известную в то время задачу о кёнигсбергских мостах. Графы строят
для того, чтобы отобразить отношения на множествах .
Пусть, например, множество A
= {a
1
, a
2
, ... a
n
}
-
множество людей, а каждый элемент будет отображён в виде точки. Множество B
= {b
1
, b
2
, ... b
m
}
-
множество связок (прямых, дуг, отрезков - пока не важно). На множестве A
задано отношение
знакомства между людьми из этого множества. Строим граф
из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые
вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф! То, что мы сначала назвали "точками", следует называть вершинами графа, а то, что
называли "связками" - рёбрами графа. Теория графов не учитывает конкретную природу множеств A
и B
. Существует
большое количество самых разных конкретных задач, при решении которых можно временно забыть о специфическом
содержании множеств и их элементов. Эта специфика никак не сказывается на ходе решения задачи, независимо
от её трудности! Например, при решении вопроса о том, можно ли из точки a
добраться до
точки e
, двигаясь только по соединяющим точки линиям, неважно, имеем ли мы дело с людьми,
городами, числами и т.д. Но, когда задача решена, мы получаем решение, верное для любого содержания,
которое было смоделировано в виде графа. Не удивительно поэтому, что теория графов - один из самых
востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может
обсудить с собеседником и вопросы любви, и вопросы музыки или спорта, и вопросы решения различных задач,
причем делает это без всякого перехода (переключения), без которого в подобных случаях не обойтись человеку. А теперь строгие математические определения графа. Определение 1.
Графом называется
система объектов произвольной
природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов. Определение 2.
Пусть V
– (непустое) множество вершин, элементы v
∈V
– вершины.
Граф G
= G
(V
)
с множеством вершин V
есть некоторое
cемейство пар вида: e
= (a
, b
)
, где a
,b
∈V
, указывающих,
какие вершины остаются соединёнными. Каждая пара e
= (a
, b
)
- ребро графа.
Множество U
- множество рёбер e
графа. Вершины a
и b
– концевые точки ребра e
. Графы как структура данных.
Широким применением теории графов в
компьютерных науках и информационных технологиях обусловлено добавлением к вышеизложенным определениям
понятия графа как структуры данных. В компьютерных науках и информационных технологиях граф определяется
как нелинейная структура данных. Что же тогда - линейная структура данных и чем от них отличаются графы?
Линейные структуры данных характеризуются тем, что связывают элементы отношениями типа "простого соседства".
Линейными структурами данных являются, например, массивы, таблицы, списки, очереди, стеки, строки. В
противоположность им нелинейные структуры данных - такие, в которых элементы располагаются на различных
уровнях иерархии и подразделяются на три вида: исходные, порождённые и подобные. Итак, граф - нелинейная
структура данных. Слово граф греческого происхождения, от слов "пишу", "описываю". Из начала этой статьи
известно, что именно описывает граф: описывает он отношения. То есть, любой граф описывает отношения. И
наоборот: любое отношение можно описать в виде графа. Понятие инцидентности необходимо и при составлении алгоритмов решения многих практических задач с
графами. Например, можно ознакомиться с программной реализацией обхода в глубину графа, представленного
матрицей инцидентности
. Идея проста: можно двигаться лишь через вершины, соединённые рёбрами. А
уж если рёбрам приписаны какие-то значения ("весы", чаще всего в виде чисел, такие графы называются
взвешенными или помеченными), то можно решать сложные прикладные задачи, некоторые из которых упомянуты
в завершающем параграфе этого урока. Один из первых опубликованных примеров работ по теории графов и применения графов - работа о "задаче с
Кёнигсбергскими мостами" (1736 г.), автором которой является выдающийся математик 18-го века Леонард Эйлер.
В задаче даны река, острова, которые омываются этой рекой, и несколько мостов. Вопрос задачи:
возможно ли, выйдя из некоторого пункта, пройти каждый мост только по одному разу и вернуться в
начальный пункт? (рисунок ниже) Задачу можно смоделировать следующим образом: к каждому участку суши прикрепляется
одна точка, а две точки соединяются линией тогда и только тогда, когда соответствующие участки суши
соединены мостом (рисунок ниже, соединительные линии начерчены пунктиром). Таким образом, построен граф. Ответ Эйлера на вопрос задачи состоит в следующем. Если бы у этой задачи было
положительное решение, то в получившемся графе существовал бы замкнутый путь, проходящий по рёбрам и
содержащий каждое ребро только один раз. Если существует такой путь, то у каждой вершины должно быть
только чётное число рёбер. Но в получившемся графе есть вершины, у которых нечётное число рёбер.
Поэтому задача не имеет положительного решения. По устоявшейся традиции эйлеровым графом называется граф, в котором можно обойти все
вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное
число рёбер. Задача средней трудности на эйлеровы графы - в материале "Основные виды графов ". В 1847 г. Кирхгоф разработал теорию деревьев для решения совместной системы линейных
алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом
контуре электрической цепи. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления,
конденсаторы, индуктивности и т.д., он рассматривал соответствующие комбинаторные структуры, содержащие
только вершины и связи (рёбра или дуги), причём для связей не нужно учитывать, каким типам электрических
элементов они соответствуют. Таким образом, Кирхгоф заменил каждую электрическую цепь соответствующим
графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый
цикл графа электрической цепи. Кэли в 1858 г., занимаясь чисто практическими задачами органической химии, открыл
важный класс графов, называемых деревьями. Он стремился перечислить изомеры насыщенных углеводородов,
с данным числом атомов углерода. Кэли прежде всего сформулировал задачу абстрактно: найти число
всех деревьев с p
вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось
сразу решить эту задачу, и он стал изменять её формулировку таким образом, чтобы можно было решить
новую задачу о перечислении: Пример 1.
Пусть A
-
множество чисел 1, 2, 3
: A
= {1, 2, 3}
.
Построить граф для отображения отношения " Решение. Очевидно, что числа 1, 2, 3 следует представить в виде вершин графа.
Тогда каждую пару вершин должно соединять одно ребро. Решая эту задачу, мы пришли к таким основным
понятиям теории графов, как ориентированные и неориентированные графы
. Неориентированные
графы - такие, рёбра которых не имели направления. Или, как говорят ещё чаще, порядок двух концов
ребра не существенен. В самом деле, граф, построенный в самом начале этого урока
и отображавший отношение знакомства между людьми, не нуждается в направлениях рёбер, так как можно утверждать,
что "человек номер 1" знаком с "человеком номер 2" в той же мере, как и "человек номер 2" с "человеком
номер 1". В нашем же нынешнем примере одно число меньше другого, но не наоборот. Поэтому соответствующее ребро графа
должно иметь направление, показывающее, какое всё же число меньше другого. То есть, порядок концов ребра
существенен. Такой граф (с рёбрами, имеющими
направление) называется ориентированным графом или орграфом. Итак, в нашем множестве A
число 1 меньше числа
2 и числа 3, а число 2 меньше числа 3. Этот факт отображаем рёбрами, имеющими направление, что
показывается стрелками. Получаем следующий граф: Пример 2.
Пусть A
-
множество чисел 2, 4, 6, 14
: A
= {2, 4, 6, 14}
.
Постоить граф для отображения отношения "делится нацело на" на этом множестве. Решение. В этом примере часть рёбер будут иметь направление,
а некоторые не будут, то есть строим смешанный граф
. Перечислим отношения на множестве: 4 делится нацело на 2, 6 делится
нацело на 2, 14 делится нацело на 2, и ещё каждое число из этого множества делится нацело на само себя.
Это отношение, то есть когда число делится нацело на само себя, будем отображать в виде рёбер, которые
соединяют вершину саму с собой. Такие рёбра называются петлями
. В данном случае нет необходимости
давать направление петле. Таким образом, в нашем
примере три обычных направленных ребра и четыре петли. Получаем следующий граф: Пример 3.
Пусть даны множества A
= {α, β, γ}
и B
= {a, b, c}
.
Построить граф для отображения отношения "декартово произведение множеств". Решение. Как известно из определения декартова произведения множеств
, в нём нет
упорядоченных наборов из элементов одного и того же множества. То есть в нашем примере нельзя соединять
греческие буквы с греческими и латинские с латинскими. Этот факт отображается в виде двудольного графа
,
то есть такого, в котором вершины разделены на две части так, что вершины, принадлежащие одной и той же
части, не соединены между собой. Получаем следующий граф: Пример 4.
В агентстве по недвижимости работают менеджеры Игорь,
Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений
"Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3, О5, О6", "Пётр работает
с объектом О8". Решение. Граф, отображающий данные отношения, будет так же двудольным, так как
менеджер не работает с менеджером и объект не работает с объектом. Однако,
в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с
объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость
давать рёбрам направления может показаться "математической тупостью". Но всё же, и это вытекает из
строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам
нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для
планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в
заданном направлении. Итак, получаем следующий ориентированный двудольный граф: И вновь к примерам с числами. Пример 5.
Пусть задано множество C
= {2, 3, 5, 6, 15, 18}
.
Построить граф, реализующий отношение, определяющее все пары чисел a
и b
из
множества C
, у которых при делении второго элемента на первый получаем частное, которое
является целым числом больше 1. Решение. Граф, отображающий данные отношения, будет ориентированным, так как в
условии есть упоминание о втором и первом элементе, то есть, ребро будет направлено от первого элемента
ко второму. Из этого однозначно понятно, какой элемент является перым, а какой вторым. Ещё добавим
терминологии: ориентированные рёбра принято называть дугами. В нашем графе будет 7 дуг:
e
1
= (3, 15)
,
e
2
= (3, 18)
,
e
3
= (5, 15)
,
e
4
= (3, 6)
,
e
5
= (2, 18)
,
e
6
= (6, 18)
,
e
7
= (2, 6)
.
В этом примере рёбра (дуги) графа просто пронумерованы, но порядковые номера - не единственное, что
можно приписать дуге. Дуге можно приписать также весы означающие, например, стоимость пересылки груза
из одного пункта в другой. Но с весами дуг мы познакомимся позже и подробнее.
Итак, получаем следующий ориентированный граф: Как мы уже знаем из теоретической вступительной части, теория графов не учитывает
специфическую природу множеств и с помощью одного и того же графа можно задать отношения на множествах
с самым разным содержанием. То есть, от этого самого содержания при моделировании задачи можно
абстрагироваться. Перейдём к примерам, иллюстрирующим это замечательное свойство теории графов. Пример 6.
На кусочке шахматной доски размером 3 Х 3 размещены
два белых коня и два чёрных коня так, как показано на рисунке ниже. Можно ли переместить коней в состояние, которое изображено на следующем рисунке,
не забывая, что две фигуры не могут находиться на одной клетке? Решение. В конструируемом графе пары вершин будут связаны отношением "ход коня".
То есть, одна вершина - та, из которой конь ушёл, а другая - та, в которую пришёл, а промежуточная клетка
буквы "г" будет за пределами этого отношения. Получаем следующий граф: И всё же конструкция получилась громозкой. В ней видны клетки шахматной доски, а
многие рёбра графа пересекаются. Нельзя ли абстрагироваться от физического вида шахматной доски и
вообразить отношения проще? Оказывается, можно. В новом графе соседними вершинами будут те, которые
связаны отношением "ход коня", а не соседние по шахматной доске (рисунок ниже). Теперь легко увидеть, что ответ на вопрос этой задачи - отрицательный. В начальном
состоянии между двумя белыми конями нет чёрного коня, а в конечном состоянии этот чёрный конь должен быть.
Рёбра графа размещены так, что два находящихся рядом коня не могут перепрыгнуть друг через друга. Пример 7.
Задача о волке, козе и капусте. На одном берегу реки
находятся человек (Ч), лодка, волк (В), коза (Кз) и капуста (Кп). В лодке одновременно могут находиться
человек и не более одного из перевозимых объектов. Человек должен перевезти на другой берег все объекты,
соблюдая условие: нельзя оставлять без присмотра волка вместе с козой и козу вместе с капустой. Решение. В конструируемом графе вершины - конфигурации, а рёбра - отношение
"связь одним плаваньем лодки" между конфигурациями. Конфигурация означает расположение объектов
на первоначальном берегу и на противоположном берегу. Каждая конфигурация отображается в виде
(A
|B
)
, где A
- объекты, находящиеся на
первоначальном берегу, а B
- объекты, находящиеся на противоположном берегу. Первоначальная
конфигурация, таким образом, - (ЧВКпКз
|
)
. Например, после
переправки на другой берег козы конфигурация будет (ВКп
|ЧКз
)
.
Конечная конфигурация всегда (
|ЧВКпКз
)
.
Теперь можем построить граф, зная уже, что означают вершины и рёбра: Разместим вершины графа так, чтобы рёбра не пересекались, а соседними были вершины,
которые связаны отношением на графе. Тогда увидеть отношения
будет намного проще (для увеличения рисунка щёлкните по нему левой кнопкой мыши): Как видим, существуют два различных непрерывных маршрута из начальной конфигурации
в конечную. Поэтому задача имеет два различных решения (и оба правильные). На основе теории графов разработаны методы решения прикладных задач, в которых в виде
графов моделируются весьма сложные системы. В этих моделях узлы содержат отдельные
компоненты, а рёбра отображают связи между компонентами. Обычно для моделирования транспортных сетей,
систем массового обслуживания, в сетевом планировании используются взвешенные графы. Мы о них уже говорили, это
графы, в которым дугам присвоены весы. Графы-деревья применяются, например, для построения деревьев решений
(служат для анализа рисков, анализа возможных приобретений и убытков в условиях неопределённостей).
С применением теории графов разработаны и другие многочисленные математические модели
для решения задач в
конкретных предметных областях. Постановка задачи. Имеется система водопроводных труб, представленная графом на рисунке ниже. Каждая дуга графа отображает трубу. Числа над дугами (весы) - пропускная способность труб.
Узлы - места соединения труб. Вода течёт по трубам только в одном направлении. Узел S
-
источник воды, узел T
- сток. Требуется максимизировать объём воды, протекающей от источника к
стоку. Для решения задачи о потоках можно воспользоваться методом Форда-Фулкерсона. Идея метода:
поиск максимального потока производится по шагам. В начале работы алгоритма поток полагается равным нулю.
На каждом последующем шаге значение потока увеличивается, для чего ищется дополняющий путь, по которому
поступает дополнительный поток. Эти шаги повторяются до тех пор, пока существуют дополнительные пути. Задача
успешно применяется в различных распределённых системах: система электоснабжения, коммуникационная сеть,
система железных дорог и других. В задачах планирования сложных процессов, состоящих из множества работ, часть из
которых выполняется параллельно, а часть последовательно, широкое применение получили взвешенные графы,
известные под названием сети ПЕРТ (PERT). PERT - Program (Project) Evaluation and Review Technique - техника оценки и анализа
программ (проектов), которая используется при управлении проектами. Сеть ПЕРТ - взвешенный ациклический ориентированный граф, в котором каждая дуга
представляет работу (действие, операцию), а вес дуги - время, требуемое для её выполнения. Если в сети есть дуги (a
, b
)
и
(b
, c
)
, то работа, представленная дугой
(a
, b
)
, должна быть завершена до начала выполнения
работы, представленной дугой (b
, c
)
. Каждая вершина
(v
i
)
представляет момент времени, к
которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (v
i
)
. В таком графе: Путь максимальной длины между этими вершинами графа (из начала в конец процесса
выполнения работ), называется критическим путём. Для сокращения времени выполнения всего комплекса
работ необходимо найти работы, лежащие на критическом пути, и уменьшить их продолжительность за счёт,
например, привлечения дополнительных исполнителей, механизмов, новых технологий. Весь блок "Теория графов" «Ещё один увлекательный способ решения задач» (метод графов) Автор: Пыркова Мария, обучающаяся 7 класса школы-интерната № 9 ОАО РЖД г. Кинель Самарской области Руководитель: Степанова Ольга Алексеевна, учитель математики высшей категории. г. Кинель, 2015 Актуальность решающая роль задач в обучении математике; введение в школьный курс разделов «Комбинаторика», «Логика», «Вероятность»; отыскание способов решения нестандартных задач. Цель исследования: изучить понятие «графа» и его элементов; применять при решении различных типов задач. Объект исследования: граф ПРЕДМЕТ ИССЛЕДОВАНИЯ история математики, виды задач, способы решения задач. Основные методы исследования: исследовательский; использование на практике. компьютерная обработка данных; классификация и анализ собранного материала; математический отбор. Математическое понятие «граф». В математике графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. нулевой граф неполный граф. полный граф. Сфера применения графов Практическая часть Алгоритм составления графа Обсудить о каком процессе идет речь? Какие величины характеризуют данный процесс? Каким соотношением связаны эти величины? Сколько процессов описывается в задаче? Есть ли связь между элементами? Если ответы на эти вопросы записывать схематически, то эта схема и будет сетевым графом. «Сколько у тебя в стаде голов скота?» Н а вопрос путника: - пастух ответил: «Если бы к моему стаду добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козленок». Сколько голов скота было в стаде? Решение: Составим граф по условию задачи. Решаем обратно. Ответ: в стаде 59 голов скота. Задачи на движение. Машина прошла первый участок пути за 3 часа, а второй участок - за 2 часа. Длина обоих участков вместе 267 км. С какой скоростью шла машина на каждом участке, если скорость на втором участке была на 8,5 км/ч больше, чем на первом? Построим сетевой граф. Пусть V 1 = х км/ч, тогда V 2 = х+ 8,5 км/ч, S 1 = 3х км, S 2 = 2(х+8.5)км Составим уравнение: 3х + 2(х+8,5) = 267 Ответ: 50 км/ч Комбинаторные задачи. Задача «Что выше?» На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому. Ответ: клен самое низкое дерево. Опрос одноклассников Заключение «Рано или поздно всякая правильная математическая идея находит применение в том или ином деле.» (А.Н. Крылов) Графы – это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи. Графы позволяют наглядно представить условие задачи, держать в памяти многочисленные факты, а значить, значительно упростить её решение. Вызывает интерес к изучению математики и получению хороших результатов. Список литературы Энциклопедический словарь юного математика. \Сост. А.П.Савин.- М.: Педагогика, 1989 Квант №6 1994г. М. Гарднер «Математические досуги» М.: Мир, 1972 Берж К. Теория графов и ее применение. ИЛ, 1962. Математика, учебник для 5 кл. / Н.Я.Виленкин, В.И.Жохов и др.-М:Просвещение, 2011 Математика, учебник для 6 кл. / Н.Я.Виленкин, В.И.Жохов и др.-М:Просвещение, 2011 Алгебра: учебник для 7 кл. / Ю.Н.Макарычев и др., под редакцией С.А.Теляковского.-М.:Просвещение,2011 Элективные курсы «Решение задач с помощью графов»/ авт.-сост.Л.Н.Харламова. - Волгоград: Учитель,2007 . Спасибо за внимание! 1736 год, г.Кёнигсберг. Через город
протекает река Прегеля. В городе - семь
мостов, расположенных так, как показано на рисунке выше. С давних времен жители
Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по
каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на
практике, на прогулках - проходя по этим самым мостам. Никому не удавалось
доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по
мостам никто не мог. Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он
решил не только эту конкретную задачу, но придумал общий метод решения подобных
задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим
образом: он "сжал" сушу в точки,
а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий,
связывающих эти точки, называют
ГРАФОМ
. Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки
называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Виды графов:
1.
Ориентированный
граф
(кратко орграф
) - рёбрам
которого присвоено направление. 2.
Неориентированный
граф
- это граф , в котором нет направления линий. 3. Взвешенный граф
–
дуги или ребра имеют вес (дополнительная информация). Решение задач с помощью графов:
Задача 1.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 2.
На пришкольном участке растут 8 деревьев: яблоня,
тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше
лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше
рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от
самого низкого к самому высокому. Решение:
Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения:
“быть ниже” и “быть выше”. Рассмотрим отношение “быть
ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче
сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине
и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем
идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь. Задача 3.
У Наташи есть 2 конверта: обычный и
авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать
конверт и марку, чтобы отправить письмо? Решение:
Ниже представлен разбор задач.
i
будет равен длине кратчайшего пути. (Алгоритм 1 для задач динамического программирования отражает принцип оптимальности Беллмана: если ищется кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути также должна быть минимальна.) На рисунке 2 приведен пример применения алгоритма 1 для определения кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).
, такой, что 
и т.д.
, все остальные вершины индексами 
, i = 1, n;
>, то вычисляем новое значение 
;
- установившиеся значения индексов, которые обладают следующим свойством: величина 
равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.
;
вычисляем величину 
где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина 
минимальна, индексом 
.
, а сам кратчайший путь определяется так, как это было описано выше.
. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись 
- остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.
, где 
- величина потока, протекающего от j
узла к узлу i
. Чтобы найти максимальный поток, выполняем следующие действия.
=. Назначим 
и пометим узел 1 меткой. Полагаем i
=1.
- множество узлов j
, в которые можно перейти из узла I
по ребру с положительной остаточной пропускной способностью 
>0 для всех j
. Если 
, выполняем 3 этап, в противном случае переходим к 4.
находим узел k
, такой, что 
. Положим 
и пометим узел k
меткой 
. Если k
=n
, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i
=k
и возвращаемся к 2 этапу.
, находим помеченный узел r
, непосредственно предшествующий узлу i
, и удаляем его из множества узлов, смежных с узлом r
. Полагаем i
=r
и возвращаемся ко 2 этапу.
. Обозначим через множество узлов, через которые проходит p
й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n
).тогда максимальный поток, проходящий по этому пути
в направлении движения потока и увеличиваются на эту же величину в противоположном направлении.
, если поток идет от узла i
к j
,
, если поток идет от узла j
к i
.
и конечных пропускных способностей ребра (i
, j
), можно вычислить оптимальный поток через это ребро следующим образом. Положим . Если 
>0, поток, проходящий через ребро (i
, j
) равен . Если 
>0, тогда поток равен . (случай, когда одновременно >0 и >0, невозможен).
= и помечаем узел 1 меткой 
. i
=1
и помечаем узел 3 меткой 
. i
=3 и возвращаемся к 2)
. Получаем сквозной путь.
:
и помечаем узел 1 меткой . i
=1
. i
=2 и возвращаемся к 2)
. Помечаем узел 3 меткой 
. i
=3 и возвращаемся к 2)
(
, поэтому узел 5 не включается в 
и помечаем узел 4 меткой 
. i
=4 и возвращаемся к 2)
(так как узлы 1 и 3 помечены, они не включаются в 
)
. Помечаем узел 5 меткой 
. Получен сквозной путь. Переходим к 5)
и . Вычисляем остаточные пропускные способности вдоль пути 
:
и помечаем узел 1 меткой . i
=1
и помечаем узел 2 меткой
. i
=2 и возвращаемся к 2)
Прежде всего, немного теории.
Составим словесный алгоритм.
Блок-схема поиска пути имеет вид:
Литература
Решение дискретной математики на заказ
Будем рады Вам помочь!Основные понятия теории графов
Классические задачи теории графов и их решения
Задачи с графами для закрепления основных понятий
Теория графов и важнейшие современные прикладные задачи
Графы и задача о потоках
Графы и сетевое планирование
