Разделы презентаций

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

Содержание

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

Слайды и текст этой презентации

Слайд 1ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ
Желобаев А.Л. МИЭТ 2009.

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВЖелобаев А.Л. МИЭТ 2009.

Слайд 21. Основные понятия теории графов

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

Слайд 3ДУГА {A,B}

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

A

B

D

C
ВЕРШИНА D
ДУГА {B,A}
ЦИКЛ (Петля)
МНОЖЕСТВО ВЕРШИН
МНОЖЕСТВО ДУГ

ДУГА {A,B}Ориентированный Граф G(V,E)ABDCВЕРШИНА DДУГА {B,A}ЦИКЛ (Петля)МНОЖЕСТВО ВЕРШИНМНОЖЕСТВО ДУГ

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

A

B

D

C
ВЕРШИНА А
(B,A)=(A,B)
МНОЖЕСТВО ВЕРШИН
МНОЖЕСТВО РЕБЕР
РЕБРО (A,B)

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


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

Неориентированный Граф G(V,E)ABDCВЕРШИНА А (B,A)=(A,B)МНОЖЕСТВО ВЕРШИНМНОЖЕСТВО РЕБЕРРЕБРО (A,B)EИЗОЛИРОВАННАЯ ВЕРШИНА ВИСЯЧАЯ ВЕРШИНА

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

= {{1,2}, {2,2}, {2,4}, {2,5}, {4,1}, {4,5}, {5,4}, {6,3}}

Неориентированный

граф G(V,E),
V = {1,2,3,4,5,6} E = {(1,2), (1,5), (2,5), (3,6)}

Подграф графа (а), порожденный множеством вершин {1,2,3,6}

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

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

(дуга) графа
Инцидентность
вес
Дуга-цикл
Совокупность дуг
Путь длины k
Цикл
Ациклический граф
Связный граф
Сильно связный

граф
Полный граф
Пустой граф
Лес
Дерево в графе
Основные понятия Вершина графаСмежнаяИзолированнаяВисячаяСтепень вершины исходящая, входящая Ребро (дуга) графаИнцидентностьвесДуга-цикл Совокупность дугПуть длины kЦиклАциклический

Слайд 7Пути и циклы в графе

A

B

D

C

E

G

H

I

J

F

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

Слайд 8Изоморфизм графов

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

Изоморфизм графовИЗОМОРФНЫЕ ГРАФЫ НЕИЗОМОРФНЫЕ ГРАФЫ

Слайд 9Подграфы

A

B

D

C

E

A

B

D

C

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

суграф G, если E’⊆E и V’ = V

ПодграфыABDCEABDCEG(V,E)G’(V’,E’)G’ подграф G, если E’⊆E и V’ ⊆ VG’ суграф G, если E’⊆E и V’ =

Слайд 10Клики в графе

A

B

D

C

E

F

G



Клики в графеABDCEFG

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

A

B

D

C

E

F

G

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

Слайд 12Планарные и плоские графы

A

B

D

C

E

F

A

B

D

C

E

F

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

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

Слайд 132. Алгоритмы на графах

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

Слайд 14Минимальные покрывающие деревья
Имеется граф G(V,E)
Каждому ребру (u,v) задан неотрицательный вес

w(u,v)
Задача: найти подмножество Т ⊆Е, связывающее все вершины, для которого

минимален суммарный вес
w(T)=∑w(u,v)
(u,v)εT
Минимальные покрывающие деревьяИмеется граф G(V,E)Каждому ребру (u,v) задан неотрицательный вес w(u,v)Задача: найти подмножество Т ⊆Е, связывающее все

Слайд 15Отличия теории и практики

A

B

C

D

A

B

C

D


A

B

C

D


А
B
C
кратчайшее дерево: А - без

дополнительных вершин В - с дополнительной вершиной С – дерево Штейнера

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

Слайд 16Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 0 Суммарная длина деревьев = 0AHGIBFCDE48112716247891410

Слайд 17Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 1 Суммарная длина деревьев = 1AHGIBFCDE48112716247891410

Слайд 18Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 2 Суммарная длина деревьев = 3AHGIBFCDE48112716247891410

Слайд 19Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 3 Суммарная длина деревьев = 5AHGIBFCDE48112716247891410

Слайд 20Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 4 Суммарная длина деревьев = 9AHGIBFCDE48112716247891410

Слайд 21Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 5 Суммарная длина деревьев = 13AHGIBFCDE48112716247891410

Слайд 22Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 6 Суммарная длина деревьев = 20AHGIBFCDE48112716247891410

Слайд 23Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 7Суммарная длина деревьев = 28AHGIBFCDE48112716247891410

Слайд 24Алгоритм Краскала шаг 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

Алгоритм Краскала шаг 8Суммарная длина деревьев = 37AHGIBFCDE48112716247891410

Слайд 25Алгоритм Краскала шаг 9
Суммарная длина деревьев = 37

A

H

G

I

B

F

C

D

E
4
8
2
1
2
4
7
9

Алгоритм Краскала шаг 9Суммарная длина деревьев = 37AHGIBFCDE48212479

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

вершина с кратчайшим ребром.
Окончание алгоритма: либо все вершины подключены,

либо невозможно подключить ни одно ребро.

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

Слайд 27Алгоритм Прима шаг 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

Алгоритм Прима шаг 0 Суммарная длина дерева = 0AHGIBFCDE48112716247891410

Слайд 28Алгоритм Прима шаг 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

Алгоритм Прима шаг 1 Суммарная длина дерева = 0AHGIBFCDE48112716247891410

Слайд 29Алгоритм Прима шаг 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

Алгоритм Прима шаг 2 Суммарная длина дерева = 4AHGIBFCDE48112716247891410

Слайд 30Алгоритм Прима шаг 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

Алгоритм Прима шаг 3 Суммарная длина дерева = 12AHGIBFCDE48112716247891410

Слайд 31Алгоритм Прима шаг 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

Алгоритм Прима шаг 4 Суммарная длина дерева = 14AHGIBFCDE48112716247891410

Слайд 32Алгоритм Прима шаг 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

Алгоритм Прима шаг 5 Суммарная длина дерева = 18AHGIBFCDE48112716247891410

Слайд 33Алгоритм Прима шаг 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

Алгоритм Прима шаг 6 Суммарная длина дерева = 20AHGIBFCDE48112716247891410

Слайд 34Алгоритм Прима шаг 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

Алгоритм Прима шаг 7 Суммарная длина дерева = 21AHGIBFCDE48112716247891410

Слайд 35Алгоритм Прима шаг 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

Алгоритм Прима шаг 8 Суммарная длина дерева = 28AHGIBFCDE48112716247891410

Слайд 36Алгоритм Прима шаг 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

Алгоритм Прима шаг 9 Суммарная длина дерева = 37AHGIBFCDE48112716247891410

Слайд 37Алгоритм Прима шаг 10
Суммарная длина дерева = 37

A

H

G

I

B

F

C

D

E
4
2
1
2
4
7
8
9

Алгоритм Прима шаг 10Суммарная длина дерева = 37AHGIBFCDE42124789

Слайд 38КРАТЧАЙШИЕ ПУТИ В ГРАФЕ
Алгоритм Дейкстры (Дийкстры)
Алгоритм Ли
Алгоритм А* (А-звездочка)

КРАТЧАЙШИЕ ПУТИ В ГРАФЕАлгоритм Дейкстры (Дийкстры)Алгоритм ЛиАлгоритм А* (А-звездочка)

Слайд 39

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


0


∞

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞
∞


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

Алгоритм Дейкстры0∞V1057291846USXY∞∞∞32Ищем путь из S ? V

Слайд 40

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


0



V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞


3
2

∞
∞

Алгоритм Дейкстры0V1057291846USXY∞∞32∞∞

Слайд 41

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


0



V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞


3
2
5
10

Алгоритм Дейкстры0V1057291846USXY∞∞32510

Слайд 42

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


0


10

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
5
∞


3
2

Алгоритм Дейкстры010V1057291846USXY∞5∞32

Слайд 43

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


0


8

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5


3
2
14
7

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

Слайд 44

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


0


8

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5


3
2
14
7

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

Слайд 45

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


0


8

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5


3
2
13
7

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

Слайд 46

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


0


8

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5


3
2
13
7

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

Слайд 47

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


0


8

V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5


3
2
9
7

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

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

S






V’

V

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

Алгоритм А* (Алгоритм оптимального поиска)SV’VF911g(v)h(v)F(v)=g(v)+h(v)

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

Точная длина
Минимальная оценка
Манхеттеновская длина

Оценка длины путиТочная длинаМинимальная оценкаМанхеттеновская длина

Слайд 50Алгоритм А*
g(v) – стоимость пути от финиша до вершины v.
h(v)

– нижняя оценка стоимости пути от вершины v до старта.
f(v)=g(v)+h(v)

– нижняя оценка стоимости пути от старта к финишу через вершину v.
Алгоритм А*g(v) – стоимость пути от финиша до вершины v.h(v) – нижняя оценка стоимости пути от вершины

Слайд 51Среди вершин, смежных с конечной найти вершину V, имеющую наименьшую

оценку f(v).
Если вершина V не смежна с начальной, то среди

вершин, достижимых из V найти вершину V’ с наименьшим значением f(v).
Продолжать, пока не будет достигнута начальная вершина.

Алгоритм А*

Среди вершин, смежных с конечной найти вершину V, имеющую наименьшую оценку f(v).Если вершина V не смежна с

Похожие презентации

Тема урока: Тема урока: 162
Элементы теории вероятностей Элементы теории вероятностей 235
БИОХИМИЯ ГЕМОГЛОБИНА, ЭРИТРОЦИТ. Для существования любого многоклеточного БИОХИМИЯ ГЕМОГЛОБИНА, ЭРИТРОЦИТ. Для существования любого многоклеточного 299
Семейное право Семейное право 254
Успенская средняя школа Успенская средняя школа 214
ПРАВИЛА И ВОЗМОЖНОСТИ ФОРМИРОВАНИЯ И ОБОСНОВАНИЯ ТАРИФОВ НА ЛЕЧЕНИЕ ДИАЛИЗНЫХ ПРАВИЛА И ВОЗМОЖНОСТИ ФОРМИРОВАНИЯ И ОБОСНОВАНИЯ ТАРИФОВ НА ЛЕЧЕНИЕ ДИАЛИЗНЫХ 371
Алена Лось.ppt Алена Лось.ppt 313
Федеральное государственное автономное образовательное учреждение высшего Федеральное государственное автономное образовательное учреждение высшего 181
Нюансы определения фактических ошибок Зыкова Л.В. Зыкова Г.Ю Нюансы определения фактических ошибок Зыкова Л.В. Зыкова Г.Ю 200
Старшая группа Золотая рыбка Старшая группа Золотая рыбка 305
Стравинский И.Ф Стравинский И.Ф 341
Федеральное государственное автономное образовательное учреждение высшего Федеральное государственное автономное образовательное учреждение высшего 293
Анализ государственной программы РАЗВИТИЕ ЗДРАВООХРАНЕНИЯ Анализ государственной программы РАЗВИТИЕ ЗДРАВООХРАНЕНИЯ 357
Щелочи Щелочи 488
значение фразеологизмов (2) значение фразеологизмов (2) 271
Общественное мнение как специфическое проявление общественного сознания. Общественное мнение как специфическое проявление общественного сознания. 570
Омск, 2010 г. Битва за Москву Выполнил студент 1 курса Михалев Омск, 2010 г. Битва за Москву Выполнил студент 1 курса Михалев 221
Lekciya_11.ppt Lekciya_11.ppt 288
Номенклатура показателей качества программной продукции Номенклатура показателей качества программной продукции 248
Процессы, обусловленные деятельностью подземных вод: - суффозия, - плывуны Процессы, обусловленные деятельностью подземных вод: - суффозия, - плывуны 451

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика