Алгоритмы на графах Графы. Основные определения

определения
Представление графов
Минимальное остовное дерево. Задача связности графа.

Построение и анализ алгоритмов

множество вершин (конечное)
E – множество ребер (конечное)
G = (V, E)

См. дисциплину «Дискретная математика»

V × V = V2 или E ⊆ { (u,

Графы. Основные определения

Сокращенная запись: u − v ≡ {u, v} ∈ E и u → v ≡ (u, v) ∈ E
Цепь (маршрут): последовательность v0, v1, v2, … , vk-1, vk, такая, что k ≥ 0, (∀ i ∈ 0..k − 1: vi − vi+1). Здесь k − длина пути, а v0 и vk − начало и конец пути. При v0 = vk – цикл. Для орграфа: цепь → путь (то же, но vi → vi+1), а цикл → контур.

(неориентированного графа)
E ⊆ { {u, v}: (u, v∈ V)

инцидентных ей ребер (дуг).
Для орграфа:
dout(v) - полустепень исхода, din(v) -

Графы. Основные определения

G1 = (V1, E1) и G2 = (V2, E2) изоморфны

и бинарные отношения.
Бинарное отношение: R ⊆ A × B. Вместо

Графы. Основные определения

a3}
a2
a3

F (a1) ={b, c, d}
F (a2) ={b}
c
d

Отличие соответствия от функции

(V, Γ) − граф, где Γ − соответствие Γ: V

Графы. Основные определения

Γ(v1) = {v3, v4, v5}, Γ(v2) = {v3}, Γ(v3) = {v1, v2, v4, v5}, Γ(v4) = {v1, v3}, Γ(v5) = {v1, v3}

Γ(v1) = {v4}, Γ(v2) = ∅, Γ (v3) = {v1, v2, v4, v5}, Γ (v4) = {v3}, Γ (v5) = {v1}

= {v′, …, v′′} – полный прообраз элемента v.
Например, для

Графы. Основные определения

Другое определение графа (орграфа)

Γ−1(v1) = {v3, v4, v5}, Γ−1(v2) = {v3}, Γ−1(v3) = {v1, v2, v4, v5}, Γ−1(v4) = {v1, v3}, Γ−1 (v5) = {v1, v3}
и Γ−1 (vi) = Γ(vi) для ∀vi ∈ V.

Γ−1 (v1) = {v3, v5}, Γ−1(v2) = {v3}, Γ−1 (v3) = {v4}, Γ−1(v4) = {v1, v3}, Γ−1 (v5) = {v3}

− упорядоченный граф, где L – множество упорядоченных списков вершин

Графы. Основные определения

(V1, L 1) и G2 = (V2, L 2) изоморфны

Графы. Основные определения

изоморфны (эквивалентны). Как упорядоченные графы они не эквивалентны.
L(v1) = (v3,

L(w1) = (w2, w3),
L(w2) = (w3, w1),
L(w3) = (v2, v1).

строк (по вершинам)
m столбцов (по ребрам)
Для орграфа: столбец для дуги

2. Представления графов

e1 = (v1, v4)
e2 = (v3, v1)
e3 = (v3, v2)
e4 = (v3, v4)
e5 = (v3, v5)
e6= (v4, v3)
e7= (v5, v1)

e1

e2

e3

e4

e6

e5

e7

графов
e1 = (v1, v3)
e2 = (v1, v4)
e3 = (v1, v5)
e4

Память размера n×m. Ответы на вопросы: «∃ дуга (x, y)?» или «к каким вершинам идут ребра из x?» - требуют m шагов.

e1

e2

e3

e4

e5

e6

u − v или u → v, иначе A[u, v]

Матрица смежности A(n × n)

Представления графов

A(n × n)
Память размера n×n. Ответ на вопрос: «∃ ребро

Многие алгоритмы, использующие матрицу смежности требуют в худшем случае Ω (n2) шагов.

(adjacent – смежный, соседний) Adj[v] – список вершин, смежных с v.









1
2
3
4
5
6
7
8
9
Adj[1]:

Adj[2]: 1, 3, 5

Adj[3]: 2, 5, 6

Adj[4]: 1, 7

Adj[5]: 1, 2, 3, 9, 8, 7

Adj[6]: 3, 9

Adj[7]: 4, 5, 8

Adj[8]: 7, 5, 9

Adj[9]: 5, 6, 8

Пример графа (n = 9; m = 14)

Пояснить круговые стрелки!

массив списков (adjacent – смежный, соседний)
Adj[v] – список вершин, смежных

Представления графов

do S(u) ≡
begin L := Adj [v].head; {L: L1_List **}
GoBOL(L);

Представления графов

представления графа (орграфа) в другое.
Виды представления:
матрица инциденций;
матрица смежности;
списки

Представления графов

{a,c}, {a,e}, {b,c}, {b,d}, {b,e}, {c,d}, {d,e} }
b
a
a
a
c
d
e
b
c
e
b
b
c
d
e
d

содержащий циклов.
Граф связный, если каждая пара различных вершин графа связана

3. Минимальное остовное дерево

…

(Седжвик).
Задан граф.
Пусть номера вершин графа есть 1, 2, 3, …,

В зависимости от требуемой формы ответа существуют разные виды этой задачи:
Ответ - да/нет
Указать путь из i в j
Найти все пути из i в j
Найти кратчайший путь

последовательность ребер графа:
i1 – j1, i2 – j2, i3 –

= 14)
Adj[1]: 2, 4, 5
Adj[2]: 1, 3, 5
Adj[3]: 2, 5,

Adj[4]: 1, 7

Adj[5]: 1, 2, 3, 9, 8, 7

Adj[6]: 3, 9

Adj[7]: 4, 5, 8

Adj[8]: 7, 5, 9

Ребра:
{1, 2}
{1, 4}
{1, 5}
{2, 3}
{2, 5}
{3, 5}
{3, 6}
{4, 7}
{5, 7}
{5, 8}
{5, 9}
{6, 9}
{7, 8}
{8, 9}

Adj[9]: 5, 6, 8

сформирован остовный лес (выделены подмножества вершин – деревья остовного леса

Операции НАЙТИ (Wi такое, что p∈Wi) и ОБЪЕДИНИТЬ (Wi и Wj )

{1} {2} {3} {4} {5} {6} {7} {8}

предъявления ребер:

{1,2,4} {3,6} {5,7,8,9}

объединение
for (i = 1; i

= 0; i < N; i++) w[i] = i; //

17.03.2014

Алгоритмы на графах Начало

Реализация: быстрый поиск – медленное объединение

9
7 8
8 9
2 5
2 3
1

17.03.2014

Алгоритмы на графах Начало

Вход:

1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9

Выход:

Реализация: быстрый поиск – медленное объединение

См. далее

Пример

9
7 8
8 9
2 5
2 3
1

17.03.2014

Алгоритмы на графах Начало

Вход:

1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9

Выход:

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

Представление в виде дерева

графах Начало
int i, j, p, q, w[N];

int i, j, p, q, w[N];
for (i = 0; i < N; i++) w[i] = i;
while (fin >> p >> q){
for (i = p; i != w[i]; i = w[i]) ; // i == w[i]
for (j = q; j != w[j]; j = w[j]) ; // j == w[j]
if (i == j) continue;
w[i] = j;
cout << "+ребро: " << p << " " << q << endl;
}

быстрый поиск – быстрое объединение
1
2
4
3
6
8
9
7
5
8
9
7
5
6
3
(3,8)

9
7 8
8 9
2 5
2 3
1

17.03.2014

Алгоритмы на графах Начало

Вход:

1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9

Выход:

Представление в виде дерева

9
7 8
8 9
2 5
2 3
1

17.03.2014

Алгоритмы на графах Начало

Вход:

1 2
1 4
3 6
5 8
5 7
5 9
7 8
8 9
2 5
2 3
1 5
3 5
4 7
6 9

Выход:

Представление в виде дерева

Матрица весов W[v, u].
Пусть T = (V, F) –

Минимальное остовное дерево

МОД : TM = Arg min ( W(T) )

лекции

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ