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

Рассмотрим ориентированный граф на рис.10.1 и обратим внимание на особенности, отличающие ориентированные графы.

Матрица смежности ориентированного графа чаще всего несимметрична (табл. 10.1). Кратные дуги в ней не показываются, аналогично тому, как не показываются кратные ребра в неориентированном мультиграфе. В таблице инциденций (табл. 10.2) записывается -1, если дуга выходит из вершины и 1, если дуга заходит в вершину. Понятие степени вершины в приложениях орграфов обычно утрачивает смысл, хотя можно говорить о полустепени захода и полустепени выхода. Полным орграф называется в том случае, когда каждая пара его вершин связана двумя дугами встречного направления и, кроме того, у каждой вершины имеется петля, т.е. замкнутая дуга, как у псевдографа. Такие понятия, как маршрут, цепь, путь и цикл подразумевают возможность движения только по направлению дуг. Изо всех деревьев интерес представляют только корневые деревья, когда к любой вершине дерева можно пройти по направлению дуг из начальной вершины, называемой корневой вершиной (рис 10.2).

Расстояние определяется только вдоль пути по направлению дуг. Замкнутый цикл в орграфах принято называть контуром, обходить контур можно только по направлению дуг. Путь, проходящий через все вершины орграфа, называется гамильтоновым путем. В незамкнутом гамильтоновом пути число дуг W на единицу меньше, чем число всех вершин графа. Замкнутый гамильтонов путь называется гамильтоновым контуром. Он по одному разу проходит все вершины графа. Число его дуг равно числу V всех вершин графа. Орграф считается связным, если все его вершины достижимы, т.е. если существуют пути от начальной вершины ко всем остальным. От выбора начальной вершины может зависеть окажется ли граф связным. Например, граф на рис. 10.1 будет связным, если в качестве начальной вершины взять a или b. Двудольным называется орграф подобный показанному на рис. 10.3.

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

Отношение эквивалентности рефлексивно, т.е. для любого а О А существует или, в сокращенной записи:

Оно обладает свойством симметричности, т.е. из следует, что . Используя знак импликации " ® " и квантор всеобщности “"” это выражение можно записать так:

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

Эквивалентность транзитивна, т.е. из и следует .

Орграф, задающий отношение эквивалентности на множестве { a, b, c, d, e, f} показан на рис. 10.5.

Ввиду симметричности отношения дуги здесь парные, встречно направленные. Ввиду транзитивности отношения, все эквивалентные элементы образуют между собой класс эквивалентности , т.е. замкнутое подмножество, где все элементы между собой связаны, но нет связей с элементами других классов. В данном примере имеется три класса эквивалентности : C₁ = { a, b} ; C₂ = { c, d, e} ; C₃ = { f} .

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

Отношение доминирования мы обозначим символом Ю . Это отношение нерефлексивно, т.е. не допускается существование а Ю а. Оно несимметрично, т.е. не может быть одновременно a Ю b и b Ю a. Наконец отношение доминирования нетранзитивно. Примером доминирования может служить результат спортивного состязания по матчевой системе. Из того, что а выиграл у b, а b выиграл у с вовсе не следует, что а выиграет у с. Граф отношения доминирования приведен на рис.10.6.

Содержание