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

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

Содержание

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 не смежна с

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

доброта и жестокость доброта и жестокость 261
Табиғи ресурстардың жіктелуі және экономикалық мәні Табиғи ресурстардың жіктелуі және экономикалық мәні 357
Презентация1 Презентация1 171
Послание Президента Российской Федерации Послание Президента Российской Федерации 255
Соединительные ткани II 1. Плотные соединительные ткани 2. Соединительные ткани Соединительные ткани II 1. Плотные соединительные ткани 2. Соединительные ткани 240
Электрический ток в различных средах Электрический ток в различных средах 171
Международное значение русского языка Международное значение русского языка 131
Государственная программа Московской области Архитектура и градостроительство Государственная программа Московской области Архитектура и градостроительство 230
Зяблик - Зяблик - 239
Рисуем поросенка Рисуем поросенка 199
ТОКСИКОЛОГИЯ ТОКСИКОЛОГИЯ 786
Влияние различных способов предпосевного замачивания семян на скорость их Влияние различных способов предпосевного замачивания семян на скорость их 178
Оптимизация с использованием встроенных функций MathCAD Оптимизация с использованием встроенных функций MathCAD 232
Розділ XII МІСЦЕВІ ПОДАТКИ І ЗБОРИ ПОДАТКОВИЙ КОДЕКС Стаття 26 7 Збір за Розділ XII МІСЦЕВІ ПОДАТКИ І ЗБОРИ ПОДАТКОВИЙ КОДЕКС Стаття 26 7 Збір за 172
Современные компьютерные технологии сбора, хранения, обработки, анализа и Современные компьютерные технологии сбора, хранения, обработки, анализа и 486
О РЕАЛИЗАЦИИ НАЦИОНАЛЬНОГО ПРОЕКТА МАЛОЕ И СРЕДНЕЕ ПРЕДПРИНИМАТЕЛЬСТВО И О РЕАЛИЗАЦИИ НАЦИОНАЛЬНОГО ПРОЕКТА МАЛОЕ И СРЕДНЕЕ ПРЕДПРИНИМАТЕЛЬСТВО И 308
Кафе Стритфуд Образование Общение Старшее поколение Романтика Кафе Стритфуд Образование Общение Старшее поколение Романтика 212
РИСУНОК ГОЛОВЫ ЧЕЛОВЕКА РИСУНОК ГОЛОВЫ ЧЕЛОВЕКА 242
Режим труда и отдыха Режим труда и отдыха 237
Методика подготовки учащихся к ЕГЭ Методика подготовки учащихся к ЕГЭ 339

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

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

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

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

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

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

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