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

Содержание Введение….1.Основные понятия…1.Графы. Определения….2.Пути и маршруты…3.Веса и длина пути… 4.Петли и ориентированные циклы… 5.Степени вершины…6.Подграфы…7.Типы графов…8.Сильносвязные графы и компоненты графа……9.Матричные представления… 2.Алгоритм Флойда…17 Заключение…18 Библиография… 19 Приложение1: Листинг программы…….… 20

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

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

сети и системы связи, приводит к графам большого размера, успешный анализ которых зависит в равной степени как от существования «хороших» алгоритмов, так и от возможности использования быстродействующих вычислительных машин. 1.Основные понятия 1.Графы. Определения Граф G задается множеством точек или вершин x1, х2 ……, хn (которое обозначается через X) и множеством линий или ребер a1, а2……, аn (которое обозначается символом

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

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

1.1(а) обо¬значение (х1, х2) относится к дуге а2 , а (х2 х1) — к дуге а2. Другое, употребляемое чаще описание ориентированного гра¬фа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответ¬ствие Г называется отображением множества

X в X, а граф в этом случае обозначается парой G = (X, Г). Для графа на рис. 1.1(а) имеем Г (x1) = {х2 х5}, т. е. вершины х2 и х5 являются конечными вершинами дуг, у которых начальной вершиной является х1. Г(x2)={x1, x3}, Г(x3)={x1}, Г(x4)=Ø-пустое множество, Г(x5)={x4} Рис. 1.1. (а) Ориентированный граф, (б) Неориентированный граф, (в)

Сме¬шанный граф. В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см например, графы, изобра¬женные на рис. 1.1(6) и 1.1(в)), предполагается, что соответствие Г задает такой эквивалентный, ориентированный граф, который получается из исходного графа заменой каждого неориентиро¬ванного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис. 1.1(6), имеем

Г (х5) = {х1, х3 x4}, Г (х1) = {х5} и т. д. Поскольку Г (x1) представляет собой множество таких вершин xi Є Х, для которых в графе G существует дуга (хi, xj), то через Г-1(xi) естественно обозначить множество вершин хk, для которых в G существует дуга (хk, xi). Отношение Г-1 (хi) принято называть обратным соответствием.

Для графа, изображенного на рис 1.1 (а), имеем Г-1(x1)={x2. x3}, Г-1(x2)={x1}, и т. д. Вполне очевидно, что для неориентированного графа Г-1(xi) = Г (хi) для всех х1 Є X. Когда отображение Г действует не на одну вершину, а на мно¬жество вершин Хq = {х1, x2, …, хq}, то под Г (Хq) понимают объединение

Г(x1) U Г(x2) U…U Г(xq), т. е. Г (Хq) является множеством таких вершин хi Є X, что для каждой из них существует дуга (хi, хj,) в G, где хi Є Хq. Для гра¬фа, приведенного на рис. 1.1(а), Г ({x2, х5}) = {х1, х3 x4} и Г ({x1, х3}) = {х2 х5, х1} Отображение Г (Г (xi)) записывается как Г2 (xi). Аналогично «тройное» отображение

Г (Г (Г (хi))) записывается как Г3 (xi) и т. д. Для графа, показанного на рис. 1.1(а), имеем: Г2 (x1) = Г (Г (x1)) = Г ({х2 x5}) = {х1, х3 x4}, Г3(x1)=Г(Г2(x1))=Г({x1, x3, x4})={x1, x3, x5} и т. д. Аналогично понимаются обозначения Г-2 (хi), Г-3 (хi) и т. Д 2. Пути и маршруты Путем (или ориентированным маршрутом) ориентированного графа называется последовательность

дуг, в которой конечная вершина всякой дуги, отличной от последней, является началь¬ной вершиной следующей. Так, на рис. 1.2 последовательности дуг a6 , a5 , a9 , a3 , a4 , (1.1) a1 , a6 , a5 , a9 , (1.2) a1 , a6 , a5 , a9 , a10 , a6 , a4 , (1.3) являются путями. Рис. 2. Дуги а = (xi , xj), xi ≠ xj , имеющие общие концевые вершины, называются смежными. Две вершины хi и xj называются смежными, если какая-нибудь из двух дуг (хi , хj) и (xj , xi) или обе

одно¬временно присутствуют в графе. Так, например, на рис. 1.2 дуги a1, a10, a3 и a6 как и вершины х5 и x3, являются смежными, в то время как дуги аг и a5 или вершины х1 и x4 не являются смежными. Ориентированной цепью (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являют¬ся орцепями, а путь (1.3) не является таким,

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

Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последова¬тельность ребер a1, а2 аq, в которой каждое ребро аi , за исключением, возможно, первого и последнего ребер, связано с ребрами аi-1 и аi+1 своими двумя концевыми вершинами. После¬довательности дуг а2 , а4 , а8 , а10 , (1.4) а2 , а7 , а8 , а4 , а3 (1.5) а10 , а7 , а4 , а8 , а7, а2 (1.6) в графе, изображенном на рис.

1.2, являются маршрутами. Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи 1) и простые цепи 2). Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) — цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью. Путь или маршрут можно изображать также последователь¬ностью вершин, что мы и будем использовать. Путь (1.1) можно представить также последовательностью вершин х2 , х5 , x4, х3, х5 , х6 и такое представление

часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей пли простых цепей. 1.3. Веса и длина пути Иногда дугам графа G сопоставляются (приписываются) чис¬ла — дуге (хi , xj ) ставится в соответствие некоторое число сi j , называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа VI) приписываются вершинам хi графа, и тогда полу¬чается граф с взвешенными вершинами.

Если в графе веса при¬писаны и дугам, и вершинам, то он называется просто взвешен¬ным . При рассмотрении пути µ , представленного последовательно¬стью дуг (a1, а2 а3), за его вес (или длину) принимается число ι (μ), равное сумме весов всех дуг, входящих в μ , т. е. ι (μ) = ∑ cij (xi , xj) Є μ Таким образом, когда слова «длина», «стоимость», «цена» и «вес» применяются к дугам, то

они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое ближе подходит по смыслу и совпадает с принятым в литературе. Длиной (или мощностью) пути µ называется число дуг, входя¬щих в него . 1.4. Петли, ориентированные циклы Петлей называется дуга, начальная и конечная вершины кото¬рой совпадают. На рис. 1.3, например, дуги а2 и а5 являются пет¬лями.

Путь a1, a2,… аq называется замкнутым, если в нем начальная вершина дуги а1 совпадает с конечной вершиной дуги аq. Так, например, в графе, приведенном на рис. 1.3, последова¬тельности дуг a3 , a6 , a11 , (1.7) a11 , a3 , a4 , a7 , a1 , a12 , a9 , (1.8) a3 , a4 , a7 , a10 , a9 , a11 , (1.9) являются замкнутыми путями. Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку

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

1.3, а граф на рис. 1.2 не имеет гамильтоновых контуров, поскольку не существует такой дуги, для которой х1 была бы конечной вершиной. Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом х1, х2 хq , в котором совпадают начальная и конечная вершины, т. е. в котором х1 = хq . На рис. 1.3 маршруты a1 , a12 , a10 , (1.10) и a10 , a1 , a3 , a4 , a7 , a1 , a12 (1.11) являются замкнутыми маршрутами.

1.5. Степени вершины Число дуг, которые имеют вершину хi своей начальной верши¬ной, называется полустепенъю исхода вершины хi , и, аналогично, число дуг, которые имеют xi своей конечной вершиной, называется полустепенъю захода вершины xi . Таким образом, на рис. 1.3 полустепень исхода вершины х6 , обозначаемая через d0 (х6 ), равна | Г (х6) | = 2, и полустепень захода вершины х6 , обозначаемая через dt (х6 ), равна | Г-1 (х) │ = 1. Совершенно очевидно, что сумма полустепеней захода всех вершин графа, а также

сумма полустепеней исхода всех вершин равны общему числу дуг графа G, т.е. где n — число вершин и m— число дуг графа G. Для неориентированного графа G = (X, Г) степень вершины хi определяется аналогично — с помощью соотношения d (xi) ≡ | Г (xi) | 1.6. Подграфы Пусть дан граф G = (X, А). Остовным подграфом Gр гра¬фа G называется граф (X,

Аp), для которого Ар c А. Таким обра¬зом, остовный подграф имеет то же самое множество вершин, что и граф G, но множество дуг подграфа Gр является подмножеством множества дуг исходного графа. Граф на рис. 1.4(6) — остовный подграф Ор графа С, изобра¬женного на рис. 1.4(а). Пусть дан граф G = (X, Г). Порожденным подграфом Gs, называется граф (Хs, Гs), для которого Хs c X и для каждой вершины

Xi Є Xs, Гs (хi ) = Г (xi) ∩ Хs. Таким образом, порож¬денный подграф состоит из подмножества вершин Хs множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству Хs. Часто бывает удобно обозначать подграф Сs просто символом (Xs ). На рис. 1.4(в) показан порожденный подграф графа, приведен¬ного на рис.

1.4(а), содержащий только вершины х1, х2, х3 и x4 и дуги, которые их связывают. Рис. 1.4. (а) Граф, (б) Остовный подграф. (в) Порожденный подграф, (г) Подграф. Соединяя приведенные выше два определения, можно сформу¬лировать определение подграфа. Граф, показанный на рис. 1.4(г), является подграфом графа, приведенного на рис. 1.4(а). Рассмотрим граф, вершины которого представляют сотрудни¬ков некоторого учреждения, а дуги —

линии связи между сотруд¬никами. Тогда граф, представляющий только наиболее важные каналы связи данного учреждения, является остовным подграфом;. граф, который подробно представляет линии связи только какой то части этого учреждения (например, отделения), является порож¬денным подграфом, а граф, который представляет только важные, линии связи в пределах отделения, является подграфом. 1.7. Типы графов Граф G = (X, А) называют полным, если для любой пары вершин хi и xj в

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

Антисимметрическим графом называется такой граф, для которого справедливо следующее условие: если (xi, хj) Є А, то в множестве А нет противоположно ориентированной дуги, т. е. (хj, хi) Є А. Очевидно, что в антисимметрическом графе нет петель. На рис. 1.5(а) показан симметрический граф, а на рис. 1.5 (б) — антисимметрический граф. Рис. 1.5. (а) Симметрический граф, (б)

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

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

Неориентированный граф G является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Доказательство. Необходимость. Поскольку X разбивается на две части Xa и Хь, то Пусть существует цикл нечетной длины хi1 , xi2 хiq , хi1 , и, без потери общности, допустим, что xi1 Є Xa. Поскольку (соглас¬но определению) одна из двух следующих друг за другом вершин этого цикла должна принадлежать Ха, а другая Хь, то имеем хi2

Є Хь, хi3,Є Ха и т. д. Следовательно, xik Є Ха, если k - нечетное, и хik Є Xb , если k - четное. Мы предположили, что длина цикла нечетная. Поэтому из соотношения хiq Є Ха следует, что xi1 Є Хb. Это противоречит (1.13), поскольку Xa ∩ Хь = Ø и вершина не может одновременно принадлежать как

Ха, так и Хь. Достаточность. Предположим, что в графе G не существует цикла нечетной длины. Выберем одну из вершин, например xi, и пометим ее плюсом « + ». Выполним следующую итерационную процедуру. Берем уже помеченную вершину хi и помечаем все вершины из множества Г (xi) знаком, противоположным тому, который присвоен вершине хi. Будем продолжать эту операцию до тех пор. пока или (i) все вершины не будут помечены, а знаки, приписанные

им, согласованы (иными словами, любые две вершины, соединенные ребром, помечены противоположными знаками), или (ii) некоторая вершина, например xik, которая была уже поме¬чена каким-то знаком («+» или «—»), может быть помечена теперь (со стороны другой вершины) знаком, противоположным припи¬санному вершине хik, или. (iii) для каждой помеченной вершины xi все вершины из мно¬жества Г (xi) уже помечены, но существуют другие, еще не поме¬ченные вершины.

В случае (i) все вершины, помеченные знаком «+», отнесем к множеству Ха, а помеченные знаком «—» — к множеству Хь. Поскольку все ребра соединяют вершины, помеченные противо¬положными знаками, то граф является двудольным. В случае (ii) вершина хik должна быть помечена знаком «+» на некотором маршруте (например, µ1), состоящем из вершин хi1 , хi2 хik; причем знаки «+» и «—», приписываемые этим вершинам при движении по маршруту µг (от вершины хi1 к верши¬не xik), должны образовывать чередующуюся

последовательность (вида +, —, + или —, +, — .). Аналогично знаком «—» вершина хik помечается вдоль некоторого маршрута µ2. Пусть х* — предпоследняя (последней является хik ) общая вершина маршрутов µ1 и µ2. Если вершина х* помечена знаком «+», то участок от х* до хi1 маршрута µ1 должен быть четным, а участок от х* до хik маршрута µ2 должен быть нечетным. Если же вершина х* помечена знаком «—», то участок маршрута

µ2 будет нечетным, а маршрута µ1 — четным. Следовательно, цикл, состоящий из уча¬стка маршрута µ1, от х* до хik, и соответствующего участка мар¬шрута µ2, от хik до х*, имеет нечетную длину. Это противоречит предположению, что граф G не содержит циклов нечетной длины, и, значит, случай (ii) невозможен. Случай (iii) означает, что между помеченной и не помеченной вершинами не существует ребра, т. е. что

граф G распадается на две или больше частей, и каждая из них может тогда рассматри¬ваться отдельно. Итак, в конце концов приходим к случаю (1) Теорема доказана. Если нужно подчеркнуть, что граф является двудольным, то для графа применяют обозначение (Ха U Хь, А), подразумевая, что выполняются также соотношения (1.13). Двудольный граф G = (Ха U Хь, А) называют полным, если для любых двух вершин хi

Є Xa и xj Є Хь существует ребро (хi, xj) в G = (X, А). Если | Ха | — число вершин множества Ха — равно r и | Хь | = s, то полный неориентированный дву¬дольный граф G = (Ха и Хь, А) обозначается через Кrs. Граф G = (X, А) называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произволь¬ные

две дуги графа не пересекаются друг с другом . На рис. 1.6(а) показан полный граф К5, а на рис. 1.6(6) — полный двудольный граф К3,3, которые, как известно, являются непланарными [1, 3]. Рис. 1.6. Непланарные графы Куратовского. (а) К5. (б) K3.3 Эти два графа играют важную роль в теории пленарных графов и известны как графы

Куратовского. 1.8. Сильно связные графы и компоненты графа Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин хi и xj существует по край¬ней мере один путь, соединяющий хi с xj. Это определение означает также, что любые две вершины такого графа взаимно достижимы. Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных

вершин хi и xj существует по крайней мере один путь из хi в хj или из xj в xi Ориентированный граф называют слабо связным или слабым, если для любых двух различных вершин графа существует по край¬ней мере один маршрут, соединяющий их. Если для некоторой пары вершин орграфа не существует марш¬рута, соединяющего их, то такой орграф называется несвязным [2]. Граф, приведенный на рис. 1.7(а), как легко проверить, силь¬но связный.

Граф, показанный на рис. 1.7(6), не является силь¬ным (так как в нем нет пути из хг в х3), но односторонне связный. Граф, изображенный на рис. 1.7(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от хг к х5 и от х5 к а2. Он — слабо связный. Наконец, граф, приведен¬ный на рис. 1.7(г), является несвязным. Пусть дано некоторое свойство Р, которым могут обладать графы.

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

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

G, приведенном на рис. 1.7(6), подграф ({x1 , x4 , x5 , x6 )) является сильной компонентой графа G. С дру¬гой стороны, подграфы ({х1, х6}) и ({х1 х5, x6}) не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе ({х1, х4 , х5, х6}) и, следова¬тельно, не максимальные. В графе, показанном на рис. 1.7(в), подграф ({х4, x4 х5}} является односторонней компонентой. В графе, приведенном на рис. 1.7(г), оба подграфа ({х1 , х5 , х6 }) и ({х2 , х3 x4}} являются слабыми

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

А) Матрица смежности Пусть дан граф G, его матрица смежности обозначается через А = [аij] и определяется следующим образом: аij = 1, если в G существует дуга (xi, xj), аij = 0, ,если в G нет дуги (xi, xj) Таким образом, матрица смежности графа, изображенного на рис. 1.8, имеет вид Матрица смежности полностью определяет структуру графа.

Например, сумма всех элементов строки хi матрицы дает полу¬степень исхода вершины хi, а сумма элементов столбца хi - полу¬степень захода вершины хi. Множество столбцов, имеющих 1 в стро¬ке xi, есть множество Г (хi), а множество строк, которые имеют 1 в столбце xi, совпадает с множеством Г-1 (хi ). Возведем матрицу смежности в квадрат. Пусть элемент аik(2) матрицы А2 определяется по формуле Слагаемое в уравнении (1.14) равно 1 тогда и только тогда, когда оба числа

аij и ajk равны 1, в противном случае оно равно О. Поскольку из равенств аij = ajk = 1 следует существование пути длины 2 из вершины хi к вершине хk, проходящего через вершину xi, то аik(2) равно числу путей длины 2, идущих из хi в xk. Рис.1.8. Б). Матрица инциденций 1 Пусть дан граф G с п вершинами и т дугами. Матрица инци¬денций графа G обозначается через В = [bij] и является матрицей размерности п х т, определяемой

следующим образом: bij = 1, если xi является начальной вершиной дуги aj, bij = —1, если xi является конечной вершиной дуги aj, bij = 0, если xi не является концевой вершиной дуги aj или если aj, является петлей. Для графа, приведенного на рис.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, таких, что cik ≠ ∞, и для всех 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]

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.