получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис. 1.1(6), имеем Г (х^) = {х^, х^, xj, Г (xj = = {xg} и т. д.

Поскольку Г {xi) представляет собой множество таких вершин Xj 6 X, для которых в графе G существует дуга {xi, Xj), то через {х^ естественно обозначить множество вершин х^, для которых в G существует дуга (х^, а;,). Отношение (х;) принято называть обратным соответствием. Для графа, изображенного на рис 1.1(a), имеем

Г-1 {х,)={х2,х,), 1-(х,) = {х,)

и т. д.

Вполне очевидно, что для неориентированного графа T-{Xi) - = Г (Xj) для всех Xi 6 X.

Когда отображение Г действует не на одну вершину, а на множество вершин Хд = {xi, х^, . . а;}, то под Г {Xq) понимают объединение

1{х,)[}Т{хг) и . и Г(а;,), т. е. Г (Zg) является множеством таких вершин Xj 6 X, что для каждой из них существует дуга (а; Xj) в G, где а;, 6 Х^. Для графа, приведенного на рис. 1.1(a), Г {{х^, х^) = {х^, х^, и Г ({a;j, Xs}) = {х^, Xs, Xi}.

Отображение Г (Г (х;)) записывается как Г^ (х;). Аналогично тройное отображение Г (Г (Г (xi))) записывается как Г' (х^) и т. д. Для графа, показанного на рис. 1.1(a), имеем:

Г2 (X,) = Г (Г (X,)) = Г {{Х2, X,}) = {х„ х„ X,}, Гз (х,) = Г (Г2 {X,)) = Г ({X х„ X,}) = {х„ Х2, X,}

и т. д.

Аналогично понимаются обозначения Г~ (xi). Г * (xi) и т. д

2. Пути и маршруты

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

Так, на рис. 1.2 последовательности дуг

Яв. 5. 9. 8, 4. (1-1)

ai, ав, 5. 9, (1-2)

ul, ag, as, as, а^, (1 3)

являются путями.

Рис. 1.2.

Дуги а = (Xi, Xj), Xi Ф Xj, имеющие общие концевые вершины, называются смежными. Две вершины XiUlxj называются смежными, если какая-нибудь из двух дуг (х;, Xj) и Х;) или обе одновременно присутствуют в графе. Так, например, на рис. 1.2 дуги ах, а^о, 3 и в, как и вершины и х^, являются смежными, в то время как дуги и или вершины х^ и х, не являются смежными.

Ориентированной цепью ) (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являются орцепями, а путь (1.3) не является таким, поскольку дуга в нем используется дважды.

Простой орцепъю ) называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (1.2) является простой орцепью, а пути (1.1) и (1.3) - нет. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Например, путь (1.1) является орцепью, но не простой орцепью, путь (1.2) является орцепью и простой орцепью, а путь (1.3) не является ни орцепью, ни простой орцепью. Маршрут есть неориентированный двойник пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направ-

) В оригинале используется термин простой путь .- Прим. ред. ) В оригинале применяется термин элементарный путь .- Прим. ред.

ленностью дуг в графе. Таким образом, маршрут есть последовательность ребер а^, aj, - . ., Яд, в которой каждое ребро а^, за исключением, возможно, первого и последнего ребер, связано с ребрами а,- 1 и a,-+i своими двумя концевыми вершинами. Последовательности дуг

аз, ui, as, aio, (1.4)

а2, ay, as, а4, аз (1-5)

aio, а;, а4, as, а;, az (1.6)

в графе, изображенном на рис. 1.2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.

Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи ) и простые цепи ). Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) - цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.

Путь или маршрут можно изображать также последовательностью вершин, что мы и будем использовать. Путь (1.1) можно представить также последовательностью вершин Xj, Xj, Х4, Xj, Х5, Хб и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей пли простых цепей.

2.1. Веса и длина пути

Иногда дугам графа G сопоставляются (приписываются) числа - дуге (х;, Xj) ставится в соответствие некоторое число c;, называемое весом, или длиной, или стоимостью {ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа у,) приписываются вершинам х,- графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным ).

При рассмотрении пути ix, представленного последовательностью дуг (а^, а^, . . ., Uq), за его вес (или длину, или стоимость) принимается число I (а,), равное сумме весов всех дуг *), входящих

1) в оригинале используется термин простой маршрут .- Прим. ред.

2) В оригинале применяется термин элементарный маршрут .- Прим.

3) Чаще взвешенным называют граф со взвешенными вершинами.- Прим.

*) Каждая дуга рассматривается столько раз, сколько она встречается в данном пути.- Прим. ред.