Дискретная математика : теория графов. Вып. 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 - симметричная.