Дискретная математика : теория графов. Вып. 5. Маршруты в графе. Виды маршрутов

УДК 519.45 
Д79 

Р е ц е н з е н т 
доктор технических наук, профессор МГГУ Л.П, Рябов 

Дубравина Т.В., Прокопчук Ю.Ю., Широков А.И. 

Д79 
Дискретная математика: Теория графов. Вып. 5. Маршруты 
в графе. Виды 
маршрутов: 
Учеб. 
пособие / Под ред. 
Ю.А. Кудрявцева. - 2-е изд., испр. - М.: МИСиС, 2003. - 31 с. 

Пособие является частью раздела «Теория графов» учебного курса 
«Дискретная математика». В нем изложены понятия, связанные с обходами 
графов. В приложении приведены некоторые математические понятия, используемые в теоретической части пособия. 

Содержание пособия соответствует программе курса «Дискретная математика».Предназначено для студентов специальностей 220200 и 351400. 

© Московский государственный институт 
стали и сплавов (Технологический 
университет) (МИСиС), 2003 

ОГЛАВЛЕНИЕ 

Введение 
4 

1. Об обозначениях 
4 

2. Маршруты 
4 

3. Виды маршрутов 
10 

Вопросы и упражнения 
14 

Библиографический список 
18 

Приложение. О булевых алгебрах и матрицах над ними 
19 

1. Булевы алгебры 
19 

2. Некоторые следствия из аксиом 
20 

3. Булевы матрицы 
28 

4. Двухэлементная булева алгебра В' 
29 

5. Матрицы над В' 
30 

Библиографический список (к приложению) 
31 

ВВЕДЕНИЕ 

1. Об обозначениях 

Чтобы не использовать двухъярусные индексы, например Z; , 

условимся о следующем. Обозначение некоторой вершины графа 
L = df<X,U;P> через xi не обязывает нас считать индекс i номером 
этой вершины во множестве X, когда оно упорядочено посредством 
нумерации его элементов. В частности, вершины Xi и Xj не обязательно различны при i ^ j . Аналогичное соглашение примем по отношению к знакам вида Ui, обозначающим ребра графа L. 

2. Маршруты 

1. Ниже мы будем изучать свойства графа, инвариантные 
относительно произвольной ориентации его звеньев и переориентации или дезориентации его дуг (всех или некоторых). Хотя без 
ограничения общности можно было бы рассматривать только неорграфы, но мы предпочитаем другой подход: для нас будут 
представлять 
интерес 
некоторые 
из 
таких 
свойств 
графа 
L = df<X,U;P> общего вида, которые эквивалентны свойствам 
графа L' = df<X,U;P'>, где инцидентор Р' графа L' определяется 
на основе инцидентора Р графа L так: 

Р'(х,и,у) = df(P(x,u,y)vP(y,u,x)). 
(1) 

Предикат Р' называют иногда полуинцендентором графа L. 

2. Конечную последовательность 

X0U1X1U2X2...X1.1U1X1, 
(2) 

где /eN, вершин и ребер графа L=df<X,U;P>, для членов которой верно 
соотношение: 

P ' ( X O , U I , X I ) A P ' ( X I , U 2 , X 2 ) A . . . A P ' ( X I . I , U I , X I ) , 
(3) 

равносильное конъюнкции 

Aie[o,i-i]P'(Xi,Ui+i, Xi+i), 
(3') 

называют его маршрутом из вершины Хо в вершину Хь или маршрутом, соединяющим Хо с Xi. Вершины Хо и Xi маршрута (2) именуют 
соответственно его начальной и конечной. Число / ребер, учитываемых в маршруте (2), называют его длиной. 

Отметим, что маршрут- это не просто часть графа [5, 
с. 3], ибо порядок его обхода также принимается во внимание. 
Так, маршрут 

X1U1X1.1...U2X1U1X0 
(4) 

при М не совпадает с (2), хотя и состоит из тех же элементов графа L, что 
и (2), и для него аналог конъюнкции (3) в силу (1) равносилен (3). 

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

3. Рассмотрим вопросы, связанные: а) с определением числа 
маршрутов заданной длины из одной вершины графа в другую; б) с 
их наличием или отсутствием; в) с их фактическим выявлением. 

а) Пусть К - полукольцо, образующие ^, г), (!^ и Э которого являются элементами матрицы инциденций графа L [3, с. 6] и удовлетворяют условию 

^ц=ц^ = С = 0'=\, 
(5) 

а также условию дистрибутивности для элементов вида 

k = df(l + l+...+ 1). 
(6) 

Поэтому полукольцо к содержит в качестве подполукольца множество К' целых неотрицательных чисел с обычными сложением и умножением. В результате наложения этих условий матрица смежности R 
графа L = <X,U;P> принимает такой вид: на пересечении ее i-й строки 
и j-ro столбца, где l<i,j<n, а n = dflX|, находится число ребер, инцидентных i-й и j-й вершинам, т.е. число | S(Xi,Xj) | [2, с. 8 соотношение 8]. В силу равенства | S(xi,Xj) | = | S(xj,Xi) |, где XbXjsX, матрица 
R - симметричная. 

Матрица смежности R графа Lj, изображенного на рис. 1, 

<==^о^ 

Рис 1. Граф Li 

имеет такой вид: 

а 
b 

Ri = c 

d 
е 

а b с d е 
0 3 0 0 0 
3 0 2 1 
0 2 0 1 
0 
1 1 1 
0 0 0 0 

(7) 

Индукцией по /, где /eN^, покажем, что элемент г*. 1-й степени R' матрицы R равен числу маршрутов длины / из вершины xi в 
вершину Xj графа L. 

Базис индукции. При / = 1 утверждение очевидно в силу определения матрицы R. 

Индуктивный 
переход. 
Предположим, 
что 
элемент 

г/^'''матрицы R''равен числу маршрутов длины р из вершины Xi в 
вершину Хк графа Ьг, где l<i,k<n. Тогда число маршрутов длины 
(р+1) из вершины Xi в вершину Xj, проходяш;их через 
вершину 
Хк, согласно комбинаторному правилу произведения равно 

i^ik •Гк](рис. 2). 

'Г,/; Ш>. А 
(р) 

-.. ••••..• i t 

г^Р) \ Х ••••••© 

rtj=0 

Рис 2. Граф L2 

Но маршруты из xi в Xj длины (р+1) могут проходить не только через 
вершину Хк, но и через другие вершины графа. Поэтому общее число 
таких маршрутов равно 

2jke[l;n](rik «Гк]), 

Т.е. элементу г-Р^'' матрицы R''^^ [3, с. 28]. 

Обратимся к рассмотренному выше примеру. Вторая степень 
матрицы (7) такова: 

RN 

9 
0 6 3 0 

О 14 1 3 О 
6 
1 5 
3 0 

3 
3 3 3 0 

0 
0 0 0 4 

(8) 

б) Интересуясь только наличием или отсутствием в графе L маршрутов длины / из i-й вершины в j-ю, мы должны к определяющим соотношениям (5) и (6) полукольца К добавить еще булево: 

2 = 1. 
(9) 

Тогда подполукольцо К' становится двухэлементной булевой алгеброй с элементами 0,1 [3, с. 23], а элемент цг\р булевой матрицы BR', 

(симметричной, как и R') (Приложение 1, п. 3) будет равен 1 или О 
смотря по тому, существует или нет в графе L хотя бы один маршрут 
длины / из i-й вершины в j-ю. 

Из сказанного следует, что для графа Lj, приведенного на 

рис. 1, матрица BR такова: 

а 
b 

d 
е 

а b с d е 
0 1 0 
0 0 
1 0 
1 1 0 
0 1 0 
1 0 
0 
1 1 1 0 
0 0 0 0 1 

(10) 

в) Для фактического выявления всех маршрутов данной длины 
из одной заданной вершины графа в другую можно предложить следующий способ, который мы во избежание излишней громоздкости 
разъясним на простом примере графа Lj, изображенного на рис. 3. 

КЕО^ 

W 

Рис 3. Граф Ьз 

Составим для него матрицу смежности R2 над полукольцом К' всех 
целых чисел: 

Я 
а 
b 
с 

а b 
1 1 
1 0 
0 2 

с 
0 
2 
0 

и, имея в виду матрицу инциденции 

U 

а 
С 
b О 
с О 

А 

W 

О 

11 

этого графа над свободным полукольцом К, построим «усовершенствованную» матрицу смежности: 

У ^ 2 
df 

а 
U 
V 
О 

V 
О 

w + t 

с 
о 

w + t 

о 

(И) 

в которой указано не только число ребер, соединяющих пару заданных вершин, но и сами эти ребра. При этом буквы и, v, w и t, обозначающие ребра графа Ьг, рассматриваем как образующие элементы 
нового некоммутативного кольца уС, которое считаем ассоциативным (и конечно, дистрибутивным, как и всякое кольцо). Последовательно находим степени матрицы уКг: 

У ^ 2 
а 
b 
с 

а 

2 
2 

U 
+ V 

VU 

wv + tv 

W 

UV 

2 
t + wt + tw 
о 
w 

с 

vw + vt 

0 
t^ + wt + tw 

(12) 

(уК-2)' ( у ^ 2 ) ' •••' (у^2)
Матрицу yRj будем называть усовершенствованной матрицей связей вершин графа Ьз маршрутами длины I или просто матрицей связей графа L, если ясно, о чем идет речь. Мы видим (и это 
можно доказать для общего случая), что элемент уГ^ 
матрицы 

vR 
л/) 
yiv 2 
(уГ )• ) равен сумме таких произведений, в каждом из которых 

сомножители соответствуют (в том же порядке) последовательным 
ребрам некоторого маршрута длины / из i-й вершины графа в j-ю, где 
l<i, j<3, причем ни один из маршрутов не может быть пропущен и ни 
один не повторится. 

Например, в элементе 

(2) 

1 
t + Wt + tw 

содержится информация о последовательностях ребер во всех маршрутах длины 2 из вершины b в эту же вершину. Последовательность вершин каждого маршрута однозначно определяется при помощи матрицы Аг. Эти маршруты суть: 

bvavb, bwcwb, btctb, bwctb, btcwb. 

С увеличением / «сложность» элементов матрицы yR' резко 
возрастает, но в этом «виноват» не предлагаемый способ, а сам факт 
наличия колоссального, вообще говоря, числа маршрутов в графе. Однако, если ограничиться рассмотрением только маршрутов каких-то 
специальных видов, которых в графе может оказаться не слишком 
много, указанная «сложность» элементов матрицы yR' может расти не 
так быстро. О некоторых из таких видов и пойдет речь ниже. 

3. Виды маршрутов 

Существуют классификации маршрутов по самым различным 
основаниям. Мы рассмотрим здесь только некоторые из таких классификаций. 

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

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

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

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

Взаимоотношение объемов введенных понятий иллюстрирует рис. 4. 

Рис. 4. Диаграмма взаимоотношений объемов 

10 

2. Желая по матрице yR выявить не все маршруты данной длины, а только цепи, мы должны после каждого умножения на yR удалять 
из элементов произведения соответствующих матриц те слагаемые, в 
которых какой-либо сомножитель встречается более одного раза. 

Например, в случае графа Lj, 
изображенного на рис. 3 
[см. матрицу (12)], получаем 

(у^1) 

о 
UV 
VW + vt 

VU 
wt + tw 
о 
wv + tv 
о 
wt + tw 

(13) 

3. Определение 1. Подмаршрутом 
маршрута 

XoUiXiU2...Xi.iUiXi 
(14) 

назовем любую подпоследовательность последовательности (14), 
являющуюся маршрутом. 

Ясно, что любая вершина xi, где 0<i</, и любой маршрут вида 
Xi.iUiXi, где l<i</, есть подмаршрут маршрута (14) - это подмаршруты 
длины О и 1 соответственно. Но только ими все подмаршруты маршрута (14), вообще говоря, не исчерпываются. 

Обозначая через Аху п р о и з в о л ь н ы й 
маршрут графа 
L = <X,U;P> с начальной вершиной х и конечной у, введем на множестве маршрутов этого графа следующее бинарное отношение. 
Пусть x,y,z,WGX. Будем говорить, что маршрут Аху содержит маршрут A^w и обозначать это так: 

Д 
^ А 

если Azw - подмаршрут маршрута Аху. Имеет место следующая лемма. 
Лемма 
1. Всякий маршрут (в частности, всякая цепь) графа содержит 
по крайней мере одну простую цепь, соединяющую ту же пару вершин. 

2. Всякий циклический маршрут нечетной длины содержит 
простой цикл нечетной длины. 

3. Всякий цикл содержит простой цикл. 

Доказательство 
1. Е с л и X i - п е р в а я из т е х в е р ш и н маршрута 

XoUiXiU2...Xi.iUiXi, 
(1) 

которая встречается в нем более одного раза, а Xj - последняя из совпадающих с Xi вершин (см. п. 1) этого маршрута, то подмаршрут 

XoUiXiU2...XiUj+iXj+iUj+2Xj+2...Xi.iUiXi 
(11) 

11 

маршрута (1) является маршрутом из Хо в Хь но имеет меньшую, чем 
маршрут (I), длину. Если в (И) есть повторения вершин, то с ними 
поступаем точно так же, как и выше, и так до тех пор, пока не выявим маршрут, соединяющий Хо с Xi, но без повторяющихся вершин, 
т.е. искомую простую цепь. Если (1) - циклический маршрут, то интересующая нас цепь окажется состоящей из одной вершины хо, которая совпадает с хь 

2. Пусть в графе есть циклический маршрут 

XoUiXiU2...X2kU2k+lXo, 
( Ш ) 

нечетной длины. Если этот маршрут является простым циклом, то 
все доказано. Пусть (111) - не простой цикл. Покажем, что он содержит цикл нечетной длины. В самом деле, если xi и Xj, О < i,j < 2к, две такие его вершины, что Xi = Xj, то оба маршрута 

XoUiXiU2...Xi.iUiXiUi+iXi+i...X2kU2k+lXo, 
(ИГ) 

И 

XiUi+iXi+i...Xj.iUjXj 
(111") 

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

3. Опишем логическую схему доказательства последнего утверждения леммы. 

1. Пусть 

А х =XoUiXiU2...Xi.iUiXo 
(IV) 

- цикл. Отсюда, в частности, следует, что 

/>0. 
(V) 

Если (IV) - простой цикл, то все доказано. Поэтому ниже будем 
считать, что 

Ах - не простой цикл. 
(VI) 

Далее, если / - нечетное число, то А^ , будучи циклическим маршрутом, содержит простой цикл в силу утверждения 2, и снова все доказано. Поэтому ниже будем предполагать, что 

12