Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

150
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
'
&
$
%
1
'
&
$
%
2
'
&
$
%
3
µ´
¶³
4
µ´
¶³
5
¶
µ
³
´
6
µ´
¶³
7
±°
²¯
8
±°
²¯
9 1
2 4
5 3
6 8
9 7
Рис. 4.41
Рис. 4.42
Непустое упорядоченное дерево T может интерпретироваться в виде си- стемы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T ) так, что:
1) если T
0
— поддерево упорядоченного дерева T
00
, T
0
, T
00
∈ S(T ), то для соответствующих множеств X
0
и X
00
выполняется включение X
0
⊆ X
00
;
2) если T
0
не является поддеревом упорядоченного дерева T
00
и T
00
не яв- ляется поддеревом упорядоченного дерева T
0
(где T
0
, T
00
∈ S(T )), то соответ- ствующие множества не пересекаются.
Пример 4.10.1. Упорядоченному дереву
(1, (2, (4), (5)), (3, (6, (8), (9)), (7)))
соответствует система множеств, изображенная на рис. 4.41. ¤
Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях.
На рис. 4.42 представлен уступчатый список, соответствующий упорядочен- ному списку из примера 4.10.1.
Согласно следующему тезису любая схема, в которой заданы определен- ные приоритеты между элементами, может рассматриваться как некоторое упорядоченное дерево.
Тезис. Любая иерархическая классификационная схема интерпретиру-
ется некоторым упорядоченным деревом.

4.10. УПОРЯДОЧЕННЫЕ И БИНАРНЫЕ ДЕРЕВЬЯ
151
Например, в виде упорядоченного дерева представляется любой терм.
На рис. 4.43 изображено упорядоченное дерево, соответствующее терму
t = a − b · (c : d + e : f ).
Частным случаем упорядоченного дерева является бинарное дерево.
дерево. Определение бинарного дерева повторяет k
−
k
a
k
×
k
b
k
+
k
:
k
:
k
c
k
d
k
e
k
f
¡
¡
@
@
¡
¡
@
@
@
@
@
@
@
@
¡
¡
¡
¡
©
©
©
©
Рис. 4.43
определение для упорядоченного дерева с ограни- чением
n ∈ {0, 1, 2}
в п. 2. При этом для бинарного дерева T = ((a), T
1
, T
2
), бинарное под- дерево T
1
называется левым поддеревом, а T
2
—
правым поддеревом.
Бинарные деревья имеют более простое устрой- ство, чем упорядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответ- ствует некоторому бинарному дереву.
Опишем алгоритм преобразования упорядоченного леса T = (T
1
, T
2
,
. . . , T
n
) в бинарное дерево B(T ).
1. Если n = 0, B(T ) ­ ∅.
2. Если n > 0, то корнем бинарного дерева B(T ) является корень a
1
упорядоченного дерева T
1
, левое поддерево дерева B(T ) — бинарное дерево
B(T
11
, T
12
, . . ., T
1m
), где T
1
= (a
1
, T
11
, T
12
, . . . , T
1m
), правое поддерево дере- ва B(T ) — бинарное дерево B(T
2
, . . . , T
n
).
На рис 4.44б представлено бинарное дерево, соответствующее упорядо- ченному лесу (T
1
, T
2
), изображенному на рис 4.44а.
A
µ´
¶³
B
µ´
¶³
C
µ´
¶³
H
µ´
¶³
¡
¡
¡
@
@
@
D
µ´
¶³
E
µ´
¶³
I
µ´
¶³
F
µ´
¶³
J
µ´
¶³
G
µ´
¶³
¡
¡
¡
@
@
@
A
µ´
¶³
B
µ´
¶³
C
µ´
¶³
H
µ´
¶³
E
µ´
¶³
I
µ´
¶³
D
µ´
¶³
F
µ´
¶³
J
µ´
¶³
G
µ´
¶³
¡
¡
¡
ª
-
?
-
¡
¡
¡
ª
?
-
?
-
а
б
Рис. 4.44

152
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
§ 4.11.
Фундаментальные циклы
Пусть G = hM; Ri — неорграф, имеющий n вершин, m ребер и c ком- понент связности, T — остов графа G. В § 4.8 отмечалось, что T имеет
ν
∗
(G) = n − c ребер u
1
, . . . , u
n−c
, которые будем называть ветвями остова
T . Оставшиеся m − n + c ребер v
1
, v
2
, . . . , v
m−n+c
, не входящие в T , будем называть хордами остова T . Согласно теореме 4.8.1, п. 5, если к лесу T до- бавить произвольную хорду v
i
, то в полученном графе найдется ровно один цикл, который обозначим через C
i
. Цикл C
i
состоит из хорды v
i
и некоторых ветвей остова T , которые принадлежат единственной простой цепи, соеди- няющей вершины хорды v
i
. Цикл C
i
называется фундаментальным циклом
графа G относительно хорды v
i
остова T . Множество
{C
1
, . . . , C
m−n+c
}
всех фундаментальных циклов относительно хорд остова T называется фун-
даментальным множеством циклов графа G относительно остова T . От- метим, что мощность фундаментального множества циклов равна циклома- тическому числу ν(G) = m − n + c.
Обозначим через (w
1
, w
2
, . . . , w
m
) последовательность
(v
1
, v
2
, . . . , v
m−n+c
, u
1
, u
2
, . . . , u
n−c
)
всех ребер графа G. Тогда фундаментальному циклу C
i
соответствует вектор
a = (a
i1
, . . . , a
im
), определенный по следующему правилу:
a
ij
=
(
1, если w
j
∈ C
i
,
0, если w
j
/
∈ C
i
.
Теперь фундаментальное множество циклов можно задать с помо- щью матрицы фундаментальных циклов, строки которой являются векторами a
1
, a
2
, . . . , a
ν(G)
:
C ­





a
11
a
12
. . .
a
1m
a
21
a
22
. . .
a
2m
. . . . . . . . . . . . . . . . . . .
a
ν(G),1
a
ν(G),2
. . . a
ν(G),m





.

4.12. РАЗРЕЗЫ
153
Так как каждый фундаментальный цикл C
i
содержит ровно одну хорду,
а именно v
i
, то матрица C имеет вид
C =





1 0
1 0
1
¯
¯
¯
¯
¯
¯
¯
¯
¯
a
1,ν(G)+1
. . .
a
1m
a
2,ν(G)+1
. . .
a
2m
. . . . . . . . . . . . . . . . .
a
ν(G),ν(G)+1
. . . a
ν(G)m





.
Таким образом, C = (C
0
1
|C
0
2
), где C
0
1
— единичная матрица порядка ν(G).
Пример 4.11.1. Найдем матрицу фундаментальных циклов графа G,
изображенного на рис. 4.45. Так как ν(G) = 8−
•
•
•
•
•
•
@
@
@
@
@
@
1 2
3 4
5 6
7 8
Рис. 4.45
− 6 + 1 = 3, то для получения остова удаляем из графа три ребра. Сопоставим этим ребрам номера 1, 2, 3.
Ребрам, входящим в остов, поставим в со- ответствие номера 4, 5, 6, 7, 8. Легко видеть,
что фундаментальный цикл C
1
, соответствую- щий хорде 1, состоит из ребер 1, 4, 6, цикл C
2
— из ребер 2, 6, 7, цикл C
3
—
из ребер 3, 6, 7, 8. Поэтому матрица фундаментальных циклов C имеет вид
C =
1 2 3 4 5 6 7 8
C
1
C
2
C
3


1 0 0 0 1 0 0 0 1
¯
¯
¯
¯
¯
¯
1 0 1 0 0 0 0 1 1 0 0 0 1 1 1

 . ¤
§ 4.12.
Разрезы
Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи воз- никают, например, при изучении потоков в сетях (сетью называется связ- ный орграф G = hM; Ri без петель; потоком в сети G называется функция
ϕ: R → Z, которая ставит в соответствие дуге некоторое число — вес ду- ги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т. е. множеств дуг, которые соединяют вершины двух непе- ресекающихся множеств вершин) и нахождение ограниченного поперечного

154
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
сечения, которое является самым узким местом. Эти узкие места определя- ют пропускную способность системы в целом.
Пусть G = hM; Ri — неорграф M = {M
1
, M
2
} — разбиение множества M .
Разрезом графа G (по разбиению M) называется множество всех ребер, соединяющих вершины из M
1
с
¾
½
»
¼
¾
½
»
¼
•
•
•
•
•
•
6 6
6
Разрез
M
1
M
2
Рис. 4.46
вершинами из M
2
(рис. 4.46). Отметим, что в связном графе любой разрез непуст.
Непустой разрез K неорграфа G называется про-
стым разрезом или коциклом, если любое непустое собственное подмножество K
0
$ K не является разре- зом ни по какому разбиению. Другими словами, из K
нельзя удалить ни одно ребро с тем, чтобы полученное множество было непустым разрезом.
Теорема 4.12.1. В конечном неорграфе G = hM; Ri, имеющем c ком-
понент связности, множество ребер K тогда и только тогда является
коциклом, когда граф hM; R \ Ki имеет (c + 1) компонент связности. ¤
Понятия остова и коцикла являются противоположными в том смысле,
что остову соответствует минимальное множество ребер, которые связыва- ют посредством маршрутов все вершины связного графа, а коцикл состоит из минимального множества ребер, отделяющего некоторые вершины связ- ного графа от остальных.
Следующие две почти очевидные теоремы дают информацию о связи остовов с разрезами, а также циклов с разрезами.
Теорема 4.12.2. В связном неорграфе остовное дерево имеет по край-
ней мере одно общее ребро с любым из разрезов графа. ¤
Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым раз-
резом четное число общих ребер. ¤
В условиях, указанных в предыдущем параграфе, рассмотрим неор- граф G с остовом T . Снова пусть u
1
, u
2
, . . ., u
n−c
— ветви остова T . Удаляя из остова T произвольную ветвь u
i
, получаем лес с (c + 1) компонентами связности, т. е. каждое ребро u
i
является разрезом остова T по некоторому разбиению {M
1
, M
2
} (рис. 4.47).
В графе G могут найтись еще какие-то ребра v
i
1
, v
i
2
, . . ., v
i
j
(являю- щиеся хордами T ), которые соединяют вершины из M
1
и M
2
. Множество

4.12. РАЗРЕЗЫ
155
K
i
= {u
i
, v
i
1
, . . . , v
i
j
} образует простой разрез, который называется фунда-
ментальным разрезом графа G относительно ветви u
i
остова T . Множе- ство {K
1
, K
2
, . . . , K
n−c
} всех фундаментальных разрезов графа G называет- ся фундаментальным множеством коциклов графа G относительно осто- ва T . Отметим, что мощность фундаментального множества коциклов не за- висит от выбора остова T и равна корангу ν
∗
(G) = n − c.
Аналогично фундаментальным циклам каж-
º
¹
·
¸
º
¹
·
¸
•
•
•
•
•
•
•
u
i
M
1
M
2
Рис. 4.47
дому фундаментальному разрезу K
i
ставится в соответствие вектор b
i
= (b
i1
, . . . , b
im
), опре- деляемый по правилу
b
ij
=
(
1, если w
j
∈ K
i
,
0, если w
j
/
∈ K
i
.
Фундаментальное множество коциклов задает- ся матрицей фундаментальных разрезов K, строки которой являются век- торами b
1
, b
2
, . . ., b
ν
∗
(G)
:
K =




b
11
. . .
b
1m
b
21
. . .
b
2m
. . . . . . . . . . . . . . .
b
ν
∗
(G),1
. . . b
ν
∗
(G),m



 .
Поскольку каждый фундаментальный разрез K
i
содержит ровно одну ветвь, а именно u
i
, матрица K имеет вид
K =




b
11
. . .
b
1,ν
∗
(G)
b
21
. . .
b
2,ν
∗
(G)
. . . . . . . . . . . . . . . . .
b
ν
∗
(G),1
. . . b
ν
∗
(G),ν
∗
(G)
¯
¯
¯
¯
¯
¯
¯
¯
¯
1 0
1 0
1





.
Таким образом, K = (K
0
1
|K
0
2
), где K
0
2
— единичная матрица порядка ν
∗
(G).
Отметим, что если C = (C
0
1
|C
0
2
) — соответствующая матрица фундаменталь- ных циклов, то K
0
1
= (C
0
2
)
T
Пример 4.12.1. Найдем матрицу фундаментальных разрезов графа G =
= hM; Ri, изображенного на рис. 4.45. Поскольку ν
∗
(G) = 6 − 1 = 5, имеется пять фундаментальных разрезов. Ребру 4 соответствует коцикл K
1
= {1, 4},

156
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
так как при удалении ребра 4 из остова T множество вершин M разбивается на две части: {a
1
} и M \ {a
1
}, а ребра 1 и 4 образуют разрез по разбиению
{{a
1
}, M \ {a}}. Аналогично ребру 5 соответствует коцикл K
2
= {5}, реб- ру 6 — коцикл K
3
= {1, 2, 3, 6}, ребру 7 — коцикл K
4
= {2, 3, 7}, ребру 8 —
коцикл K
5
= {3, 8}. Следовательно, матрица фундаментальных разрезов имеет вид
K =
1 2 3 4 5 6 7 8
K
1
K
2
K
3
K
4
K
5






1 0 0 0 0 0 1 1 1 0 1 1 0 0 1
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1






. ¤
§ 4.13.
Векторные пространства, связанные с графами
Рассмотрим алгебраическую систему Z
2
= h{0, 1}; ⊕, ¯i с двухместны- ми операциями кольцевого сложения ⊕ и умножения ¯, задаваемыми следу- ющими правилами: 0⊕0 = 1⊕1 = 0, 1⊕0 = 0⊕1 = 1, 0¯0 = 0¯1 = 1¯0 = 0,
1 ¯ 1 = 1. Система Z
2
является булевым кольцом (см. § 2.6) и, более того,
образует поле.
Пусть G = hM; Ri — связный неорграф, имеющий n вершин и m ребер u
1
,
u
2
, . . ., u
m
. Произвольному множеству ребер A ⊆ R поставим в соответствие вектор a = (a
1
, a
2
, . . . , a
m
), положив
a
i
­
(
1, если u
i
∈ A,
0, если u
i
/
∈ A.
Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора (a
1
, a
2
, . . . , a
m
) нулей и единиц най- дется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества ребер R и множе- ством всех наборов длины m, состоящих из нулей и единиц: P(R) ↔ {0, 1}
m
Пусть a = (a
1
, . . . , a
m
) и b = (b
1
, . . . , b
m
) — наборы (векторы) из {0, 1}
m
. Опре- делим сложение векторов с помощью соотношения a⊕b = (a
1
⊕b
1
, . . . , a
m
⊕b
m
)
по правилам, определенным в поле Z
2
. Кроме этого, определим произведение векторов на элементы λ ∈ {0, 1}, положив λ¯a = (λ¯a
1
, . . . , λ¯a
m
). Множе- ство векторов {0, 1}
m
с операциями сложения ⊕ и умножения ¯ на элементы

4.13. ВЕКТОРНЫЕ ПРОСТРАНСТВА, СВЯЗАННЫЕ С ГРАФАМИ
157
поля Z
2
образует линейное пространство над полем Z
2
. Это пространство обозначим через V
m
(Z
2
).
Отметим, что сложение ⊕ векторов a и b соответствует кольцевой сумме множеств ребер A и B, представляемых этими векторами. Действительно,
равенство a
i
⊕ b
i
= 1 выполняется тогда и только тогда, когда a
i
= 1, b
i
= 0
(т. е. u
i
∈ A \ B) или a
i
= 0, b
i
= 1 (т. е. u
i
∈ B \ A). Следовательно, сумме
a ⊕ b соответствует множество (A \ B) ∪ (B \ A) = A ⊕ B.
Внутреннее произведение векторов a = (a
1
, a
2
, . . . , a
m
) и b = (b
1
, b
2
,
. . . , b
m
) определяется соотношением
(a, b) = a
1
¯ b
1
⊕ a
2
¯ b
2
⊕ . . . ⊕ a
m
¯ b
m
.
Равенство (a, b) = 0 означает, что четное число произведений a
i
¯ b
i
равно 1.
Для таких произведений a
i
= 1, b
i
= 1 и, следовательно, соответствующие векторам a и b множества ребер A и B имеют четное число общих ребер.
Множество ребер A называется границей (кограницей), если A есть объ- единение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A
1
⊕ A
2
границ (кограниц) A
1
и A
2
также является границей (когра- ницей). Следовательно, множества
V
Γ
= {a | вектор a соответствует некоторой границе},
V
K
= {b | вектор b соответствует некоторой когранице}
образуют линейные подпространства пространства V
m
(Z
2
).
Теорема 4.13.1. 1. Если {C
1
, C
2
, . . . , C
m−n+1
} — фундаментальное мно-
жество циклов графа G, то множество B
C
­ {a
1
, a
2
, . . . , a
m−n+1
} векто-
ров, соответствующих фундаментальным циклам, образует базис подпро-
странства границ V
Γ
.
2. Если {K
1
, K
2
, . . . , K
n−1
} — фундаментальное множество коциклов
графа G, то множество B
K
= {b
1
, b
2
, . . . , b
n−1
} векторов, соответствую-
щих фундаментальным разрезам, образует базис подпространства когра-
ниц V
K
.
Следствие 4.13.2. 1. Размерность dim V
Γ
подпространства границ V
Γ
равна цикломатическому числу ν(G), а размерность dim V
K
подпростран-
ства кограниц V
K
равна корангу ν
∗
(G).
2. Любой цикл (коцикл) в графе можно представить в виде коль-
цевой суммы некоторых фундаментальных циклов (разрезов).