Равносильность формул логики предикатов

Пусть формулы А и В имеют одно и то же множество свободных переменных.

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

Определение. Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М..

Определение. Формулы А и В равносильны в логике предикатов, если они равносильны на всех множествах (АºВ).

Укажем несколько правил перехода от одних формул к другим, им равносильным.

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

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

Кроме этого, существуют следующие правила:

1. Перенос квантора через отрицание

2. Вынос квантора за скобки

 

3. Перестановка одноименных кванторов

"х "у А(х, у) º "у "х А(х, у),

$х $у А(х, у) º $у $х А(х, у).

4. Переименование связанных переменных.

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

Определение. Формула А, равносильная формуле В, и не содержащая символов ®,», а также составных формул под знаком отрицания, называется приведенной формой формулы В.

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

Пример 66.

Преобразовать в приведенную форму формулу .

Решение.

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

Пример 67.

Преобразовать в ПНФ формулы:

1. ;

2. .

Решение.

1.

 

2.

 

 

3. ТЕОРИЯ ГРАФОВ

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

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

 

3.1. Основные определения

Определение. Пара (V(G), E(G)) называется простым графом, если V(G) – непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). В простом графе данную пару вершин может соединять не более чем одно ребро.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v₁, v₂, если оно соединяет эти вершины и наоборот, каждая из вершин v₁, v₂ инцидентна ребру е.

Рассмотрим графическое представление графов (табл. 66).

Таблица 66

Графическое представление графов

№	Элементы графов	Геометрические элементы
1.	х Î Х – вершина	- точка в пространстве
2.	(vi, vj) Î V Ù (vi, vj) Ï V	- направленный отрезок, ориентированное ребро
3.	(vi, vj) Î V Ù (vi, vj) Î V	- отрезок, неориентированное ребро
4.	(vi, vi) Î V	- замкнутый отрезок, петля

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

Пример 68.

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

Иногда удобно преобразовать неориентированный граф в ориентированный – заменой одного неориентированного ребра парой ребер с противоположной ориентацией.

Приведем ряд понятий и определений для ориентированных и неориентированных графов. Там, где это специально не оговорено, те же понятия и определения переносятся без изменений на ориентированные и неориентированные псевдографы.

 

3.1.1. Смежность, инцидентность, степени

Определение. Если е = {v, w} – ребро графа, то вершины v, w называются концами ребра е; в этом случае также говорят, что ребро е соединяет вершины v, w.

Определение. Если е = {v, w} – дуга орграфа, то вершина v называется началом, а вершина w – концом дуги е; в этом случае также говорят, что дуга е исходит из вершины v и заходит в вершину w.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.

Определение. Две вершины называются смежными, если существует ребро, концами которого они являются. Два ребра называются смежными, если они имеют общую вершину.

Определение. Степенью вершины v графа G называется число d(v) ребер графа, которым инцидентна эта вершина.

Определение. Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.

Замечание. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Определение. Полустепенью исхода (захода) вершины v орграфа D называется число d⁺(v) (d ^-(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

Замечание. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d⁺(v), так и в d ^-(v).

Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).

Утверждение. Для любого псевдографа G выполняется равенство

Утверждение. Для любого ориентированного псевдографа D выполняется равенство

Пример 69.

Найти локальные степени графа (рис. 19) и орграфа (рис. 20).

Решение.

d ^+(u) = 1;	d ^-(u) = 1;
d ^+(v) = 2;	d ^-(v) = 0;
d ^+(z) = 0;	d ^-(z) = 3;
d ^+(m) = 1;	d ^-(m) = 0.

d (u) = 2;

d (v) = 2;

d (z) = 3;

d (m) = 1.

3.1.2. Изоморфизм, гомеоморфизм

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

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

Изоморфизм графов есть отношение эквивалентности.

Пример 70.

На рисунке 21 изображены три изоморфных графа. На рисунке 22 изображены два неизоморфных графа.

 

 

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример 71.

С точностью до изоморфизма существует ровно четыре простых графа с тремя вершинами и одиннадцать с четырьмя вершинами. Постройте эти графы.

Решение.

1. Построим четыре простых графа с тремя вершинами с точностью до изоморфизма (рис. 23):

2. Построим одиннадцать простых графов с четырьмя вершинами с точностью до изоморфизма (рис. 24):

Определение. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение. Орграф D₁ называется подразбиением орграфа D₂, если орграф D₁ можно получить из D₂ путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Определение. Орграфы D₁, D₂ называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

3.1.3. Матричное задание графов. Матрицы смежности, инцидентности

Пусть D = (V, Х) – орграф, где V={v₁, v₂, …,v_n}, X={x₁, x₂, …, x_m}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[a_ij] порядка n, у которой

Определение. Матрицей инцидентности орграфа D называется (n´m) –матрица B(D)=[b_ij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v₁, v₂, …,v_n}, X={x₁, x₂, …, x_m}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[a_ij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (n´m) –матрица B(G)=[b_ij], у которой

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).

Решение.

Матрица смежности имеет вид

.

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

Для того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 26). Матрица инцидентности имеет вид:

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

Пример 73.

Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 27).

Решение.

Матрица смежности имеет вид:

Матрица инцидентности имеет вид

 

3.1.4. Примеры графов. Операции над графами

Рассмотрим некоторые важные типы графов.

Определение. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают N_n.

Заметим, что у вполне несвязного графа все вершины изолированы.

Определение. Простой граф, в котором любые две вершины смежны, называется полным. Полный граф обозначают К_n.

Пример 74.

 

Заметим, что для полного графа выполняется равенство , где m – число ребер, n – число вершин графа.

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

Регулярные графы степени 3 называются кубическими (или трехвалентными).

Пример 75.

Известным примером кубического графа является граф Петерсона (рис. 29).

 

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

Пример 76.

На рис. 30 приведен граф, соответствующий кубу.

Определение. Допустим, что множество вершин графа G можно разбить на два непересекающихся подмножества V₁ и V₂ так, что каждое ребро в G соединяет какую-нибудь вершину из V₁ с какой-нибудь вершиной из V₂, тогда данный граф называется двудольным.

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

Определение. Если в двудольном графе каждая вершина из V₁ соединена с каждой вершиной из V₂, то граф называется полным двудольным.

Обозначение. К_{m. n}

Заметим, что граф К_{m. n} имеет ровно m + n вершин и mn ребер.

Пример 77.

На рис. 31 изображены двудольные графы.

Определение. Объединением графов называется граф

Определение. Пересечением графов , где , называется граф

Определение. Соединением графов G₁ и G₂ является новый граф, у которого V=V₁ÈV₂, а множеством ребер являются все ребра первого и второго графа и ребра, соединяющие между собой каждую вершину первого графа с первой вершиной второго графа.

Определение. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

Очевидно, что всякий несвязный граф можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой связности графа.

Определение. Связный регулярный граф степени 2 называется циклическим графом. Обозначается С_n (рис. 32).

Определение. Соединение графов N₁ и C_n-1 (n³3) называется колесом с n вершинами. Обозначается W_n (рис. 32).

Пример 78.

 

Определение. Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

Обозначение.

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

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

 

3.1.5. Маршруты, цепи, циклы

Введем понятие маршрута для графа G = (V, E) (и соответственно понятие пути для орграфа D = (V, E)).

Определение. Маршрутом в данном графе G называется конечная последовательность ребер вида {v₀, v₁}, {v₁, v₂}, …, {v_m-1, v_m} (обозначаемая также v₀®v₁®v₂®…®v_m).

Каждому маршруту соответствует последовательность вершин v₀v₁v₂…v_m; v₀ – начальная вершина, а v_m – конечная вершина маршрута.Одна и та же вершина может одновременно оказаться начальной, конечной и внутренней. Таким образом, мы будем говорить о маршруте из v₀ в v_m.

Определение. Длиной маршрута называется число ребер в нем.

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

Определение. Цепь или простая цепь замкнуты, если начальная и конечная вершины совпадают.

Определение. Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

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

3.1.6. Связность. Компоненты связности

Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w(маршрут, соединяющий v, w).

Дадим более удобное определение связных графов.

Определение. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

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

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

Определение. Если граф не является связным, то он называется несвязным.

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

В дальнейшем количество компонент связности графа будем обозначать k.

Пример 79.

Данный граф не является связным: k = 3.

 

Данный граф является связным: k = 0.

 

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

 

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

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

Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Пример 80.

Для графа, изображенного на рис.33, каждое из множеств {e₁, e₂, e₅} и {e₃, e₆, e₇, e₈} является разделяющим.

Разрезом является множество ребер {e₁, e₂}.

В графе возможно выделить несколько разделяющих множеств и разрезов.

 

3.2. Задачи поиска маршрутов (путей) в графе (орграфе)

3.2.1. Поиск путей (маршрутов) с минимальным числом дуг (ребер)

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

Рассмотрим более сложную задачу: нахождение пути (маршрута) с минимальным числом дуг (ребер).

Определение.Путь в орграфе D из вершины v в вершину w, где v ¹ w, называется кратчайшим, если он имеет минимальную длину среди всех путей орграфа D из v и w. Аналогично определяется и кратчайший маршрут в графе G.

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

Рассмотрим задачу поиска минимального пути (маршрута). Введем некоторые обозначения. Пусть D=(V, X) – орграф, vÎV, V₁ÌV. Обозначим D(v)={wÎV| (v, w)ÎX} – образ вершины v; D^-1(v)={wÎV| (w,v)ÎX} – прообраз вершины v; - образ множества вершин V₁; - прообраз множества вершин V₁. Пусть G=(V, X) – граф, vÎV, V₁ÌV. Обозначим G(v)={wÎV|{v, w}ÎX} – образ вершины v; - образ множества вершин V₁.

Пусть D=(V, X) – орграф с n ³ 2 вершинами и v, w – заданные вершины из V, где v ¹ w. Опишем алгоритм поиска кратчайшего пути из v в w в орграфе D.

Алгоритм фронта волны.

Шаг 1. Помечаем вершину v индексом 0. Затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначаем FW₁(v). Полагаем k=1.

Шаг 2. Если FW_k(v)=Æ или выполняется k=n-1, wÏFW_k(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.

Шаг 3. Если wÏFW_k(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является кратчайшим. Последовательность вершин

vw₁w₂…w_k-1w, где

и есть искомый кратчайший путь из v и w. На этом работа алгоритма заканчивается.

Шаг 4. Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем FW_k+1(v). Присваиваем k:=k+1 и переходим к шагу 2.

Замечание. Множество FW_k(v) обычно называют фронтом волны k -го уровня.

Замечание. Вершины w₁w₂…w_k-1, вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных кратчайших путей из v и w.

Пример 81.

Определить кратчайший путь из v₁ и v₆ в орграфе D, заданном матрицей смежности (табл. 67).

Таблица 67

	v1	v2	v3	v4	v5	v6
v1	0	0	0	1	1	0
v2	1	0	0	1	1	1
v3	1	1	0	1	1	1
v4	0	1	1	0	1	0
v5	1	1	1	1	0	0
v6	1	1	1	1	1	0

Решение.

Согласно алгоритму Фронта волны, последовательно определяем

FW₁(v₁) = {v₄, v₅};

FW₂(v₁) = D(FW₁(v₁))\{v₁, v₄, v₅} = {v₂, v₃};

FW₃(v₁) = D(FW₂(v₁))\{v₁, v₂, v₃, v₄, v₅} = {v₆}.

Таким образом, v₆ Î FW₃(v₁), а значит, существует путь из v₁ в v₆ длины 3, и этот путь является кратчайшим. Найдем теперь кратчайший путь из v₁ в v₆. Определим множество

Выберем любую вершину из найденного множества, например вершину v₃. Определим далее множество

Выберем любую вершину из найденного множества, например вершину v₅. Тогда v₁v₅v₃v₆ – искомый кратчайший путь из v₁ в v₆ (длины 3) в орграфе D.

 

3.2.2. Расстояния в графе. Диаметр, центр, радиус графа

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w. Это расстояние удовлетворяет аксиомам метрики:

1. d(v, w) ³ 0, причем d(v, w) = 0 тогда и только тогда, когда v=w;
2. d(v, w) = d(w, v);
3. d(v, w) £ d(v, u) + d(u, w).

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

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

Пример 82.

Для графа G, изображенного на рисунке 34, найти радиус, диаметр и центры.

Решение.

Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами d_ij которой будут расстояния между вершинами v_i и v_j. Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5. В результате получаем: r(v₁) = 3, r(v₂) = 2, r(v₃) = 2, r(v₄) = 2, r(v₅) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v₂, v₃, v₄.

 

3.2.3. Нахождение минимального пути в нагруженном графе

Определение. Назовём орграф нагруженным, если на множестве дуг определена некоторая функция , которую часто называют весовой функцией.

Тем самым и нагруженном орграфе каждой дуге поставлено в соответствие некоторое дей­ствительное число . Значение будем называть длиной дуги .

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

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

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

Пусть - нагруженный орграф, , . Введем величины , где ,..., , , ,... Для каж­дых фиксированных и величина равна длине минималь­ного пути среди путем из в , содержащих не более дуг; если же таких путей нет, то = . Кроме того, если произ­вольную вершину считать путем из в нулевой длины, то величины можно ввести также и для , при этом

(1)

Введем также в рассмотрение квадратную матрицу порядка с элементами

которую будем называть матрицей длин дуг нагруженного орграфа .

Следующее утверждение дает простые формулы для вычисле­ния величин .

Утверждение.

.

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

Алгоритм Форда – Беллмана нахождения минимального пути в нагруженном орграфе из в

Шаг 1. Пусть мы уже составили таблицу величин . Если не достижима из (предполагаем, что все величины конечны). В этом случае работа алгоритма заканчивается.

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

Шаг 3. Последовательно определяем номера такие что

...... (4)

Из (4) с учётом того, что , имеем , откуда, используя (1), получаем

(5)