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

Классификация формул логики предикатов

Сформулируем классификационные определения для формул логики предикатов. Рассмотрим некоторую интерпретацию с множеством М.

Определение. Формула А выполнима в данной интерпретации, если существует набор <a₁, …, a_n>, a_iÎ M, значений свободных переменных x_i1, …, x_in формулы А такой, что А|<a₁, …, a_n>=И.

Определение. Формула А истинна в данной интерпретации, если она принимает значение И на любом наборе <a₁, …, a_n>, a_iÎ M, значений своих свободных переменных x_i1, …, x_in.

Определение. Формула А выполнима (в логике предикатов), если существует интерпретация, в которой А выполнима.

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

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

Аналогично вводятся понятия опровержимого и тождественно-ложного предиката.

Пример 64.

Выяснить является ли формула выполнимой и опровержимой: .

Решение.

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

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

1. Зададим множество М = {0}.
2. Зададим предикат Р(х, у): «х = у».
3. Поскольку заданное множество М имеет единственные элемент, то свободному вхождению переменной у припишем значение 0.

При такой интерпретации данная формула обращается в истинное высказывание.

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

Значит, исходная формула является выполнимой.

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

1. Зададим множество М = N.
2. Зададим предикат Р(х, у): «х < у».
3. Свободному вхождению переменной у припишем значение 5.

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

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

Значит, исходная формула является опровержимой.

Пример 65.

Доказать общезначимость формулы "х Р(х) ® $х Р(х).

Решение.

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

Таким образом, исходная формула "х Р(х) ® $х Р(х) общезначима.

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

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

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

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

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

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

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

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

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) = 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

Решение.

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

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)

Складывая равенства (4) и учитывая (5), имеем

т.е. - искомый минимальный путь из в в нагруженном орграфе . Заметим, что в этом пути ровно дуг Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном оргра­фе .

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

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

Пример 83.

Определить минимальный путь из v₁ в v₆ в нагруженном орграфе D, изображенном на рисунке 35.

Решение.

Составим матрицу C(D) длин дуг нагруженного орграфа D (табл. 68). Справа от матрицы C(D) припишем шесть столбцов, которые будем определять, используя рекуррентное соотношение (2) и исходя из (1).

Величина выражает длину минимального пути из v₁ в v₆ в нагруженном орграфе D. Найдем минимальное число , при котором выполняется равенство . Получаем, что k₁ = 4. Таким образом, минимальное число дуг в пути среди всех минимальных путей из v₁ в v₆ в нагруженном графе D равняется 4. Определим теперь последовательность номеров i₁, i₂, i₃, i₄, i₅, где i₁ = 6, удовлетворяющих (4) (для этого используем формулу (2)).

Таблица 68

v1

v2

v3

v4

v5

v6

v1

¥

¥

v2

¥

¥

¥

¥

¥

¥

¥

v3

¥

¥

¥

¥

¥

¥

v4

¥

¥

¥

¥

¥

¥

v5

¥

¥

¥

¥

¥

v6

¥

¥

¥

¥

¥

¥

¥

Получаем, что в качестве такой последовательности надо взять номера 6, 2, 3, 5, 1, так как

Тогда v₁v₅v₃v₂v₆ – искомый минимальный путь из v₁ в v₆ в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из v₁ в v₆ .

3.2.4. Эйлеровы цепи и циклы

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

Пусть G – псевдограф.

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

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

Определение. Граф является эйлеровым, если он содержит эйлеров цикл.

Рассмотрим вопрос о наличии эйлеровой цепи и цикла в псевдографе.

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

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

Завершая рассмотрение эйлеровых графов, рассмотрим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.

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

• стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;

· на каждом этапе идем по мосту только тогда, когда нет других возможностей.

Пример 84.

Любой простой полный граф с нечетным количеством вершин является эйлеровым. Любой циклический граф является эйлеровым. Граф, являющийся колесом, не является эйлеровым.

3.2.5. Гамильтоновы цепи и циклы

Пусть G – псевдограф.

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

Определение. Граф является гамильтоновым, если он содержит гамильтонов цикл.

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

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

Теорема. Если в простом графе с n (³ 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым.

Пример 85.

Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым.

3.3. Деревья и циклы

3.3.1. Определение и свойства деревьев

Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

Пример 86.

Граф G₁ является деревом (рис.38). Граф G₂ является лесом (рис. 38), он содержит три связные компоненты, каждая из которых является деревом.

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

Утверждение. Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина.

Утверждение. Пусть G – дерево. Тогда любая цепь в G будет простой.

3.3.2. Остовное дерево связного графа

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

Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.

Определение. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).

Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографа G.

Покажем существование остовного дерева для произвольного связного псевдографа G=(V,X), описав алгоритм его выделения.

Шаг 1. Выбираем в G произвольную вершину u₁, которая образует подграф G₁ псевдографа G, являющийся деревом. Полагаем i=1.

Шаг 2. Если i=n, где n=n(G), то задача решена, и G_i – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.

Шаг 3. Пусть уже построено дерево G_i, являющееся подграфом псевдографа G и содержащий некоторые вершины u₁, …, u_i, где 1≤i≤n-1. Строим граф G_i+1, добавляя к графу G_i новую вершину u_i+1Î V, смежную в G с некоторой вершиной u_j графа G_i, и новое ребро (u_i+1, u_j) (в силу связности G и того обстоятельства, что i < n, указанная вершина u_i+1 обязательно найдется). Согласно утверждению граф G_i+1 также является деревом. Присваиваем i:=i+1 и переходим к шагу 2.

Пример 87.

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

Решение.

На рисунке 40 приведена последовательность графов G_i, i=1, 2, 3, 4, 5, получаемых в результате выполнения алгоритма.

При этом в силу того, что n(G)=5, G₅ - остовное дерево графа G.

Замечание. Остовное дерево связного графа может быть выделено, вообще говоря, не единственным способом.

Общее число остовных деревьев связного графа может оказаться весьма большим. Например, для полного графа с n вершинами оно равно n^n-2.

В общем случае обозначим через G произвольный граф с n вершинами, m ребрами и k компонентами. Как уже было сказано, применяя выше описанный алгоритм, получим в результате граф, являющийся остовным лесом.

Определение. Число ребер, удаленных при построении остовного леса произвольного графа G, называется цикломатическим числом (или цикломатическим рангом) графа G и обозначается через g (G) = m – n + k.

Пример 88.

Циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице.

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

С понятием остовного леса Т графа G тесно связано понятие фундаментальной системы циклов, ассоциированной с Т.

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

3.3.3. Минимальные остовные деревья нагруженных графов

Пусть теперь каждому ребру x Î X связного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным. Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальной суммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа G).

Определение. Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G.

Алгоритм выделения МОД нагруженного связного графа G:

Шаг 1. Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему вершинами оно образует подграф G₂ графа G. Положим i=2.

Шаг 2. Если i=n, где n=n(G), то задача решена, и G_i – искомое МОД графа G. В противном случае переходим к шагу 3.

Шаг 3. Строим граф G_i+1, добавляя к графу G_i новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно к какой-нибудь вершине графа G_i и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G_i. Вместе с этим ребром включаем в G_i+1 и инцидентные ему вершины, не содержащуюся в G_i . Присваиваем i:=i+1 и переходим к шагу 2.

Пример 89.

Определить МОД нагруженного графа G, изображенного на рисунке 41, используя алгоритм.

Решение.

На рисунке 42 приведена последовательность графов G_i, i=2,3,4,5, получаемых в результате выполнения алгоритма. При этом в силу того, что n(G)=5, G₅ - МОД графа G. Причем, МОД(G) = 7.

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

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

3.4. Транспортные сети

Определение. Транспортной сетью называется орграф D = (V, X) с множеством вершин V, для которого выполняются условия:

1) существует одна и только одна вершина v₁, называемая источником, такая, что D^-1(v₁) = 0 (т.е. ни одна дуга не заходит в v₁);

2) существует одна и только одна вершина v_n, называемая стоком, такая, что D(v_n) = 0 (т.е. из v_n не исходит ни одной дуги);

3) каждой дуге x Î X поставлено в соответствие целое число c(x) 0, называемое пропускной способностью дуги.

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