В качестве примера связи между орграфами и бинарными отношениями рассмотрим отношения частичного порядка с точки зрения теории графов.
Вершина u в орграфе G(V, Е) достижима из вершины v, если существует путь из v в u. Путь из v в и обозначим <u, v>.
Отношение достижимости можно представить матрицей T:array[l..p, l..p] of 0..1, где T[i, j] = 1, если вершина v(j) достижима из вершины v(i), и T[i, j] = 0, если не достижима.
Рассмотрим отношение строгого порядка >, которое характеризуется следующими аксиомами:
• антирефлексивность: для любого v ∈ V неверно, что v > v;
• антисмметричность: для любых u, v ∈ V неверно, что u > v и v > u;
• транзитивность: для любых u, v, w ∈ V таких, что u > v и v > w следует, что u > w;
Отношению строгого порядка >, заданному на множестве V, можно сопоставить граф G(V, Е), в котором u > v ⇔ (u, v) ∈ Е.
Теорема 1. Если отношение Е есть отношение строгого порядка, то орграф G(V, Е) не имеет контуров.
Доказательство. От противного. Пусть в G есть контур. Рассмотрим любую дугу (a, b) в этом контуре. Тогда имеем а > b, но b > а по транзитивности, что противоречит строгости упорядочения.
Теорема 2. Если орграф G(V, E) нe имеет контуров, то достижимость есть отношение строгого порядка.
Доказательство.
1. Нет циклов, следовательно, нет петель, следовательно, достижимость антирефлексивна.
2. Если существуют пути из v в w и из w в u, то существует и путь из v в u. Следовательно, достижимость транзитивна.
3. Пусть достижимость — это не строгое упорядочение. Тогда существуют u, v такие, что u > v и v > u, то есть существует путь из v в u и из u в v. Следовательно, существует контур <u, v> ∩ <v, u>, что противоречит условию.
Теорема 3. Если орграф не имеет контуров, то в нем есть вершина, полустепень захода которой равна 0.
Доказательство. От противного. Пусть такой вершины нет, тогда для любой вершины найдется вершина, из которой есть дуга в данную вершину. Следовательно, имеем контур против направления стрелок. Это противоречие и доказывает теорему.
Замечание. Теорема 3 позволяет найти минимальный элемент в конечном частично упорядоченном множестве. А именно, минимальный элемент — это источник, то есть вершина, которой в матрице смежности соответствует нулевой столбец.