ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

1. Основные понятия теории графов

ДУГА {A,B}

Ориентированный Граф G(V,E)

A

B

D

C

ВЕРШИНА D

ДУГА {B,A}

ЦИКЛ (Петля)

МНОЖЕСТВО ВЕРШИН

МНОЖЕСТВО ДУГ

Неориентированный Граф G(V,E)

A

B

D

C

ВЕРШИНА А

(B,A)=(A,B)

МНОЖЕСТВО ВЕРШИН

МНОЖЕСТВО РЕБЕР

РЕБРО (A,B)

E

ИЗОЛИРОВАННАЯ ВЕРШИНА

ВИСЯЧАЯ ВЕРШИНА

Ориентированные и неориентированные графы

Ориентированный граф G(V,E),
V = {1,2,3,4,5,6} E = {{1,2},

Основные понятия

Вершина графа
Смежная
Изолированная
Висячая
Степень вершины исходящая, входящая

Ребро (дуга) графа
Инцидентность
вес
Дуга-цикл

Совокупность

Пути и циклы в графе

A

B

D

C

E

G

H

I

J

F

Изоморфизм графов

ИЗОМОРФНЫЕ ГРАФЫ

НЕИЗОМОРФНЫЕ ГРАФЫ

Подграфы

A

B

D

C

E

A

B

D

C

E

G(V,E)

G’(V’,E’)

G’ подграф G, если E’⊆E и V’ ⊆ V

G’ суграф G,

Клики в графе

A

B

D

C

E

F

G

Двудольные графы

A

B

D

C

E

F

G

Планарные и плоские графы

A

B

D

C

E

F

A

B

D

C

E

F

Планарный граф

Плоский граф

2. Алгоритмы на графах

Минимальные покрывающие деревья

Имеется граф G(V,E)
Каждому ребру (u,v) задан неотрицательный вес w(u,v)
Задача:

Отличия теории и практики

A

B

C

D

A

B

C

D

A

B

C

D

А

B

C

кратчайшее дерево: А - без дополнительных вершин В

Алгоритм Краскала шаг 0

Суммарная длина деревьев = 0

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 1

Суммарная длина деревьев = 1

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 2

Суммарная длина деревьев = 3

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 3

Суммарная длина деревьев = 5

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 4

Суммарная длина деревьев = 9

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 5

Суммарная длина деревьев = 13

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 6

Суммарная длина деревьев = 20

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 7

Суммарная длина деревьев = 28

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 8

Суммарная длина деревьев = 37

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Краскала шаг 9

Суммарная длина деревьев = 37

A

H

G

I

B

F

C

D

E

4

8

2

1

2

4

7

9

Алгоритм Прима

Начало алгоритма: с произвольной вершины
К текущему дереву присоединяется смежная вершина

Алгоритм Прима шаг 0

Суммарная длина дерева = 0

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 1

Суммарная длина дерева = 0

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 2

Суммарная длина дерева = 4

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 3

Суммарная длина дерева = 12

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 4

Суммарная длина дерева = 14

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 5

Суммарная длина дерева = 18

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 6

Суммарная длина дерева = 20

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 7

Суммарная длина дерева = 21

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 8

Суммарная длина дерева = 28

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 9

Суммарная длина дерева = 37

A

H

G

I

B

F

C

D

E

4

8

11

2

7

1

6

2

4

7

8

9

14

10

Алгоритм Прима шаг 10

Суммарная длина дерева = 37

A

H

G

I

B

F

C

D

E

4

2

1

2

4

7

8

9

КРАТЧАЙШИЕ ПУТИ В ГРАФЕ

Алгоритм Дейкстры (Дийкстры)
Алгоритм Ли
Алгоритм А* (А-звездочка)

Алгоритм Дейкстры

0

∞

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

∞

∞

∞

3

2

Ищем путь из S ? V

Алгоритм Дейкстры

0

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

∞

∞

3

2

∞

∞

Алгоритм Дейкстры

0

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

∞

∞

3

2

5

10

Алгоритм Дейкстры

0

10

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

∞

5

∞

3

2

Алгоритм Дейкстры

0

8

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

5

3

2

14

7

Алгоритм Дейкстры

0

8

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

5

3

2

14

7

Алгоритм Дейкстры

0

8

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

5

3

2

13

7

Алгоритм Дейкстры

0

8

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

5

3

2

13

7

Алгоритм Дейкстры

0

8

V

10

5

7

2

9

1

8

4

6

U

S

X

Y

5

3

2

9

7

Алгоритм А* (Алгоритм оптимального поиска)

S

V’

V

F

9

11

g(v)

h(v)

F(v)=g(v)+h(v)

Оценка длины пути

Точная длина

Минимальная оценка

Манхеттеновская длина

Алгоритм А*

g(v) – стоимость пути от финиша до вершины v.
h(v) –