Глава 2. ОСНОВНЫЕ ПОНЯТИЯ: ОРИЕНТИРОВАННЫЕ ГРАФЫ

2.1. Введение

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

2.2. Ориентированные графы

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

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

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

С другой стороны, введение ориентации необходимо для установления системы координат и устранения неоднозначностей. Например, при соединении электрических приборов одно направление необходимо обозначить как «положительное» для того, чтобы однозначно описать распределение электрического тока, хотя действительное направление может и не быть жестко ограниченным.

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

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

им ребра неориентированного графа параллельны (смежны).

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

тогда и только тогда, когда

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

Рис. 2.1.

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