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

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

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

С другой стороны, введение ориентации необходимо для установления системы координат и устранения неоднозначностей. Например, при соединении электрических приборов одно направление необходимо обозначить как «положительное» для того, чтобы однозначно описать направление электрического тока, хотя действительное направление не может быть жестко ограниченным. С формальной точки зрения ориентированный граф состоит из непустого множества V, множества А, не пересекающегося с V, и отображения D множества А на V ´ V. Элементы V и А соответственно называются вершинами и дугами (или направленными ребрами), а D называется ориентированным отношением инцидентности ориентированного графа. Если аÎА и D(а)=(v, w), то говорят, что дуга а имеет начальную вершину v и конечную вершину w. Обозначение а @ (v, w) будет употребляться для того, чтобы передать тот же самый смысл там, где D не задано в явном виде. (Как и в неориентированном случае, здесь редко появляется необходимость символически изображать само отношение инцидентности, хотя его существование является фундаментальным в понятии ориентированного графа.) Будем снова предполагать, что число вершин и дуг конечно.

Ориентированные графы будут обозначаться через D, (V, А, D) или через (V, А), когда D не задано в явном виде. Если дан ориентированный граф D =(V, А, F), то соответствующим неориентированным графом для него является граф G=(V, А, F ), для которого отношение инцидентности F(а)=(v&w), если D(а)=(v, w). Таким образом, граф G получается из графа D отбрасыванием требования упорядоченности граничных точек каждой дуги. При их описании необходимо использовать соответствующие ориентированные графы. Например, две дуги графа D называются параллельными (смежными), если соответствующие им ребра неориентированного графа G параллельны (смежны).

Говорят, что два ориентированных графа изоморфны, если их соответствующие неориентированные графы изоморфны в обычном смысле и, кроме того, граничные точки каждой пары соответствующих дуг упорядочены одинаковым образом. Формально ориентированные графы D =(V, А, D) и D¢ =(V¢, А¢, D¢) называются изоморфными, если элементы V и А могут быть поставлены во взаимно однозначное соответствие с элементами V¢ и А¢ таким образом, что D¢(а¢)=(v¢, w¢) тогда и только тогда, когда D(а)=(v, w), где а¢, v¢, w¢ обозначают соответственно образы а, v и w. Таким образом, два ориентированных графа на рис. 6.1, а и б изоморфны. С другой стороны, ориентированный граф, приведенный на
рис. 6.1, в, не изоморфен с ними, несмотря на то, что все три соответствующих неориентированных графа изоморфны в обычном смысле.