Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов

• Название: 2. теория графов общие понятия теории графов
• Анкор: Теория графов
• Дата: 30.09.2022
• Размер: 1.41 Mb.
• Имя файла: 02 Теория графов.pdf
• Тип: Документы; #706797
• страница: 2 из 8

Определение.Матрицей смежности неориентированного графа
G = (V, X) называется квадратная симметричная матрица A(G) = [a
ij
] порядка n, где
{ }
{
}



∉
∈
=
,
,
0
,
,
,
1
X
v
v
X
v
v
a
j
i
j
i
ij
Определение.Матрицей инцидентности графа G называется матрица B(G) = [b
ij
] порядка n
×
m, где



−
−
=
ребру инцидентна не
,
0
;
ребру инцидентна
,
1
j
i
j
i
ij
x
v
x
v
b
Пример
Рассмотрим граф (рис. 2.9).
Рис. 2.9. Пример орграфа для построения матриц A(D) и B(D)

11
Матрицы смежности и инцидентности для данного орграфа имеют вид:
матрица смежности матрица инцидентности
0 0
1 1
0 1
0 1
0
)
(
3 2
1 3
2 1
v
v
v
v
v
v
D
A
=
0 1
1 1
1 0
0 1
1 1
0 1
)
(
4 3
2 1
3 2
1
−
−
−
−
=
x
v
v
v
x
x
x
D
B
Замечание.
Для изоморфных графов, вершины которых занумерованы произвольным образом, матрицы смежности различны, но они получаются друг из друга одинаковыми перестановками строк и столбцов. То же самое верно для матриц инцидентности.
Определение.
Матрицей
Кирхгофа называют квадратную матрицу K(G)=
[k
ij
] порядка n , где





=
≠
−
=
если
,
deg смежны;
не и
вершины и
если
0,
смежны;
и вершины если
,
1
j
i
v
j
i
j
i
j
i
k
i
ij
Сумма элементов в каждой строке и в каждом столбце матрицы равна 0.
Пример
Рассмотрим граф (рис. 2.10).
Рис. 2.10. Пример графа для построения матрицы Кирхгофа

12
Матрица Кирхгофа для данного графа имеет вид
=
ij
K


















−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
3 0
0 1
1 1
0 3
0 1
1 1
0 0
3 1
1 1
1 1
1 3
0 0
1 1
1 0
3 0
1 1
1 0
0 3
6 5
4 3
2 1
6 5
4 3
2 1
v
v
v
v
v
v
v
v
v
v
v
v
2.4. Связность. Компоненты связности
Определение. Подграфом графа G (орграфа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).
Подграф называется собственным, если он отличен от самого графа.
Замечание.Говорят, что вершина w графа G (орграфа D)
достижима
из вершины v, если либо w=
v
, либо существует маршрут
(путь) из v в w.
Определение.Неориентированный граф (орграф) называется
связным
(сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.
Орграф называется односторонне связным, если для любых двух его вершин, по крайней мере, одна достижима из другой.
Орграф называется
слабо
связным
, если соответствующий неориентированный граф является связным.
Связность вершин неориентированного графа, как и сильная связанность вершин орграфа, задает некоторое отношение
R
на множестве вершин. Рассмотрим R для орграфа. Пара
R
v
v
j
i
∈
)
,
(
тогда и только тогда, когда существует путь из вершины
i
v
в
j
v
. Будем считать, что
R
v
v
i
i
∈
)
,
(
(длина пути в этом случае равна 0). Если
R
v
v
j
i
∈
)
,
(
, то
R
v
v
i
j
∈
)
,
(
. Если
R
v
v
j
i
∈
)
,
(
и
R
v
v
k
j
∈
)
,
(
, тогда,

13 очевидно,
R
v
v
k
i
∈
)
,
(
, таким образом, отношение
−
R
рефлексивно, симметрично и транзитивно, следовательно, оно является
отношением
эквивалентности
Отношение эквивалентности позволяет разбить множество вершин V на классы эквивалентности:
m
k
V
V
V
V
∪
∪
∪
∪
=
K
K
1
, где
∅
=
∩
j
i
V
V
Две вершины
V
v
v
j
i
∈
и связаны тогда и только тогда, когда они принадлежат одному классу эквивалентности.
Определение. Компонентой связности графа G (сильной
связности
орграфа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).
Каждый неориентированный граф единственным образом представляется в виде объединения своих компонент связности.
Примеры
На рис.
2.11 показан граф, состоящий из четырех компонент связности.
Рис. 2.11. Пример неориентированного графа из четырех компонент связности
Примеры компонент сильной связности орграфов приведены на рис. 2.12, причем компонентой сильной связности может быть и изолированная вершина, так на рис. 2.12, в показаны две компоненты сильной связности.
а б в
Рис. 2.12. Примеры компонент сильной связности орграфов

14
Теорема о связи вершин с нечетными степенями
Если в графе G есть ровно две вершины с нечетными степенями, то они связаны.
Доказательство. Пусть
1
v
и
−
2
v
вершины с нечетными степенями.
Если они принадлежат одной компоненте связности, то они связаны.
Если они принадлежат разным компонентам связности, т. е.
i
G
v ∈
1
,
k
G
v ∈
2
, то в графе
k
G
, например, всего одна вершина с нечетной степенью, чего не может быть.
Лемма о присоединении ребра
Если
(
)
−
=
Х
V
G
,
связный граф,
1
v
и
−
2
v
две разные его вершины и
{
}
X
v
v
∉
2 1
,
, тогда добавление к графу ребра
{
}
2 1
, v
v
приводит к образованию простого цикла.
Доказательство. G – связный граф, поэтому существует маршрут
)
,
(
2 1
v
v
P
, в нем можно выделить подмаршрут
)
,
(
2 1
v
v
P′
, который будет простой цепью.
Маршрут
)
,
(
1 2
v
v
P ′′
, который получается из
2
v
в
1
v
по вершинам и ребрам пути P′ , также будет простой цепью. Рассмотрим маршрут:
2
v
,
(
)
1 2
, v
v
P ′′
,
1
v
,
)
,
(
2 1
v
v
,
2
v
, он будет простым циклом.
Лемма об удалении ребра
Пусть
(
)
X
V
G
,
=
– связный граф, ребро
{
}
2 1
, v
v
x =
входит в цикл C , тогда граф
1
G
, полученный из G удалением ребра x , будет связным.
Доказательство. Пусть
i
v
и
j
v
– произвольные вершины графа. Так как граф G связный, то существует маршрут
G
v
v
P
j
i
⊆
)
,
(
. Если этот маршрут не содержит ребро x , то
1
)
,
(
G
v
v
P
j
i
⊆
, т. е. эти вершины связаны маршрутом и в графе
1
G
. Если
)
,
(
j
i
v
v
P
проходит по ребру x, тогда он имеет вид
i
j
i
v
v
v
P
=
)
,
(
,
j
v
A
v
x
v
A
,
,
,
,
,
2 2
1 1
, где
2 1
, A
A
– последовательности ребер и вершин. Ребро x входит в цикл
1 2
1
,
,
,
,
v
A
v
x
v
C
′
=
, следовательно, существует цепь
1 2
1 2
'
)
,
(
v
A
v
v
v
P
=
′
, тогда существует
−
′′
)
,
(
2 1
v
v
P
противоположная цепь. Рассмотрим в этом случае маршрут
j
i
j
i
v
A
v
v
v
P
v
A
v
v
v
P
,
,
),
,
(
,
,
,
)
,
(
2 2
2 1
1 1
1
′′
=
, который не содержит ребро x и связывает вершины
i
v
и
j
v
в графе
1
G
, следовательно,
−
1
G
связный граф.

15
Лемма о числе компонент связности
Пусть G=
(V,
X
) – простой граф,
n
V =
,
m
X =
, k – количество компонент связности, тогда
m
n
k
−
≥
Причем если в G нет циклов, то
m
n
k
−
=
Лемма о максимальном числе ребер в графе
Пусть G = (V, X) – простой граф,
n
V =
, k – количество компонент связности, тогда максимальное число ребер в графе будет
( ) (
)(
)
2 1
,
+
−
−
=
k
n
k
n
k
n
m
Следствие. Если
2
=
k
, то
(
) (
)(
)
2 1
2 2
,
−
−
=
n
n
n
m
и это максимальное число ребер при двух компонентах связности, поэтому если
(
)(
)
2 1
2
−
−
>
n
n
m
, то граф связный.
Замечание. Для связного графа
1
=
k
и
2
)
1
(
)
1
,
(
−
= n
n
n
m
, а это число ребер в полном графе.
Пусть
A
(D)
– матрица смежности ориентированного псевдографа D=
(V,
X
) (или псевдографа G=
(V,
X
)), где
n
V =
Обозначим через
( )
[ ]
k
ij
k
a
A =
k-ю степень матрицы смежности A(D)
(или A(G)).
Элемент
( )
k
ij
a
матрицы A
k
ориентированного псевдографа
D=
(V,
X
) (псевдографа G = (V,
X
)) равен числу всех путей
(маршрутов) длины k из v
i
в v
j
Определение.Матрица достижимости орграфа D − квадратная матрица T(D) = [t
ij
] порядка n, элементы которой равны



=
случае.
противном в
,
0
,
из достижима
,
1
i
j
ij
v
v
t

16
Определение.Матрица сильной связности орграфа D – квадратная матрица S(D) = [s
ij
] порядка n, элементы которой равны



=
случае.
противном в
,
0
,
из достижима и
из достижима
,
1
j
i
i
j
ij
v
v
v
v
s
Определение.Матрица связности графа G − квадратная матрица
S
(G) = [s
ij
] порядка n, элементы которой равны



=
случае.
противном в
,
0
,
и й
соединяющи маршрут,
есть если
,
1
i
j
ij
v
v
s
Для того чтобы n-вершинный орграф D с матрицей смежности
A
(D) имел хотя бы один контур, необходимо, чтобы матрица
K
= A
2
+ A
3
+…+ A
n
имела хотя бы один ненулевой диагональный элемент.
Если A(D) – матрица смежности графа D, то элемент
n
ij
a матрицы А
п
равен числу путей длины п, соединяющих вершины v
i
и v
j
графа D.
В некоторых случаях при вычислениях степеней матрицы A(D) важно знать не число соответствующих путей, а только есть ли в графе эти пути или нет. Тогда при вычислении элементов матриц A
2
,
A
3
,…, A
n–1 используют функцию sign, которая равна 1, если число положительное, и 0, если число равно 0. В результате матрицы sign[A
2
], sign[A
3
], ..., sign[A
n–1
] состоят только из нулей и единиц.
Утверждение 3
Пусть D=
(V, X) – орграф,
n
V =
, A(D) – его матрица смежности. Тогда матрица достижимости находится следующим образом:
T
(D) = sign[E+A+A
2
+A
3
+…+A
n–1
], где E – единичная матрица порядка n.
Матрица сильной связности
орграфа находится по формуле
S
(D) = T(D)&T
T
(D), где T
T
– транспонированная матрица достижимости, операция «&» обозначает поэлементное умножение матриц, т. е. каждый элемент

17 матрицы S(D) равен
ji
ij
ij
t
t
s
×
=
произведению соответствующих элементов из матриц T(D) и T
T
(D).
Пусть G = (V, X) – неориентированный граф,
n
V =
, A(G) – его матрица смежности. Тогда его матрица связности находится аналогично матрице достижимости орграфа
S
(G) = sign[E + A + A
2
+ A
3
+…+ A
n–1
].
Под операцией удаления вершины из графа (орграфа) будем понимать операцию, заключающуюся в удалении некоторой вершины вместе с инцидентными ей ребрами (дугами).
Определение.Вершина графа, удаление которой увеличивает число компонент связности, называется точкой сочленения.
Замечание.
Изолированная вершина не является точкой сочленения.
Определение. Неразделимый граф – это связный граф без точек сочленения. Все другие графы – разделимые, включая несвязные.
Замечание. Связный граф G является разделимым тогда и только тогда, когда в графе G существует такая вершина v, что она является единственной общей вершиной для двух собственных нетривиальных подграфов G
1
и G
2
, объединение которых равно G.
Пример
На рис. 2.13 точками сочленения графа являются вершины v
3
, v
4
,
v
6
, v
7
Рис. 2.13. Пример графа с точками сочленения

18
2.5. Расстояния, нагруженный граф, деревья
Пусть
)
,
(
X
V
G =
– неориентированный граф (или псевдограф).
Определение.Расстоянием между вершинами
)
,
( w
v
d
называется минимальная длина маршрута между ними, при этом
0
)
,
(
=
v
v
d
,
∞
=
)
,
( w
v
d
, если не существует маршрута.
Условно понятие расстояния применимо и для орграфа.
Расстояние в графе удовлетворяет аксиомам метрики:
0
)
,
(
≥
w
v
d
,
w
v
w
v
d
=
⇔
= 0
)
,
(
;
)
,
(
)
,
(
v
w
d
w
v
d
=
(в неориентированном графе);
)
,
(
)
,
(
)
,
(
1 1
v
w
d
w
v
d
w
v
d
+
≤
;
∞
<
)
,
( w
v
d
в связном неориентированном графе.
Пусть
)
,
(
X
V
G =
связный граф (или псевдограф).