Определение кратчайших путей

Содержание

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

1.Основные понятия……………………………………………2

1.1.Графы. Определения…………………………………….2

1.2.Пути и маршруты…………………………………………4

1.3.Веса и длина пути………………………………………..6

1.4.Петли и ориентированные циклы…………………..7

1.5.Степени вершины…………………………………………8

1.6.Подграфы……………………………………………………8

1.7.Типы графов………………………………………………10

1.8.Сильносвязные графы и компоненты графа……13

1.9.Матричные представления…………………………..14

2.Алгоритм Флойда…………………………………………17

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

Библиография………………………………………………..19

Приложение1: Листинг программы…….……………..20

Введение

Часто бывает полезно и наглядно изображать некоторую ситуацию в

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

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

1.Основные понятия

1.1.Графы. Определения

Граф G задается множеством точек или вершин x_1, х₂,,……, х_n (которое обозначается через X) и множеством линий или ребер a_1, а₂……, а_n (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).

Если ребра из множества А ориентированы, что обычно пока­зывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис. 1.1(а)). Если ребра не имеют ориентации, то граф называется неориентирован­ным (рис. 1.1(6)). В случае когда G = (X, А) является ориенти­рованным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G = (X, А).

Далее, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 1.1(а) обо­значение (х₁, х₂) относится к дуге а₂ , а (х₂,, х₁) — к дуге а₂.

Другое, употребляемое чаще описание ориентированного гра­фа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответ­ствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = (X, Г).

Для графа на рис. 1.1(а) имеем Г (x₁) = {х₂,, х₅}, т. е. вершины х₂ и х₅ являются конечными вершинами дуг, у которых начальной вершиной является х_1.

Г(x₂)={x₁, x₃},

Г(x₃)={x₁},

Г(x₄)=?-пустое множество,

Г(x₅)={x₄}

Рис. 1.1. (а) Ориентированный граф, (б) Неориентированный граф, (в) Сме­шанный граф.

В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изобра­женные на рис. 1.1(6) и 1.1(в)), предполагается, что соответствие Г задает такой эквивалентный, ориентированный граф, который получается из исходного графа заменой каждого неориентиро­ванного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис. 1.1(6), имеем Г (х₅) = {х_1, х₃,, x₄},

Г (х₁) = {х₅} и т. д.

Поскольку Г (x₁) представляет собой множество таких вершин x_i Є Х, для которых в графе G существует дуга (х_i, x_j), то через Г^-1(x_i) естественно обозначить множество вершин х_k, для которых в G существует дуга (х_k, x_i). Отношение Г^-1 (х_i) принято называть обратным соответствием. Для графа, изображенного на рис 1.1 (а), имеем

Г^-1(x₁)={x₂. x₃},

Г^-1(x₂)={x₁},

и т. д.

Вполне очевидно, что для неориентированного графа Г^-1(x_i) = Г (х_i) для всех х₁ Є X.

Когда отображение Г действует не на одну вершину, а на мно­жество вершин Х_q = {х₁, x₂, …, х_q}, то под Г (Х_q) понимают объединение

Г(x₁) U Г(x₂) U…U Г(x_q),

т. е. Г (Х_q) является множеством таких вершин х_i Є X, что для каждой из них существует дуга (х_i, х_j,) в G, где х_i Є Х_q. Для гра­фа, приведенного на рис. 1.1(а), Г ({x₂, х₅}) = {х₁, х_3,, x₄} и Г ({x₁, х₃}) = {х_2,, х₅, х₁}

Отображение Г (Г (x_i)) записывается как Г² (x_i). Аналогично «тройное» отображение Г (Г (Г (х_i))) записывается как Г^{3 (}x_i) и т. д. Для графа, показанного на рис. 1.1(а), имеем:

Г² (x₁) = Г (Г (x₁)) = Г ({х₂,, x₅}) = {х₁, х₃,, x₄},

Г³(x₁)=Г(Г²(x₁))=Г({x₁, x₃, x₄})={x₁, x₃, x₅}

и т. д.

Аналогично понимаются обозначения ^Г-2 (х_i), ^Г-3 (х_i) и т. Д

1.2. Пути и маршруты

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

Так, на рис. 1.2 последовательности дуг

a₆ , a₅ , a₉ , a₃ , a₄ , (1.1)

a₁ , a₆ , a₅ , a₉ , (1.2)

a₁ , a₆ , a₅ , a₉ , a₁₀ , a₆ , a₄ , (1.3)

являются путями.

Рис. 1.2.

Дуги а = (x_i , x_j), x_i ? x_j , имеющие общие концевые вершины, называются смежными. Две вершины х_i и x_j называются смежными, если какая-нибудь из двух дуг (х_i , х_j) и (x_j , x_i) или обе одно­временно присутствуют в графе. Так, например, на рис. 1.2 дуги a₁, a₁₀, a₃ и a₆ как и вершины х₅ и x₃, являются смежными, в то время как дуги а_г и a₅ или вершины х₁ и x₄ не являются смежными.

Ориентированной цепью (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являют­ся орцепями, а путь (1.3) не является таким, поскольку дуга а_в в нем используется дважды.

Простой орцепъю называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (1.2) является простой орцепью, а пути (1.1) и (1.3) — нет. Очевидно, что простая орцепь является также орцепью, но обратное утвер­ждение неверно. Например, путь (1.1) является орцепью, но не простой орцепью, путь (1.2) является орцепью и простой орцепью, а путь (1.3) не является ни орцепью, ни простой орцепью. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последова­тельность ребер

a₁, а₂. . . а_q, в которой каждое ребро а_i , за исключением, возможно, первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими двумя концевыми вершинами. После­довательности дуг

а₂ , а₄ , а₈ , а₁₀ , (1.4)

а₂ , а₇ , а₈ , а₄ , а₃ (1.5)

а₁₀ , а₇ , а₄ , а₈ , а₇, а₂ (1.6)

в графе, изображенном на рис. 1.2, являются маршрутами.

Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи ¹) и простые цепи ²). Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) — цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.

Путь или маршрут можно изображать также последователь­ностью вершин, что мы и будем использовать. Путь (1.1) можно представить также последовательностью вершин х₂ , х₅ , x₄, х₃, х₅ , х₆ и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей пли простых цепей.

1.3. Веса и длина пути

Иногда дугам графа G сопоставляются (приписываются) чис­ла — дуге (х_i , x_j ) ставится в соответствие некоторое число с_{i j} , называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа v_i) приписываются вершинам х_i графа, и тогда полу­чается граф с взвешенными вершинами. Если в графе веса при­писаны и дугам, и вершинам, то он называется просто взвешен­ным .

При рассмотрении пути µ , представленного последовательно­стью дуг (a₁, а₂, . . ., а₃), за его вес (или длину) принимается число ? (?), равное сумме весов всех дуг, входящих в ? , т. е.

? (?) = ? c_ij

(x_{i ,} x_j) Є ?

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

1.4. Петли, ориентированные циклы

Петлей называется дуга, начальная и конечная вершины кото­рой совпадают. На рис. 1.3, например, дуги а₂ и а₅ являются пет­лями.

Путь a₁, a₂,….., а_q называется замкнутым, если в нем начальная вершина дуги а₁ совпадает с конечной вершиной дуги а_q.

Так, например, в графе, приведенном на рис. 1.3, последова­тельности дуг

a₃ , a₆ , a₁₁ , (1.7)

a₁₁ , a₃ , a₄ , a₇ , a₁ , a₁₂ , a₉ , (1.8)

a₃ , a₄ , a₇ , a₁₀ , a₉ , a₁₁ , (1.9)

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина х₁ используется в нем дважды . Контур, проходящий через все вершины графа, имеет особое значение и называется гамилътоновым контуром . Конеч­но, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.3, а граф на рис. 1.2 не имеет гамильтоновых контуров, поскольку не существует такой дуги, для которой х₁ была бы конечной вершиной.

Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом х₁, х₂, . . ., х_q , в котором совпадают начальная и конечная вершины, т. е. в котором х₁ = х_q .

На рис. 1.3 маршруты

a₁ , a₁₂ , a₁₀ , (1.10)

и

a₁₀ , a₁ , a₃ , a₄ , a₇ , a₁ , a₁₂ (1.11)

являются замкнутыми маршрутами.

1.5. Степени вершины

Число дуг, которые имеют вершину х_i своей начальной верши­ной, называется полустепенъю исхода вершины х_i , и, аналогично, число дуг, которые имеют x_i своей конечной вершиной, называется полустепенъю захода вершины x_i .

Таким образом, на рис. 1.3 полустепень исхода вершины х₆ , обозначаемая через d₀ (х₆ ), равна | Г (х₆) | = 2, и полустепень захода вершины х₆ , обозначаемая через d_t (х₆ ), равна | Г^-1 (х) ? = 1.

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

где n — число вершин и m— число дуг графа G.

Для неориентированного графа G = (X, Г) степень вершины х_i определяется аналогично — с помощью соотношения d (x_i) ? | Г (x_i) |

1.6. Подграфы

Пусть дан граф G = (X, А). Остовным подграфом G_р гра­фа G называется граф (X, А_p), для которого А_р c А. Таким обра­зом, остовный подграф имеет то же самое множество вершин, что и граф G, но множество дуг подграфа G_р является подмножеством множества дуг исходного графа.

Граф на рис. 1.4(6) — остовный подграф О_р графа С, изобра­женного на рис. 1.4(а).

Пусть дан граф G = (X, Г). Порожденным подграфом G_s, называется граф (Х_s, Г_s), для которого Х_s c X и для каждой вершины X_i Є X_s, Г_s (х_i ) = Г (x_i) ? Х_s. Таким образом, порож­денный подграф состоит из подмножества вершин Х_s множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству Х_s. Часто бывает удобно обозначать подграф С_s просто символом (X_s ).

На рис. 1.4(в) показан порожденный подграф графа, приведен­ного на рис. 1.4(а), содержащий только вершины х₁, х₂, х₃ и x₄ и дуги, которые их связывают.

Рис. 1.4. (а) Граф, (б) Остовный подграф. (в) Порожденный подграф, (г) Подграф.

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

Рассмотрим граф, вершины которого представляют сотрудни­ков некоторого учреждения, а дуги — линии связи между сотруд­никами. Тогда граф, представляющий только наиболее важные каналы связи данного учреждения, является остовным подграфом;. граф, который подробно представляет линии связи только какой то части этого учреждения (например, отделения), является порож­денным подграфом, а граф, который представляет только важные, линии связи в пределах отделения, является подграфом.

1.7. Типы графов

Граф G = (X, А) называют полным, если для любой пары вершин х_i и x_j в X существует ребро (х_i , х_j) в G = (X, А), т. е. для каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их. Полный неориентированный граф, построенный на п вершинах, обозначается через К_п

Граф (X, А) называется симметрическим, если в множестве дуг А для любой дуги (x_i , x_j ) существует также противоположно ориентированная дуга (х_j , х_i).

Антисимметрическим графом называется такой граф, для которого справедливо следующее условие: если (x_i, х_j) Є А, то в множестве А нет противоположно ориентированной дуги, т. е. (х_j, х_i) Є А. Очевидно, что в антисимметрическом графе нет петель.

На рис. 1.5(а) показан симметрический граф, а на рис. 1.5 (б) — антисимметрический граф.

Рис. 1.5. (а) Симметрический граф, (б) Антисимметрический граф, (в) Полный Симметрический граф, (г) Полный антисимметрический граф.

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

Неориентированный граф G = (X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Х^а и Х^ь, что каждое ребро имеет один конец в Х^а, а другой в Х^ь. Ориентированный граф G называется двудольным, если его неориентированный двойник — двудольный граф. Лег­ко доказать следующее утверждение.

Теорема 1. Неориентированный граф G является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство. Необходимость. Поскольку X разбивается на две части X^a и Х^ь, то

Пусть существует цикл нечетной длины х_i1 , x_i2, . . ., х_iq , х_i1 , и, без потери общности, допустим, что x_i1 Є X^a. Поскольку (соглас­но определению) одна из двух следующих друг за другом вершин этого цикла должна принадлежать Х^а, а другая Х^ь, то имеем х_i2 Є Х^ь, х_i3,Є Х^а и т. д. Следовательно, x_ik Є Х^а, если k - нечетное, и х_ik Є X^b , если k - четное. Мы предположили, что длина цикла нечетная. Поэтому из соотношения х_iq Є Х^а следует, что x_i1 Є Х^b. Это противоречит (1.13), поскольку X^a ? Х^ь = ? и вершина не может одновременно принадлежать как Х^а, так и Х^ь.

Достаточность. Предположим, что в графе G не существует цикла нечетной длины. Выберем одну из вершин, например x_i, и пометим ее плюсом « + ». Выполним следующую итерационную процедуру.

Берем уже помеченную вершину х_i и помечаем все вершины из множества Г (x_i) знаком, противоположным тому, который присвоен вершине х_i.

Будем продолжать эту операцию до тех пор. пока или

(i) все вершины не будут помечены, а знаки, приписанные им, согласованы (иными словами, любые две вершины, соединенные ребром, помечены противоположными знаками), или

(ii) некоторая вершина, например x_ik, которая была уже поме­чена каким-то знаком («+» или «—»), может быть помечена теперь (со стороны другой вершины) знаком, противоположным припи­санному вершине х_ik, или.

(iii) для каждой помеченной вершины x_i все вершины из мно­жества Г (x_i) уже помечены, но существуют другие, еще не поме­ченные вершины.

В случае (i) все вершины, помеченные знаком «+», отнесем к множеству Х^а, а помеченные знаком «—» — к множеству Х^ь. Поскольку все ребра соединяют вершины, помеченные противо­положными знаками, то граф является двудольным.

В случае (ii) вершина х_ik должна быть помечена знаком «+» на некотором маршруте (например, µ₁), состоящем из вершин х_i1 , х_i2 , . . ., х_ik; причем знаки «+» и «—», приписываемые этим вершинам при движении по маршруту µ_г (от вершины х_i1 к верши­не x_ik), должны образовывать чередующуюся последовательность (вида +, —, +, . . . или —, +, —, . . .). Аналогично знаком «—» вершина х_ik помечается вдоль некоторого маршрута µ₂. Пусть х* — предпоследняя (последней является х_ik ) общая вершина маршрутов µ₁ и µ₂. Если вершина х* помечена знаком «+», то участок от х* до х_i1 маршрута µ₁ должен быть четным, а участок от х* до х_ik маршрута µ₂ должен быть нечетным. Если же вершина х* помечена знаком «—», то участок маршрута µ₂ будет нечетным, а маршрута µ₁ — четным. Следовательно, цикл, состоящий из уча­стка маршрута µ₁, от х* до х_ik, и соответствующего участка мар­шрута µ₂, от х_ik до х*, имеет нечетную длину. Это противоречит предположению, что граф G не содержит циклов нечетной длины, и, значит, случай (ii) невозможен.

Случай (iii) означает, что между помеченной и не помеченной вершинами не существует ребра, т. е. что граф G распадается на две или больше частей, и каждая из них может тогда рассматри­ваться отдельно. Итак, в конце концов приходим к случаю (1) Теорема доказана.

Если нужно подчеркнуть, что граф является двудольным, то для графа применяют обозначение (Х^а U Х^ь, А), подразумевая, что выполняются также соотношения (1.13).

Двудольный граф G = (Х^а U Х^ь, А) называют полным, если для любых двух вершин х_i Є X^a и x_j Є Х^ь существует ребро (х_i, x_j) в G = (X, А). Если | Х^а | — число вершин множества Х^а — равно r и | Х^ь | = s, то полный неориентированный дву­дольный граф G = (Х^а и Х^ь, А) обозначается через К_rs.

Граф G = (X, А) называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произволь­ные две дуги графа не пересекаются друг с другом . На рис. 1.6(а) показан полный граф К₅, а на рис. 1.6(6) — полный двудольный граф К₃,₃, которые, как известно, являются непланарными [1, 3].

Рис. 1.6. Непланарные графы Куратовского. (а) К₅. (б) K_3.3

Эти два графа играют важную роль в теории пленарных графов и известны как графы Куратовского.

1.8. Сильно связные графы и компоненты графа

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

Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных вершин х_i и x_j существует по крайней мере один путь из х_i в х_j или из x_j в x_i

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

Если для некоторой пары вершин орграфа не существует марш­рута, соединяющего их, то такой орграф называется несвязным [2].

Граф, приведенный на рис. 1.7(а), как легко проверить, силь­но связный. Граф, показанный на рис. 1.7(6), не является силь­ным (так как в нем нет пути из х_г в х₃), но односторонне связный. Граф, изображенный на рис. 1.7(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от х_г к х₅ и от х₅ к а₂. Он — слабо связный. Наконец, граф, приведен­ный на рис. 1.7(г), является несвязным.

Пусть дано некоторое свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства Р называется порожденный подграф (Х_s) графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа (Х_s), у которого Х_s ) Х_s и который также обладает свойством Р. Так, например, если в качестве свойства Р взята

Рис. 1.7. (а) Сильно связный граф, (б) Односторонне связный граф, (в) Слабо связный граф, (г) Несвязный граф.

сильная связность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится в любом дру­гом сильном подграфе. Такой подграф называется сильной компо­нентой графа G. Аналогично, односторонняя компонента пред­ставляет собой односторонний максимальный подграф, а слабая компонента — максимальный слабый подграф.

Например, в графе G, приведенном на рис. 1.7(6), подграф ({x₁ , x₄ , x₅ , x₆ )) является сильной компонентой графа G. С дру­гой стороны, подграфы ({х₁, х₆}) и ({х₁ х₅, x₆}) не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе ({х₁, х₄ , х₅, х₆}) и, следова­тельно, не максимальные. В графе, показанном на рис. 1.7(в), подграф ({х₄, x₄,, х₅}} является односторонней компонентой. В графе, приведенном на рис. 1.7(г), оба подграфа ({х₁ , х₅ , х₆ }) и ({х₂ , х₃,, x₄}} являются слабыми компонентами, и у этого графа только две такие компоненты.

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

1.9. Матричные представления

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

А) Матрица смежности

Пусть дан граф G, его матрица смежности обозначается через А = [а_ij] и определяется следующим образом:

а_ij = 1, если в G существует дуга (x_i, x_j),

а_ij = 0, ,если в G нет дуги (x_i, x_j)

Таким образом, матрица смежности графа, изображенного на рис. 1.8, имеет вид

Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки х_i матрицы дает полу­степень исхода вершины х_i, а сумма элементов столбца х_i - полу­степень захода вершины х_i. Множество столбцов, имеющих 1 в стро­ке x_i, есть множество Г (х_i), а множество строк, которые имеют 1 в столбце x_i, совпадает с множеством Г^-1 (х_i ).

Возведем матрицу смежности в квадрат. Пусть элемент а_ik⁽²⁾ матрицы А² определяется по формуле

Слагаемое в уравнении (1.14) равно 1 тогда и только тогда, когда оба числа а_ij и a_jk равны 1, в противном случае оно равно О. Поскольку из равенств а_ij = a_jk = 1 следует существование пути длины 2 из вершины х_i
к вершине х_k, проходящего через вершину x_i, то а_ik⁽²⁾ равно числу путей длины 2, идущих из х_i в x_k.

Рис.1.8.

Б). Матрица инциденций

1 Пусть дан граф G с п вершинами и т дугами. Матрица инци­денций графа G обозначается через В = [b_ij] и является матрицей размерности п х т, определяемой следующим образом:

b_ij = 1, если x_i является начальной вершиной дуги a_j,

b_ij = —1, если x_i является конечной вершиной дуги a_j,

b_ij = 0, если x_i не является концевой вершиной дуги a_j или если a_j, является петлей.

Для графа, приведенного на рис.1.8, матрица инциденций имеет вид

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один — равный —1, либо все элементы столбца равны 0.

Если G является неориентированным графом, то его матрица инциденций определяется так же, как и выше, за исключением того, что все элементы, равные —1, заменяются на +1.

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

Предположим, что в начальной матрице весов с_ii = 0 для всех i = 1, 2, .... n и с_ij = ?, если в графе отсутствует дуга (х_i, х_j).

Присвоение начальных значений

Шаг 1. Положить k = 0.

Итерация

Шаг 2. k = k + 1.

Шаг 3. Для всех i?k, таких, что c_ik ? ?, и для всех j?k, таких, что с_kj ?? введем операцию

с_ij = min[с_ii, (с_ik + с_kj)]. (*)

Проверка на окончание

Шаг 4. (а) Если с_ii <0, то в графе G существует цикл отрица­тельного веса, содержащий вершину х_i, и решения нет. Останов.

(б) Если все с_ii >= 0 и k = п, то получено решение. Матрица [с_ij] дает длины всех кратчайших путей. Останов.

(в) Если все с_ii >= 0, но k < п, то вернуться к шагу 2.

Доказательство оптимальности ответа, полученного с помощью

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

Заключение

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

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

Библиография

1.Белецкая С.Ю. Основы дискретной математики: Учебное пособие. Воронеж: Воронежский институт высоких технологий, 2004.-104 с.

2.Кристофидес Н. Теория графов: алгоритмический подход. Москва: Мир, 1978. 427 с.

3.Немнюгин С.А. Turbo Pascal.-Санкт-Петербург, Питер, 2002.-496 с.: ил.

Приложение

Листинг программы:

Program Floyd;

uses crt;

type mas=array[1..10,1..10] of integer;

var

w0,w:mas;

p:array[0..9,1..10,1..10] of integer;

i,j,k,n:integer;

Procedure Get(var i,j :integer);

var I : integer;

begin

for I:=n downto 1 do begin

if p[I, i, j]=p[I-1, i, j] then continue

else write(‘-‘,p[I, i, j];

end;

write(‘-‘,j);

end;

begin

clrscr;

write(‘Сколько вершин?’);readln(n);

k:=0;

write(‘Введите матрицу весов (если пути нет пишите 99):’);

for i:=1 to n do

for j:=1 to n do begin

GotoXY(j*3,i+3);

read(w0[i,j]);

end;

for i:=1 to n do

for j:=1 to n do

if i=j then p[k,i,j]:=0

else p[k,i,j]:=i;

repeat

inc(k);

for i:=1 to n do

for j:=1 to n do

if w0[i,k]+w0[k,j]

w[i,j]:=w0[i,k]+w0[k,j];

p[k,i,j]:=p[k-1,k,j];

end

else begin

w[i,j]:=w0[i,j];

p[k,i,j]:=p[k-1,i,j];

end;

w0:=w;

until k=n;

for i:=1 to n do

for j:=1 to n do

if <> j then begin

write(i,’и’,j,’:L(‘,i,’,’,j,’)=’,w[i,j],’,путь:’,i);

Get(i,j);

writeln;

end;

readln;

readln;

end.