214 |
Глава 7. Связность графов |
|
|
Глава 7
Связность графов
7.1 Маршруты, цепи, циклы
Предварительные замечания. В этом разделе рассматриваются такие свойства графов, которые не зависят от ориентации, то есть такие, которые полностью определяются в терминах полуинцидентора
»
P (x; u; y) = P (x; u; y) _ P (y; u; x).
Будем обозначать граф общего вида как G = (X; U) , предполагая
»
заданным полуинцидентор P .
Об индексах. Обозначение вершины xi не обязывает нас считать индекс i номером вершины в множестве X; вершины с индексами i и j не обязательно различны при i 6= j. Индексы обозначают порядковый номер cоответствующего элемента в маршруте.
Определение. Конечная последовательность
x0u1x1u2x2 : : : xl¡1ulxl (l ¸ 0)
элементов графа G, для которой истинно высказывание
» |
(x0; u1; x1) & |
» |
(x1; u2; x2) & : : : & |
» |
(xl¡1; ul; xl) |
P |
P |
P |
называется маршрутом из вершины x0 в вершину xl, или маршрутом, соединяющим вершину x0 с вершиной xl.
В случае x0 = xl маршрут называется циклическим. Число l называется длиной маршрута.
Маршрут не является частью графа, так как порядок его обхода имеет существенное значение. Так, маршрут
xlulxl¡1 : : : x2u2x1u1x0
7.1. Маршруты, цепи, циклы |
215 |
|
|
|
|
при l =6 0 не совпадает с приведенным в определении, хотя состоит из тех же элементов и с той же инцидентностью.
7.1.1Число маршрутов
Рассмотрим матрицу смежности R над полукольцом Kсо следующими определяющими соотношениями
°> °< = °< °> =°± 2 =°» 2 = 1; 1 + 1 = 2
(обычное арифметическое сложение). Таким образом, Kсодержит подполукольцо K0 целых неотрицательных чисел с обычными сложением и умножением.
Элемент rij матрицы смежности в этом случае определяет число ребер s(xi; xj), соединяющих вершины xi; xj.
Рассмотрим далее l-ю степень
Rl = krij(l)k; l = 1; 2; : : :.
матрицы смежности R графа G.
Лемма 1 Элемент rij(l) равен числу различных маршрутов длины l из вершины xi в вершину xj.
До к а з а т е л ь с т в о . При l = 1 это утверждение очевидно.
Вобщем случае утверждение доказывается индукцией по l. Если
известно, что rik(l¡1) – число различных маршрутов длины l ¡ 1 из вершины xi в вершину xk, то для числа маршрутов длины l из вершины xi в вершину xj имеем (для фиксированной вершины xk)
rik(l¡1) ¢ rkj,
a для всех k число маршрутов равно
Pn rik(l¡1) ¢ rkj, k=1
а это ни что иное, как rij(l) – элемент матрицы Rl. £
Пример 7.1.
Рассмотрим степени матрицы смежности графа, представленного на рисунке:
216 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Глава 7. |
Связность графов |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
1 |
|
|
|
|
|
|
|
|
b |
|
|
|
|
4 |
|
|
|
|
|
|
|
c |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
¾ |
|
|
|
2 ~ |
|
|
|
|
|
|
|
|
|
- |
|
|
|
R |
a |
|
b |
c |
d e |
|
|
|||||||||||||
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
rKAA |
5 |
|
¢¸¢ |
r |
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
0 3 0 0 0 |
|
|
|||||||||||||||||||||
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
9 |
²¯²¯ |
|
|
|
|
8 A |
¢ 6 |
|
R = |
b |
3 |
0 |
2 |
1 |
0 |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
0 |
2 |
0 |
1 |
0 |
|
|
||||||||||||||||
|
|
|
|
r |
10 |
|
|
|
|
|
|
|
|
A¢ |
|
|
|
d |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
±°±°e |
|
|
|
|
|
|
²¯7 |
|
|
d |
0 |
1 |
1 |
1 |
0 |
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
±° |
|
e |
0 |
0 |
0 |
0 |
2 |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
R2 |
|
a b c d e |
|
|
R3 |
|
a b |
c d e |
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
a |
|
9 0 6 3 0 |
|
|
a |
|
0 42 3 |
9 |
0 |
|
||||||||||||||||||||
|
|
R2 |
= |
|
|
|
|
|
b |
|
0 |
|
|
14 |
|
1 |
3 0 |
R3 = |
b |
|
42 |
5 |
31 18 |
0 |
|
||||||||||||||||
|
|
|
|
|
|
|
c |
|
6 |
|
|
1 5 |
3 0 |
c |
|
3 31 5 |
9 0 |
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
d |
3 |
|
|
3 3 3 0 |
|
|
d |
|
9 18 |
9 |
9 0 |
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
e |
|
0 |
|
|
0 0 |
0 4 |
|
|
e |
|
0 0 |
0 |
0 8 |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Например, из вершины c в c идут 5 маршрутов длины 2: c 4 b 4 c; c 5 b 5 c; c 4 b 5 c; c 5 b 4 c; c 6 d 6 c;
из c в d идут 3 маршрута длины 2: c 4 b 8 d; c 5 b 8 d; c 6 d 7 d;
из d в c идут 9 маршрутов длины 3:
d 6 c 6 d 6 c; d 6 c 4 b 4 c; d 6 c 4 b 5 c; d 6 c 5 b 4 c; d 6 c 5 b 5 c, d 7 d 7 d 6 c; d 7 d 8 b 4 c; d 7 d 8 b 5 c; d 8 b 8 d 6 c. J
Если нас интересует только достижимость j-й вершины из i- й за число шагов l (то есть только наличие маршрута длины l из вершины xi в вершину xj), добавим к определяющим соотношениям в полукольце Kеще булево 2 = 1 (то есть 1 + 1 = 1). Тогда подполукольцо K0 ½ Kстанет булевой алгеброй Bf0; 1g. При этом
элемент rij(l) матрицы Rl будет равен 1, если существует хотя бы один маршрут длины l из вершины xi в вершину xj, и 0, если не существует ни одного такого маршрута.
Пример 7.2.
Для графа из предыдущего примера имеем:
7.1. Маршруты, цепи, циклы |
|
|
|
|
|
|
|
|
|
|
217 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
R |
a b c d e |
|
|
|
|
|
|
R2 |
a b c d e |
||||||||||||||
|
|
a |
0 1 0 0 0 |
|
|
|
|
|
a |
1 0 1 1 0 |
|||||||||||||||
R = |
|
b |
1 0 1 1 0 |
|
|
R2 = |
|
b |
0 |
1 |
1 |
1 |
0 |
|
|||||||||||
|
|
c |
0 1 |
0 |
1 0 |
|
|
|
|
|
c |
|
1 |
1 |
1 |
1 |
0 |
|
|||||||
|
|
d |
0 1 |
1 |
1 0 |
|
|
|
|
|
d |
1 |
1 |
1 |
1 |
0 |
|
||||||||
|
|
e |
0 0 |
0 |
0 1 |
|
|
|
|
|
e |
|
0 |
0 |
0 |
0 |
1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
R3 |
a b c d e |
|
|
R4 |
a b c d e |
|
|
||||||||||||||||
|
|
a |
0 1 1 1 0 |
|
|
|
a |
1 1 1 1 0 |
|
||||||||||||||||
R3 = |
b |
1 |
1 |
1 |
1 |
0 |
|
R4 = R5 = |
|
b |
1 |
1 1 |
1 0 |
J |
|||||||||||
|
|
c |
|
1 |
1 |
1 |
1 |
0 |
|
|
|
c |
|
1 |
1 1 |
1 0 |
|
|
|||||||
|
|
d |
1 |
1 |
1 |
1 |
0 |
|
|
|
d |
1 |
1 1 |
1 0 |
|
|
|||||||||
|
|
e |
|
0 |
0 |
0 |
0 |
1 |
|
|
|
e |
|
0 |
0 0 |
0 1 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для нахождения всех маршрутов данной длины, идущих из одной заданной вершины в другую, можно использовать модифицированную матрицу смежности. Продемонстрируем это на примере.
Пример 7.3.
Для графа, изображенного на рисунке, построим такую матрицу смежности:
u²¯sa v |
|
|
|
|
|
|
|
bs |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
R |
a |
b |
c |
||||||||
±°w |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t |
Ru = |
a |
u |
v |
0 |
||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b |
v |
0 |
w + t |
||
|
c s |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
c |
0 |
w + t |
0 |
|||||||
Элемент rij матрицы Ru заменен на ребро, соединяющее вершины xi с xj; если таких ребер несколько, то rij будет суммой ребер.
Таким образом, символы u; v; w; t из примера можно рассматривать как образующие элементы нового некоммутативного кольца Ku, которое будем считать ассоциативным и дистрибутивным. Теперь последовательно образуем степени матрицы Ru:
218 |
|
|
|
Глава 7. Связность графов |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R |
a |
b |
c |
|
|
|
|
|
|
|
|
R2 |
= |
a |
u2 + v2 |
uv |
vw + vt |
|
u |
|
b |
vu |
v2 + w2 + wt + tw |
0 |
|
|
|
|
||||
|
|
c |
wv + tv |
0 |
w2 + t2 + wt + tw |
|
Поясним смысл, например, элемента rac2 = vw + vt: из вершины a в вершину c имеется два маршрута длины 2 – [avbwc] и [avbtc]. J
Этот способ нахождения всех маршрутов более нагляден и прост в реализации, если вместо матричного представления графа использовать представление в виде массива
fa u a; a v b; b v a, b t c, b w c, c t b, c w bg.
Тогда “2-ю степень” аналога матрицы смежности можно представить как массив
fa u a u a; a u a v b, a v b v a, a b t c, a v b v c, b v a u a, b v a v b, b t c t b, b t c w b, b w c t b; b w c w b, c t b v a, c t b t c, c t b w c, c w b v a, c w b t c, c w b w cg.
Как видно из примера, маршрут длины l образуется в том случае, если начало l-ой тройки маршрута (например, b v a), совпадает с концом маршрута длины l ¡ 1 (например, c t b).
|
r |
t |
r |
v |
|
r |
|
|
|
|
|||
c |
|
b |
|
a |
||
Следующую степень получим, умножая аналог 2-й степени матрицы смежности на аналог первой степени матрицы смежности.
Определение. Маршрут x0u1x1u2x2 : : : xl¡1ulxl называется цепью, если все ребра в нем различны. Циклическая цепь называется циклом.
Пример 7.4.
ad
r 1 2 ´r
@@c ´´
6 @´r 3
,5 ,bbb4 r, br
be
7.1. Маршруты, цепи, циклы |
219 |
|
|
|
|
Примеры циклов: [a1c4e3d2c5b6c]; [b6a1c5b], [c2d3e4c]. J
Определение. Цепь называется простой, если все ее вершины различны.
Цикл называется простым, если все его вершины различны, кроме x0 = xl.
Если нужно выявить только простые цепи (с помощью R), то после каждого умножения нужно вычеркивать те слагаемые, в которых сомножители встречаются более одного раза ( т.е. элементы в квадрате).
Пример 7.5. Для нашего графа
|
R2 |
a |
b |
c |
|
Ru2 = |
a |
0 |
uv |
vw + vt |
J |
|
b |
vu |
wt + tw |
0 |
|
|
c |
wv + tv |
0 |
wt + tw |
|
|
|
|
|
|
|
Лемма 2 Всякий маршрут (в частности, всякая цепь) графа содержит хотя бы одну простую цепь, соединяющую ту же пару вершин.
Всякий циклический маршрут нечетной длины содержит простой цикл нечетной длины.
Всякий цикл содержит простой цикл.
Д о к а з а т е л ь с т в о . 1. Если в данном маршруте
x0u1x1 : : : xl¡1ulxl
все вершины различны, то он сам и есть искомая простая цепь. Если xi – первая из тех вершин маршрута, которая входит в него более одного раза, а xj – последняя из совпадающих с xi вершин этого маршрута, то его можно заменить более коротким
x0u1x1 : : : xiuj+1xj+1uj+2 : : : xl¡1ulxl.
Если в полученном маршруте есть еще повторяющиеся вершины, то снова заменяем его более коротким и так далее, пока не выделим маршрут без повторяющихся вершин, соединяющий x0 с xl, то есть искомую простую цепь (если исходный маршрут циклический, то эта цепь будет состоять из единственной вершины x0 = xl).
