ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13031
Скачиваний: 110
246
Рис. П.3
Два ребра с общей вершиной, или две вершины, являющиеся концевыми точка-
ми ребра, называют смежными. Вершина является изолированной, если она не ин-
цидентна никакому ребру. Обозначим граф следующим образом:
(
)
,
G
V E
=
.
Подграф графа
G
– это подмножество
1
V
множества вершин
V
и подмножество
1
E
множества ребер
E
с теми же связями между вершинами и ребрами, что и в
G
.
Граф называют простым, если он не имеет ни петель, ни параллельных ребер,
т. е. кратных ребер между парами вершин. В основном будем рассматривать про-
стые графы, но поскольку в определение графов введены петли и параллельные
ребра, при рассмотрении непростых графов будем вносить ясность.
С каждым ребром можно ассоциировать направления или ориентацию, указан-
ную стрелкой. Тогда граф называют направленным (ориентированным) графом и его
ребра называют дугами (см. рис. П.2). Направленный граф обозначают так:
(
)
,
D
V A
=
.
Число ребер инцидентных вершине
v V
∈
называют степенью вершины и обо-
значают
( )
d x
. Обозначим
( )
d v
−
число дуг, направленных к
v
, а
( )
d v
+
– число
дуг, направленных от
v
. При определении степени инцидентная вершине петля счи-
тается дважды. Для изолированной вершины имеем
( )
0
d v
=
.
Обозначим число вершин и число ребер графа
(
)
,
G
V E
=
через
V
и
E
соот-
ветственно,
V
называют степенью графа. Граф на рис. П.З имеет
7
V
=
и
10
E
=
.
Граф называется конечным, если и
V
и
E
конечны, в противном случае – граф
бесконечный. Рассматривать будем только конечные графы. Степень
1
v
графа на
рис. П.З равна 5:
7
v
– изолированная вершина.
Легко показать, что в любом графе число вершин нечетной степени четно. Для
этого отметим, что
( )
2
v V
d v
E
∈
=
∑
, так как каждое ребро считается дважды. Если
обозначить через
0
V
и
e
V
множество вершин, имеющих нечётные и чётные степени
соответственно, то получим этот результат, учитывая, что
247
( )
( )
0
2
e
v V
v V
v V
d v
d v
dv
E
∈
∈
∈
+
=
=
∑
∑
∑
,
следовательно,
( )
e
v V
d v
∈
∑
– четное число. Это может быть только в том случае, если в
сумму входит четное число членов.
Последовательность
n
ребер
1
,
,
n
e
e
…
в графе
G
называется маршрутом, если
существует соответствующая последовательность
1
n
+
(не обязательно различных)
вершин
0
1
, ,
,
n
v v
v
…
, таких, что
i
e
инцидентно
1
i
v
−
и
i
v
,
1,
,
i
n
= …
. Маршрут замкнут
(циклический), если
0
n
v
v
=
, в противном случае разомкнут. Если
i
j
e
e
≠
для всех
i
и
j
,
i
j
≠
, маршрут называют цепью. Замкнутая цепь называется циклом (конту-
ром). Если все вершины различны, маршрут называется простой цепью, в то время
как при
0
n
v
v
=
и различных всех остальных вершинах имеем простой цикл при ус-
ловии
3
n
≥
. Пример простой цепи дан последовательностью ребер
{
} (
) (
) (
) (
)
{
}
3
4
7
2
6
1
1
5
5
2
2
3
, , ,
,
,
,
,
,
,
,
e e e e
v v
v v
v v
v v
≡
на рис. П.1. Здесь каждое ребро в последовательности заменено парой вершин, ко-
торые являются его концевыми точками, так как следуют друг за другом в маршруте
6
1
5
2
3
, , , ,
v v v v v
. Аналогичные определения могут быть даны для направленных гра-
фов, если учитывать направление каждой дуги. Здесь речь идет о направленных
(ориентированных) маршрутах, путях и контурах, а также о простых путях и про-
стых контурах.
Граф называют связным (сильно связным) в ненаправленном (направленном)
смысле, если существует простая цепь (путь) между любой парой вершин. Граф с
1
n
+
вершинами является
n
-связным, если после удаления
1
n
−
или менее вершин
он остается связным. Две цепи называют параллельными, если у них нет общих вер-
шин, за исключением их концевых точек.
Компонента
C
графа
G
– максимальный связный подграф (т. е. каждая верши-
на, которая смежна вершине в
C
, также принадлежит
C
, и все ребра
G
инцидент-
ные вершинам
C
, также принадлежат
C
).
Поддерево – это связный подграф, не имеющий циклов. Перекрывающее дерево
– это (максимальное) поддерево, которое содержит все вершины графа. Ребро гра-
фа, не принадлежащее дереву, называют хордой. Ребро графа, принадлежащее де-
реву, называют ветвью. Когда хорда добавляется к перекрывающему дереву, в ре-
зультате получается цикл, который называется фундаментальным циклом. На
рис. П.4 приводится перекрывающее дерево для направленного графа. Корень де-
рева находится в вершине
0
v
, из которой начинаются все пути, существующие на
дереве.
Рис. П.4
248
Рис. П.5
Рис. П.6
Специальный тип цикла в графе, важный для практических применений, назван
в честь известного ирландского математика Уильяма Гамильтона (1805–1865). Мы
называем цикл, который проходит через каждую вершину графа только однажды,
гамильтоновым циклом. В то же время отметим, что имя швей царского математика
Л. Эйлера (1707—1783) ассоциируется с эйлеровым графом, в котором ребра фор-
мируют цепь с каждым ребром графа, включенным в цепь только однажды. Цепь
может быть разомкнута или может образовать цикл.
Два графа
(
)
,
G
V E
=
и
(
)
,
G
V E
′
′ ′
=
изоморфны друг другу, если существует
взаимно однозначное соответствие между
V
и
V ′
и между
E
а
E′
, сохраняющее
инцидентность. Например, два графа, показанные на рис. П.5, изоморфны.
Простой граф
(
)
,
G
V E
=
, у которого
V
n
=
и любая пара вершин соединена
ребром, называется полным графом для
n
-вершин. Легко убедиться, что полный
граф имеет
(
)
1 2
n n
−
ребер. Так как любые два полных графа, имеющие одинако-
вое число вершин, изоморфны, говорят о полном графе для
n
-вершин.
Граф называется двудольным, если его вершины могут быть так разделены на
два непересекающихся множества, что ребра графа будут только соединять верши-
ны одного множества с вершинами другого (см. рис. П.6).
Обсуждение
Важным элементарным понятием, связанным с графом
G
на
n
вершинах, явля-
ется связность. По сути, большая часть алгоритмической теории графов имеет отно-
шение к связности, ее избыточности и даже ее отсутствию в графе.
Граф не связан (или несвязный), когда множество вершин
V
может быть разде-
лено на два множества
1
V
и
2
V
так, что нет ребра, соединяющего вершину в
1
V
с
вершиной в
2
V
, в противном случае говорят, что граф связный. Хотя две вершины
могут не быть прямо связанными ребром, оказывается возможно достижение одной
из этих вершин из другой простой цепью. Если такая цепь, соединяющая любую па-
ру вершин, имеется, то говорят, что граф связный. Иногда предпочитают примене-
249
ние первого определения, но чаще используется эквивалентное ему второе опреде-
ление. В действительности второе определение намного богаче, так как охватывает
целую область проблем достижимости графа или подграфов этого графа. Например,
можно начать требовать большего. Можно ли начать с вершины и пройти по ребрам
графа последовательно без повторения? Можно ли проделать это и закончить пере-
мещение на начальной вершине? Можно ли, стартуя с вершины, пройти простую
цепь через все вершины с возвращением или без возвращения к начальной верши-
не? Можно ли проделать это, если рассматривать только подграфы
1
n
−
вершин?
Другой вопрос касается того, насколько велика связность графа. Имеются два
пути исследования этой проблемы: через ребра графа и через его вершины. Граф
можно сделать несвязным, убрав одновременно несколько ребер.
Минимальный набор из таких ребер известен как разрез, а наименьшее число
ребер в разрезе называется степенью связности графа. Степень связности дерева
равна единице. Ясно, что дерево – это наиболее слабый тип связного графа. С дру-
гой стороны, если убрать из цикла ребро, то останется связный граф (фактически
дерево).
В терминах реберной связности величину связности графа можно измерить через
минимальное число цепей, связывающих любую пару вершин, или через сущест-
вующие простые циклы различных размеров. Цепи и циклы, с одной стороны, и раз-
резы – с другой, являются двумя дополнительными путями изучения связности и ее
отсутствия. Даже вопросы планарности (построение графа на плоскости без пересе-
чений ребер в точках, не являющихся вершинами) и непланарности графов относят-
ся к связности. Уменьшая число ребер непланарного графа, его можно сделать пла-
нарным.
Существуют два подхода к изучению того, как вершины разделяют граф. Первый
ассоциируется с понятием степени вершины. Например, если в дереве с вершиной
степени два исключить ее вместе с инцидентными ей ребрами, то оставшийся граф
будет несвязным. С другой стороны, если граф является простым циклом и, следо-
вательно, любая вершина имеет степень два, исключение вершины не превратит
граф в несвязный. Представляется допустимым тот факт, что чем выше степени
вершин, тем сильнее будет связность. Однако выражение такого типа слишком об-
щее и нуждается в уточнении в контексте конкретной проблемы.
Вершина графа называется точкой артикуляции, или разделяющей вершиной,
если ее исключение делает граф несвязным. Кратность разделяющей вершины – это
число компонент, на которые распался граф после ее удаления. Может существо-
вать более чем одна вершина, являющаяся точкой артикуляции. Например, на рис.
П.1
2
v
и
5
v
– точки артикуляции,
6
v
не является таковой. Набор точек артикуляции
образует множество вершин артикуляции, которые в контексте коммуникационных
сетей можно считать «узким местом» графа. Конечно, граф может не иметь точки
артикуляции (такой граф называют несепарабельным), однако удаление одновре-
менно
k
вершин делает его несвязным. Такое множество известно как множество
артикуляции степени
k
.
Граф
k
-связный,
0
k n
≤ ≤
, если удаление
1
k
−
или менее вершин не делает его
несвязным. Любая пара вершин такого графа может быть соединена
k
параллель-
ными цепями (из которых никакие две не имеют общих вершин). Граф, не имеющий
множества артикуляции степени
k
, называется
k
-несводимым. В противном случае
говорят, что граф
k
-сводимый.
До сих пор речь шла об общем ненаправленном графе. Вопросы связности не-
сколько усложняются, если ребрам графа приписываются направления. Здесь граф
может быть связным в ненаправленном смысле и может быть, но только слабо связ-
ным, в направленном смысле. Следовательно, возможен путь из одной вершины в
250
другую, но не наоборот, т. е. граф – не сильно связный. Ясно, что циклы играют
важную роль в сильно связных графах.