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

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

1
2. ТЕОРИЯ ГРАФОВ
2.1. Общие понятия теории графов
Теория графов – это математический аппарат, применяемый для формализации (моделирования) реальных задач по исследованию свойств конечных множеств с заданными отношениями между их элементами. В их числе задачи из области администрирования сетей, информационных потоков, планирования, проектирования и управления различными системами.
Определение. Графом
Г называется любая пара
(
)
Х
V ,
, где
{ }
i
v
V =
– множество элементов произвольной природы, называемых вершинами графа;
{ }
k
x
X =
(k=
1,...,m) – семейство пар из V :
)
,
(
j
i
k
v
v
x
=
(i, j=
1,...,n).
Задачи на графах удобно переводить на языки программирования, т. е. решать с использованием современной вычислительной техники.
Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис.
2.1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.
Рис. 2.1. Пример графа
Широкое определение графа допускает любую трактовку: множество предприятий с экономическими отношениями, множество людей с психологической совместимостью, система управления с подчинением, технические системы со связями, электрические цепи с источниками и потребителями, транспортные сети. Поэтому язык теории графов получил распространение в химии, физике, лингвистике, экономике, психологии и т.д.

2
Определение.Неориентированным графом G = (V, X) называется пара множеств: V – множество, элементы которого называются
вершинами, X – множество неупорядоченных пар вершин, называемых ребрами.
Если вершины v, w∈V, x=(v,
w)∈X, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом,
{v,
w} – обозначение ребра.
Если Х представляет собой упорядоченные пары (т. е. X – подмножество декартова произведения V×V), то граф называется
ориентированным (орграфом), а пары (v,
w) называют дугами.
Замечание. Граф, в котором присутствуют и ребра, и дуги, называется смешанным. Записывается упорядоченной тройкой
G=
(V, X, A), где V – множество вершин, X – множество ребер и A – множество дуг.
Очевидно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Если множеству X принадлежат пары v=
w, то такие ребра {v,
v}
(дуги (v,
w)) называют петлями.
Существование одинаковых пар {v,
w} (или (v,
w)) соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер (дуг) называют количество таких одинаковых пар.
Пример
Кратность ребра {v
1
, v
2
} в графе на рис.
2.2 равна двум, кратность ребра {v
3
, v
4
} − трем.
Рис. 2.2. Пример графа с кратными ребрами
Определения
Псевдограф – граф, в котором есть петли и/или кратные ребра.
Мультиграф – псевдограф без петель.
Простой граф – граф без кратных ребер и петель.
Граф, состоящий из одной вершины, называется тривиальным.

3
Будем применять следующие обозначения:
V – множество вершин;
X – множество ребер или дуг;
v (или v
i
) – вершина;
G – неориентированный граф;
D – орграф;
{v,
w} – ребро неориентированного графа;
(v,
w) – дуга в орграфе;
{v,
v}, (v,
v) – обозначение петли;
x, y, z – ребра и дуги;
n(G), n(D),
n
V
= – мощность множества вершин графа;
m(G) (m(D)),
m
X
= – мощность множества ребер (дуг).
Примеры
Орграф D=
(V, X) (рис. 2.3), V=
{v
1
, v
2
, v
3
, v
4
},
X=
{x
1
=
(v
1
, v
2
), x
2
=
(v
1
, v
2
), x
3
=
(v
2
, v
2
), x
4
=
(v
2
, v
3
)}.
Рис. 2.3. Пример орграфа
v
3
– висячая вершина; v
4
– изолированная вершина
Неориентированный граф (рис.
2.4):
G=
(V, X), V=
{v
1
, v
2
, v
3
, v
4
, v
5
},
X=
{x
1
=
{v
1
, v
2
}, x
2
=
{v
2
, v
3
}, x
3
=
{v
2
, v
4
}, x
4
=
{v
3
, v
4
}}.
Рис. 2.4. Пример неориентированного графа
v
1
– висячая вершина; v
5
– изолированная вершина

4
Определения
Если x=
{v,
w} – ребро, то v и w − концы ребра x.
Если x=
(v,
w) – дуга орграфа, то v − начало, w – конец дуги.
Вершина v и ребро x неориентированного графа (дуга x орграфа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).
Вершины v, w называются смежными, если {v,
w}∈X.
Ребра называются смежными, если они инцидентны одной и той же вершине.
Определение.Полный граф – это простой граф, в котором любые две вершины смежные, обозначается K
n
, где n – число вершин.
Замечание.Число ребер полного неориентированного графа
(
)
2 1
2
−
=
n
n
C
n
На рис. 2.5 показаны неориентированные полные графы и их число ребер.
Рис. 2.5. Полные графы K
1
, K
2
, K
3
и K
4
Определение. Степенью вершины v графа G называется число
δ(v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0, называется изолированной, а степень 1 – висячей (см. рис.
2.3, 2.4).
Определение. Полустепенью исхода (захода) вершины v орграфа D называется число deg
–
(v) (deg
+
(v)) дуг орграфа D, исходящих из v
(заходящих в v).
В случае ориентированного псевдографа вклад каждой петли, инцидентной вершине v, равен 1 как в deg
–
(v), так и в deg
+
(v).

5
Определение. Регулярный граф – граф, степень каждой вершины которого равна r.
Замечание. Графы K
n
являются регулярными графами степени
n – 1.
Определение. Граф G называется двудольным, если его множество вершин можно разбить на два непересекающихся подмножества:
2 1
V
V
V
∪
=
, причем для любого ребра x = {v
i
,
v
j
} вершины v
i
и v
j
принадлежат разным подмножествам.
Если каждая вершина из
1
V соединена ребром с каждой из
2
V , то граф называется полным двудольным графом, обозначается
n
q
K
,
, где
q, n – мощности подмножеств
1
V и
2
V , т. е.
n
V
q
V
=
=
2 1
,
Пример
На рис. 2.6 показан граф
3
,
3
K
Рис. 2.6. Полный двудольный граф K
3,3
Лемма о рукопожатиях. Если в графе
(
)
X
V
G
,
=
m
X
n
V
=
= ,
, то
∑
=
=
n
i
i
m
v
1 2
deg
Доказательство леммы очевидно: каждое ребро в этой сумме участвует ровно два раза, так как имеет два конца.
Следствие. Число вершин графа G с нечетной степенью четно.
Определение.Графы
(
)
1 1
1
, X
V
G =
и
(
)
2 2
2
, X
V
G =
называются
изоморфными, если существует биекция
2 1
:
V
V
f
→
, причем если пара
{
}
1
,
X
v
v
j
i
∈
, то пара
( )
( )
{
}
2
,
X
v
f
v
f
j
i
∈
и наоборот.
Таким образом, одна и та же система объектов и связей между ними может быть изображена разными способами. Способы эти и будут изоморфными графами. Для установления изоморфизма

6 достаточно одинаково занумеровать вершины графа множества
1
V и соответствующие им при биекции f вершины множества
2
V .
Пример
На рис. 2.7 показаны примеры изоморфных графов
а
б
Рис. 2.7. Пары изоморфных графов
Отношение изоморфизма графов представляет собой отношение
эквивалентности и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности (см. подглаву 1.4).
Определение.Дополнительный граф (или дополнение) графа G – это граф
G , определяемый следующим образом:
|
|
|
:|
G
G
V
V
G
=
, и любые две несовпадающие вершины смежны в
G тогда и только тогда, когда они не смежны в G (рис. 2.8, а, б).
а
б
в
Рис. 2.8. Граф (a), его дополнение (б), самодополнительный граф (в)
Очевидно, что
G
G =
и объединение
G и G дает полный граф на том же множестве вершин.
Определение.Граф, изоморфный своему дополнению, называется
самодополнительным.
Пример
На рис.
2.8,
в пунктиром показан граф, который изоморфен своему дополнению, графу, изображенному сплошной линией.

7
2.2. Маршруты и пути
Определение. Последовательность v
1
x
1
v
2
x
2
v
3
…x
k
v
k+1
(где
1
≥
k
,
v
i
∈V, i = 1,…,k + 1, x
j
∈X, j=
1,…,k), в которой чередуются вершины и ребра (дуги) и для каждого j=
1,…,k ребро (дуга) x
j
имеет вид {v
j
,v
j+1
}
(для орграфа (v
j
,v
j+1
)), называется маршрутом, соединяющим вершины v
1
и v
k+1
(путем из v
1
в v
k+1
).
Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v
1
=
v
k+1
Пример
В графе на рис.2.4 v
1
x
1
v
2
x
2
v
3
x
4
v
4
x
3
v
2
– маршрут, v
2
x
2
v
3
x
4
v
4
–
подмаршрут; маршрут можно восстановить и по записи x
1
x
2
x
4
x
3
; если кратности ребер (дуг) равны 1, то можно записать и так:
v
1
v
2
v
3
v
4
v
2
Определения
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) различны, т.е. не повторяются.
Цикл (контур) − замкнутый маршрут (путь), в котором все ребра
(дуги) различны, т.е. не повторяются.
Простая цепь – цепь, в которой все вершины различны.
Простой цикл (контур) − цикл (контур), в котором все вершины
(кроме первой и последней) различны, т.е. не повторяются.
Гамильтонова цепь (цикл, контур) – простая цепь (цикл, контур), проходящая через все вершины графа ровно по одному разу.
Эйлерова цепь (цикл, контур) – цепь (цикл, контур), содержащая все ребра (дуги) графа по одному разу.
Длина маршрута (пути) – число ребер в маршруте (дуг в пути).
Пример
Рассмотрим четыре графа и определим наличие в них эйлеровых и гамильтоновых цепей и циклов.
Утверждение 1
Для того чтобы связный (для любых двух вершин графа существует маршрут их соединяющий) псевдограф G обладал эйлеровым циклом,

8 необходимо и достаточно, чтобы степени всех его вершин были четными.
Утверждение 2
Для того чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.
В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).
Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.
Определение.Минимальный маршрут (путь) – маршрут (путь) с наименьшим числом ребер (дуг).
Каждый минимальный маршрут (путь) является простой цепью.
Пусть
k
k
v
v
v
v
v
≠
=
Π
1 2
1
,
– минимальный маршрут (путь) в графе G
(в орграфе D). Тогда для любых i и j таких, что
k
j
i
≤
<
≤
1
, маршрут
(подпуть)
j
i
i
v
v
v
1 0
+
=
Π
тоже является минимальным.
Эйлеровы и гамильтоновы циклы сходны по способу задания.
Но, несмотря на внешнее сходство, задачи их поиска резко отличаются по степени трудности. Для решения вопроса о наличии эйлерова цикла или цепи в графе достаточно применить утверждения
1 и 2. Критерий же существования гамильтонова цикла в произвольном графе еще не найден.
Граф
Эйлеров цикл
Эйлерова цепь
Гамильтонов цикл
Гамильтонова цепь

9
Решение этой проблемы имеет практическую ценность, так как к ней близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован в том, чтобы затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени.
Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе.
1) Всякий полный граф содержит гамильтонов цикл.
Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа.
2) Если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие ребра, то он все равно содержит гамильтонов цикл.
Если граф, содержащий гамильтонов цикл, объединить с еще одной вершиной ребром так, что образуется висячая вершина, то такой граф больше не содержитгамильтонов цикл.
Поиск необходимого и достаточного условия для того, чтобы граф содержал гамильтонов цикл, стал одной из главных задач теории графов. О таких графах известно немного. Большинство известных теорем имеет вид «если граф G имеет достаточное число ребер, то он содержит гамильтонов цикл». Вероятно, самой знаменитой из этих теорем является теорема, принадлежащая
Г. Э. Дираку.
Теорема Дирака. Если в связном простом графе
(
)
X
V
G
,
=
3
,
≥
=
n
n
V
степени всех его вершин
2
/
deg
n
v
i
≥
(
n
i
,
,
1 K
=
), то граф содержит гамильтонов цикл. Обратное не верно.

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