Реферат: Графы и их представление на ЭВМ

--PAGE_BREAK--3. Виды графов и операции над ними
3.1 Элементы графов
Для рассмотрения видов граф и операций над ними необходимо познакомиться с такими понятиями как подграфы, маршрут, цепь, цикл.

Граф G
'(
V
', Е') называется подграфом графа G
(
V
, Е) (обозначается G
' ÌG
), если V
' ÌV
и/или Е' ÌЕ.

Если V
' =
V
, то G

' называется остовным подграфом G
.

Если V
' ÌV

& Е' ÌЕ & (V
'
¹

V
ÚЕ'
¹
Е), то граф G

' называется собственным подграфом графа G
.

Подграф G
'(
V
', Е') называется правильным подграфом графа G
(
V
, Е), если G

' содержит все возможные ребра G
:
"
и,
v
ÎV
' (и,
v
)ÎЕ Þ
(и,
v
)ÎЕ'.
Правильный подграф G

'(
V

', Е') графа G

(
V
, Е) определяется подмножеством вер шин V

'.

Маршрутом в графе называется чередующаяся последовательность вершин и ребер в которой любые два соседних элемента инцидентны.
v, e1, v1, e2, v2,…,ek, vk,
Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v= vk, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v, e1, v1, e2, v2,…,ek, vk,

 вершины vи vk, называются концами цепи. Говорят, что цепь с концами и и v

соединяет вершины и и v
. Цепь, соединяющая вершины и и v
, обозначается (и, v
). Очевидно, что если есть цепь, соединяющая вершины и и v
, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G
обозначается z
(
G
). Граф без циклов называется ациклическим.

Элементы графа – любое чередование вершин и рёбер графа, в котором каждому ребру предшествует смежная ей вершина, называющаяся контуром графа.
<img width=«242» height=«171» src=«ref-1_1593943444-4980.coolpic» v:shapes="_x0000_i1028">

Рис 3.1 Маршруты, цепи, циклы
По рисунку 3.1 можно определить следующие утверждения:

1.                 A, C, A, D– маршрут, но не цепь;

2.                 A, C, E, B, C, D– цепь, но не простая цепь;

3.                 A, D, C, B, E, — простая цепь;

4.                 A, C, E, B, C, D, A– цикл, но не простой цикл;

5.                 A, C, D– простой цикл;

Цепь в ориентированном графе называется путём, а цикл – контуром.




3.2 Изоморфизм графов
Говорят, что два графа G
1
(
V
1
, Е1) и G
2
(
V
2
, Е2)изоморфны (обозначается G
1~ G
2), если существует биекция h
:
V
1

®

V
2
, сохраняющая смежность:

e1 = ( u, v ) ÎE1Þe2 = ( h( u ), h( v ) ) ÎE2,

e2 = ( u, v ) ÎE2Þe1 = ( h-1( u ), h-1( v ) ) ÎE1
Изоморфизм графов есть отношение эквивалентности. Действительно, изомор физм обладает всеми необходимыми свойствами:

1.рефлексивность: G
~ G, где требуемая биекция суть тождественная функция;

2.симметричность: если G1~ G2с биекцией h, то G2~ G1с биекцией h-1;

3.транзитивность: если G1~ G2с биекцией h, и G2~ G3с биекцией g, тоG1~ G3с биекцией goh.

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

<img width=«148» height=«140» src=«ref-1_1593948424-3539.coolpic» v:shapes="_x0000_s1026">Приведём примеры изоморфных графов рис. 3.2
<img width=«144» height=«105» src=«ref-1_1593951963-3301.coolpic» v:shapes="_x0000_s1027"><img width=«156» height=«125» src=«ref-1_1593955264-4613.coolpic» v:shapes="_x0000_i1029"> 

Рис. 3.2 Диаграммы изоморфных граф
Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, р(G
) и д(G
) — инварианты графа С.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.


3.3 Тривиальные и полные графы

Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с kвершинами, обозначается Сk.

Пример

С3 — треугольник.

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф ср вершинами обозначается Кр, он имеет максимально возможное число ребер:
<img width=«138» height=«49» src=«ref-1_1593959877-552.coolpic» v:shapes="_x0000_i1030">
Полный подграф (некоторого графа) называется кликой (этого графа).
3.4 Двудольные графы
Двудольный граф (или биграф, или четный граф) — это граф G
(
V
, Е), такой что множество V
разбито на два непересекающихся множества V
1и V
2
(
V
1ÈV
2
=
V
&

V
1ÇV
2
) причем всякое ребро из Е инцидентно вершине из V
1 и вершине из V
2
(то есть соединяет вершину из V
1
с вершиной из V
2). Множества V
1 и V
2
называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V
1
и V
2
, то он называется полным двудольным графом. Если |V
1 | = mи |V
1 | = п, то полный двудольный граф обозначается Km,n




3.5 Направленные орграфы и сети
Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Направленный орграф, полученный из полного графа, называется турниром.

Название «турнир» имеет следующее происхождение. Рассмотрим спортивное соревнование для пар участников (или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат однокругового турнира в спортивном смысле.

Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d+(v) = 0), то такая вершина называется источником, если же нулю равна полу степень исхода (то есть d-(v) = 0), то вершина называется стоком. Направлен ный орграф с одним источником и одним стоком называется сетью.
3.6 Операции над графами
1.Дополнением графа G
1
(
V
1
, Е1) называется граф G
(
V
2
, Е2) рис. 3.6.1, где

<img width=«12» height=«99» src=«ref-1_1593960429-150.coolpic» v:shapes="_x0000_s1028"><img width=«98» height=«98» src=«ref-1_1593960579-296.coolpic» v:shapes="_x0000_s1029"><img width=«98» height=«98» src=«ref-1_1593960875-295.coolpic» v:shapes="_x0000_s1030"><img width=«30» height=«30» src=«ref-1_1593961170-165.coolpic» alt=«Овал: 3» v:shapes="_x0000_s1031"><img width=«30» height=«30» src=«ref-1_1593961335-165.coolpic» alt=«Овал: 4» v:shapes="_x0000_s1032"><img width=«30» height=«30» src=«ref-1_1593961500-164.coolpic» alt=«Овал: 2» v:shapes="_x0000_s1033"><img width=«30» height=«30» src=«ref-1_1593961664-162.coolpic» alt=«Овал: 1» v:shapes="_x0000_s1034">V
2
: =
V
1

&

Е2: =
Ø

Е1: =
{
e

Î

V
1

´

V
1

ê

e

Ï

Е1
}<img width=«12» height=«99» src=«ref-1_1593961826-152.coolpic» v:shapes="_x0000_s1035"><img width=«74» height=«2» src=«ref-1_1593961978-78.coolpic» v:shapes="_x0000_s1036"><img width=«2» height=«98» src=«ref-1_1593962056-79.coolpic» v:shapes="_x0000_s1037"><img width=«30» height=«30» src=«ref-1_1593962135-162.coolpic» alt=«Овал: 4» v:shapes="_x0000_s1038"><img width=«30» height=«30» src=«ref-1_1593962297-162.coolpic» alt=«Овал: 3» v:shapes="_x0000_s1039"><img width=«30» height=«30» src=«ref-1_1593962459-159.coolpic» alt=«Овал: 1» v:shapes="_x0000_s1040"><img width=«30» height=«30» src=«ref-1_1593962618-162.coolpic» alt=«Овал: 2» v:shapes="_x0000_s1041">

G1ØG
Рис 3.6.1 Дополнение


Объединением графов G
1
(
V
1
, Е1)и G
2
(
V
2
, Е2)(обозначение — G
1ÈG
2
,при условии V
1

Ç
V
1
= Æ, Е1Ç
Е2 = Æ) называется граф G(V,E), рис. 3.6.3

V

: =
V
2 ÈV
1

&

Е: = Е1
Ç
Е2
<img width=«222» height=«186» src=«ref-1_1593962780-997.coolpic» v:shapes="_x0000_s1048 _x0000_s1047 _x0000_s1046 _x0000_s1045 _x0000_s1044 _x0000_s1043 _x0000_s1042">



Рис. 3.6.3 Объединение графов
2.Соединением графов G
1
(
V
1
, Е1)и G
2
(
V
2
, Е2)(обозначение — G
1
(
V
1
, Е1)+ G
2
(
V
2
, Е2), при условии V
1
Ç

V
2 называется граф G
(
V
,
E
), где
V: = V1 Ç
V2
&
E: =
Е
1
ÈЕ
2 È{e = (v1, v2)
ê
v1Î
V1
&
v2
Î
V2}
3.Удаление вершины vиз графа G
1
(
V
1
, Е1) (обозначение — G
1
(
V
1
, Е1) –
v
, при условии v
Î
V
1) даёт граф G
2
(
V
2
, Е2), где
V2: = V1 \ {v}&
E2: = E1 \ {e = (v1, v2)
êv1 = v Ú
v2 = v}
4.Удаление ребра eиз графа G
1
(
V
1
, Е1)(обозначение — G
1
(
V
1
, Е1)– e, при условии eÎ

E
1) даёт граф G
2
(
V
2
, Е2), где
V
2
: =
V
1

&

E
2
: =
E
1
\
{
e
}
5.Добавление вершины vв граф G
1
(
V
1
, Е1)(обозначение — G
1
(
V
1
, Е1) +
v, при условии vÏV1) даёт граф G
2
(
V
2
, Е2), где


V2: = V1È{v}&
E2: = E1
6.Добавление ребра eв граф G
1
(
V
1
, Е1)(обозначение — G
1
(
V
1
, Е1) +
v, при условии e

Ï

E
1) даёт граф G
2
(
V
2
, Е2), где
V
2
: =
V
1

&

E
2
: =
E
1

È

{
e
}
7.Стягивание подграфа А графа G
1
(
V
1
, Е1)(обозначение — G
1
(
V
1
, Е1) / А, при условии А Ì

V
1) даёт граф G
2
(
V
2
, Е2), где
V2: = (V1 \ A) È{v}&

E2: = E1 \
{
e = (u,w)
ê
u
Î
A
Ú
w
Î
A
}

È

{
e = (u,v)
ê
u
Î

Г
(
А
) \
А
}



    продолжение
--PAGE_BREAK--