Шапорев С.Д. Дискретная математика - файл n4.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n4.doc





Глава 4. Теория графов.
§ 4.1. Основные понятия и определения.
Теория графов применяется при анализе функционирования сложных систем, таких как сети железных дорог, телефонных или компьютерных сетей, ирригационных систем. Эта теория традиционно является эффективным аппаратом формализации задач экономической и планово – производственной практики, применяется в автоматизации управления производством, в календарном и сетевом планировании.

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

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

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

Если в графе все элементы множества изображаются дугами, то граф называется ориентированным или орграфом, если ребрами, то неориентированным. Два ребра называются смежными, если они имеют общий конец.

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


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

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

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

рядка 1, 2, 3 и 4. Они обозначаются

. Число ребер в полном графе .

Два графа и называются изо-

морфными, если между множеством

их вершин существует такое взаимно

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

Способов задания графов - великое множество. Самый простой способ – задание множеств и . Граф также может быть задан просто рисунком. В силу изоморфизма один и тот же граф может быть изображен разными рисунками. Например, слева

на рисунке изображение одного и того

же графа, так как в обоих случаях со-

держится одна и та же информация о

вершинах и дугах графа и их взаимном

расположении. В некоторых случаях

все же приходится различать изоморф-

ные графы, тогда полезно понятие по-

меченный граф. Граф порядка называется помеченным, если его вершинам присвоены некоторые метки, например, 1, 2, 3… Пусть , тогда, например, на рисунке

1 2 3 слева изображены три разных графа.

Строго говоря, абстрактный или непо-

меченный граф - это класс изоморфных

2 3 1 3 1 2 графов. Число непомеченных гра-

фов порядка определяется очень сложно. Известна формула Пойа

, (4.1.1)

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

Маршрут называется циклическим, если . Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется длиной маршрута.

Важным понятием теории графов является связность. Граф называется связ-

ным, если любые две его несовпадающие

вершины соединены маршрутом. Для

орграфа существует еще понятие сильной

связности. Для этого определим понятие

сильно- слабо- пути. Путь – это ориентированный марш-

связный связный граф рут. Поэтому, если для установления

граф (нет пути из в ) простой ( или слабой ) связности графа



Пойа (1-1 г.г.) - ский математик.

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

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

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

Весом пути (длиной, стоимостью и так далее в зависимости от контекста) сети называется число (4.2.1)

Понятие сети и веса маршрута для неориентированного графа определяется аналогично.
§ 4.3. Способы задания графов.
В подавляющем большинстве случаев граф задается матрицей. Для расчетов на

B ЭВМ – это единственный способ. Существует редко

D применяемый сейчас метод задания графа в виде ла-

латинской матрицы. В этом способе направление дуг

задается порядком букв в их названии. Например,

А рассмотрим граф, изображенный на рисунке слева.

E Для него латинская матрица имеет следующий вид.

Если граф неориентированный, то в латинской мат-

C рице просто штрихуют соответствующую клеточку в




А

B

C

D

E

A




AB

AC







B

BA







BD




C

CA










CE

D




DB










E










ED

EE

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



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



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



торами инциденций графа Для матрицы смежности и матрицы инциденций справедливы следующие теоремы.

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

Теорема 2. Графы (орграфы) изоморфны тогда и только тогда, когда их матрицы инциденций получаются друг из друга произвольными перестановками строк и столбцов.
§ 4.4. Упорядочивание дуг и вершин орграфа.
Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены. Под упорядочиванием вершин связного орграфа без контуров, то есть циклических цепей понимают такое разбиение его вершин на группы, при котором:

1). вершины первой группы не имеют предшествующих, а вершины последней группы последующих;

2). вершины любой другой группы не имеют предшествующих в следующей группе;

3). вершины одной и той же группы дугами не соединяются.

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

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

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

Аналогичным образом упорядочиваются дуги орграфа. Рассмотрим несколько примеров. Упорядочим вершины графа изображенного слева. На рисунке графа верши-

на B не содержит входящих дуг, отнесем ее к первой

B группе. Вычеркиваем все дуги, исходящие из B. По-

D лучим следующий граф ( смотрите ниже ). В нем

C опять находим одну вершину, в которую не заходит

А ни одна дуга. Это вершина D. Вычеркиваем дуги,

исходящие из D. Появится еще одна вершина – вер-

шина Е, в которую не заходит ни одна дуга (смотри-

E те следующий рисунок правее). После вычеркива-

ния дуг EC и EA получим вершину А, которая вхо-

B B

D

C D C

А

A

E E

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

E дит только по одной вершине. Однако в об-

щем случае в каждую такую группу могут

В D C входить несколько вершин, если граф боль-

шой и содержит много вершин. При упоря-

A дочивании дуг получается та же картина, а

сами дуги нумеруются подобным же обра-

зом.

1-я 2-я 3-я 4-я 5-я группа



Фалкерсон (1-1 г.г.) - ский математик.

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

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

Пример. Рассмотрим неориентированный граф, изображенный ниже. Соста-

B вим матрицу смежности вершин и возведем ее в квадрат. Ре-

зультат возведения изображен прямо под графом. Рассмотрим

первую строку. Элемент Это значит, что существуют

А три маршрута из А в А длиной два ребра. Действительно, это

C маршруты Из А в B существу-

D ют два маршрута: Если использовать чис-



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



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

же. Рассмотрим элемент после воз-

А B C D ведения матрицы смежности вершин в

квадрат. , то есть из вершины В

в вершину В есть два маршрута длиной

две дуги. Это маршруты и

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


§ 4.6. Определение экстремальных путей на графах. Метод Шимбелла.
Введем, следуя Шимбеллу, специальные операции над элементами матрицы смежности вершин, позволяющие находить кратчайшие или максимальные пути между вершинами, состоящие из заданного количества ребер. Эти операции таковы.

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

(4.6.1)

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

(4.6.2)

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

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

1 B 2 фа матрицу смежности – нагрузки. Она определяет

A все маршруты, состоящие из одного ребра. Найдем

2 2 C кратчайшие пути из двух ребер, для этого возведем

3 эту матрицу в квадрат с учетом операций Шимбелла

2 D (min – кратчайшие пути).

1





Шимбелл (1-1 г.г.) - ский математик.
Например,

Аналогично, кратчайшие пути из трех ребер будут


и так далее. Например, длина кратчайшего пути из трех ребер из вершины D в вершину C равна семи. Это путь DBAC.
§ 4.7. Алгоритм Дейкстры (случай неотрицательных весов).
Рассмотрим еще несколько алгоритмов нахождения кратчайшего пути между двумя заданными вершинами в ориентированной сети. Пусть - ориентированный граф со взвешенными дугами. Обозначим - вершину - начало пути и - вершину – конец пути.

Общий подход к решению задачи о кратчайшем пути был развит американским математиком Ричардом Беллманом, который предложил название динамическое программирование. Задача о кратчайшем пути частный случай следующей задачи: найти в заданном графе пути, соединяющие две заданные вершины и доставляющие минимум или максимум некоторой аддитивной функции, определенной на путях. Чаще всего эта функция трактуется как длина пути и задача называется задачей о кратчайших путях. Алгоритм Дейкстры одна из реализаций этой задачи. Его часто называют алгоритмом расстановки меток. В процессе работы этого алгоритма узлам сети приписываются числа (метки) , которые служат оценкой длины (веса) кратчайшего пути от вершины к вершине . Если вершина получила на некотором шаге метку , это означает, что в графе существует путь из в , имеющий вес . Метки могут находиться в двух состояниях – быть временными или постоянными. Превращение метки в постоянную означает, что кратчайшее расстояние от вершины до соответствующей вершины найдено.

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

Этап 1. Нахождения длины кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

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

Шаг 2. Изменение меток.

Для каждой вершины с временной меткой, непосредственно следующей за вершиной , меняем ее метку в соответствии со следующим правилом:

(4.7.1)

Шаг 3. Превращение метки из временной в постоянную.

Из всех вершин с временными метками выбираем вершину с наименьшим



Дейкстра (1-1 г.г.) - американский математик.

Ричард Беллман (1-1 г.г.) - американский математик.

значением метки (4.7.2)

Превращаем эту метку в постоянную и полагаем

Шаг 4. Проверка на завершение первого этапа.

Если , то - длина кратчайшего пути от до . В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение самого кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине с постоянными метками, находим вершину , удовлетворяющую соотношению

(4.7.3)

Включаем дугу в искомый путь и полагаем

Шаг 6. Проверка на завершение второго этапа.

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

Пример. Задана весовая матрица сети . Найти минимальный путь из вершины в вершину по алгоритму Дейкстры.

Изобразим теперь сам граф по данной матрице весов. Поскольку в данном графе есть цикл ме-

жду вершинами , и , то верши-

7 ны графа нельзя упорядочить по алго-

5 8 9 ритму Фалкерсона. На рисунке графа

6 9 временные и постоянные метки указаны

6 6 над соответствующей вершиной. Итак,

11 6 4 распишем подробно работу алгоритма

Дейкстры по шагам.

Этап 1. Шаг1. Полагаем ,



1-я итерация. Шаг 2. Множество вершин, непосредственно следующих за с временными метками Пересчитываем временные метки этих вершин

Шаг 3. Одна из временных меток превращается в постоянную

Шаг 4. , происходит возвращение на второй шаг.

2-я итерация. Шаг 2. , , .

Шаг 3.

Шаг 4. , возвращение на второй шаг.

3-я итерация. Шаг 2.

Шаг 3. .

Шаг 4. , возвращение на второй шаг.

4-я итерация. Шаг 2.

Шаг 3. .

Шаг 4. , возвращение на второй шаг.

5-я итерация. Шаг 2. .

Шаг 3.

Шаг 4. конец первого этапа.

Этап 2. Шаг5. Составим множество вершин, непосредственно предшествующих с постоянными метками Проверим для этих двух вершин выполнение равенства (4.7.3).

Включаем дугу в кратчайший путь. .

Шаг 6. , возвращение на пятый шаг.

2-я итерация. Шаг 5.

Включаем дугу в кратчайший путь. .

Шаг 6. , завершение второго этапа.

Итак, кратчайший путь от вершины до вершины построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг
§ 4.8. Алгоритм Беллмана - Мура (случай произвольных весов).
Если веса – произвольные числа и граф не содержит ориентированных циклов отрицательного веса, то минимальный путь может быть найден алгоритмом Беллмана – Мура, похожим на алгоритм Дейкстры. Этот алгоритм часто называют алгоритмом корректировки меток. Как и в алгоритме Дейкстры всем вершинам приписываются метки, однако здесь нет деления меток на временные и постоянные. Корректировка меток осуществляется по старому правилу (4.7.1), однако выполнение условия (4.7.2) теперь не гарантирует, что длина кратчайшего пути от до найдена, так как наличие в графе дуг с отрицательными весами может уменьшить эту метку на последующих шагах. Поэтому в алгоритме Беллмана – Мура вместо процедуры превращения временной метки в постоянную формируется очередь вершин, которые нужно просмотреть



Мур (1-1 г.г.) - американский математик.

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

Глава 4. Теория графов
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации