Отступление

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

2. Достижимость и упорядочение

В качестве примера связи между орграфами и бинарными отношениями рассмотрим отношения порядка с точки зрения теории графов. Вершина u в орграфе G(V, Е) достижима из вершины v, если существует путь из v в u.
Путь из v в u обозначим

Отношение достижимости можно представить матрицей Т : array [1..p, 1..p] of 0..1, где T[i, j] = 1, если вершина u, достижима из вершины v_i, и T[i, j] = 0, если вершина v_j недостижима из вершины v_i.
Рассмотрим отношение строгого порядка , которое характеризуется следующими аксиомами:

• антирефлексивность v V (vv);
• транзитивность: u, v, w (vw&wu vu);
• несимметричность: u, v (uv&vu).

Отношению строгого порядка VxV можно сопоставить граф G(V, Е), в котором ab (a, b) E.

Теорема
Если отношение Е есть строгое упорядочение, то орграф G(V, E) не имеет контуров.

Доказательство
От противного. Пусть в G есть контур. Рассмотрим любую дугу (а, b) в этом контуре. Тогда имеем а b, но b а по транзитивности, что противоречит строгости упорядочения.

Теорема
Если орграф G(V, E) не имеет контуров, то достижимость есть строгое упорядочение.

Доказательство
1. Нет циклов, следовательно, нет петель, следовательно, достижимость антирефлексивна.
2. Если существуют пути из v в w и из w в u, то существует и путь из v в u. Следовательно, достижимость транзитивна.
3. Пусть достижимость — это не строгое упорядочение. Тогда u, v   uv&vu, то есть существует путь из v в u и из u в v. Следовательно, существует контур
что противоречит условию.

Теорема
Если орграф не имеет контуров, то в нем есть вершина, полустепень захода которой равна 0.

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

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

3. Транзитивное замыкание

Если Е — бинарное отношение на V, то транзитивным замыканием E+ на V будет отношение достижимости на орграфе G(V, E).

Теорема
Пусть М — матрица смежности орграфа G(V, Е). Тогда Мk[i, j] = 1 в том и только в том случае, если существует путь длиной k из вершины vi, в вершину vj.

Доказательство
Индукция по k. База: k = 1, М¹ = М — пути длины 1. Пусть М^k-1 содержит пути длины k-1. Тогда

то есть путь длины k из вершины i в вершину j существует тогда и только тогда, когда существуют вершина l, такая что существует путь длины k - 1 из i в l и дуга (l, j), то есть

Если T — матрица достижимости, то очевидно, что

Трудоемкость прямого вычисления по этой формуле составит O(р⁴). Матрица достижимости Т может быть вычислена по матрице смежности М алгоритмом Уоршалла за O(р³).

Упражнения
1. Построить пример графов G₁ и G₂, для которых p₁ = р₂, q₁ = q₂, ₁ = ₂, ₁ = ₂, но G₁G₁ (кроме примера подраздела 1.6).

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

3. Задача Рамсея. Доказать, что среди любых 6 человек есть либо 3 попарно знакомых, либо 3 попарно незнакомых.

4. Рассмотрим матрицу смежности ребер Q : array [1..q, 1..q] of 0..1, где

Является ли матрица смежности ребер Q представлением в ЭВМ графа G(V, Е)?

5. Описать в терминах теории графов отношение эквивалентности на конечном множестве.

[Список тем]