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

Графы. Поиск путей в графе

Содержание

Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра.Ребро графа называется дугой, если одна из его

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

Слайд 1ГРАФЫ.
ПОИСК ПУТЕЙ В ГРАФЕ.
Автор: Сергеенкова И.М.,
ГБОУ Школа № 1191,

г. Москва

ГРАФЫ.ПОИСК ПУТЕЙ В ГРАФЕ.Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Москва

Слайд 2Граф и его элементы. Основные понятия.
Граф – это совокупность объектов со

связями между ними. 
Объекты рассматриваются как вершины, или узлы графа,
а

связи – как дуги, или ребра.
Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной.

Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф.

А

Б

В

Дуга графа

Дуга графа

ребро графа

Вершина
графа

Вершина
графа

Вершина
графа

Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или

Слайд 3Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух

его конечных вершин.

Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.

Слайд 4Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух

его конечных вершин.
Пара вершин может соединяться двумя или более ребрами

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

Слайд 5Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных

ребра. Любой из перечисленных видов графа может содержать одно или несколько

ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями. 

Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин.
Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество k ребер в пути называется длиной пути. Путь называют циклом, если в нем первая и последняя вершины совпадают.

Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать

Слайд 612
Задачи на поиск путей в Графе
Задача 1.
На ри­сун­ке – схема

дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G,

H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

Решение

B

A

K

C

E

G

F

H

L

M

12Задачи на поиск путей в ГрафеЗадача 1.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D,

Слайд 7Решение задачи 1.
Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та –

с го­ро­да М.
NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А

в город X, N — общее число путей. В "М" можно при­е­хать из C, F, L или H, по­это­му
N = NM = NC + NF + N H + N L (1)

C

F

H

L

M

Решение задачи 1.Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да М. NX — ко­ли­че­ство раз­лич­ных путей

Слайд 82. Ана­ло­гич­но:
NC = NB;
NF = NE;
NH = NF + NG;
NL = NK.
C
F
H
L
M
B
E
G
K
A
3. До­ба­вим еще вер­ши­ны:
NB =

NA = 1;
NE = NB + NA + NG = 1 + 1 + 2

= 4;
NG = NA + NK = 1 + 1 = 2;
NK = NA = 1.
2. Ана­ло­гич­но:NC = NB;NF = NE;NH = NF + NG;NL = NK.CFHLMBEGKA3. До­ба­вим еще вер­ши­ны:NB = NA = 1;NE = NB + NA + NG = 1 +

Слайд 94. Пре­об­ра­зу­ем вер­ши­ны:
NC = NB = 1;
NF = NE = 4;
NH = NF + NG = 4

+ 2 = 6;
NL = NK = 1.
5. Под­ста­вим в фор­му­лу (1):
N

= NК = 1 + 4 + 6 + 1 = 12

B

A

K

C

E

G

F

H

L

M

Ответ: 12

4. Пре­об­ра­зу­ем вер­ши­ны:NC = NB = 1;NF = NE = 4;NH = NF + NG = 4 + 2 = 6;NL = NK = 1.5. Под­ста­вим

Слайд 10Задача 2.
На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б,

В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге

можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И?

Решение

Задача 2.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И.

Слайд 11Решение задачи 2.
1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та

– с го­ро­да И. NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да

А в город X, N — общее число путей. В "И" можно при­е­хать из Д, Ж, или З, по­это­му N = NИ = NД + NЖ + N З (1)
Решение задачи 2.1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да И. NX — ко­ли­че­ство раз­лич­ных

Слайд 122. Ана­ло­гич­но:
NД = NБ; NЖ = NБ +

NВ + NЕ; NЗ = NЖ + NЕ.
3. .

До­ба­вим еще вер­ши­ны:
NБ = NА = 1;
NВ = NА + NГ = 1 + 1 = 2;
NЕ = NВ + NГ = 2 + 1 = 3;
NГ = NА = 1.
2. Ана­ло­гич­но: NД = NБ; NЖ = NБ + NВ + NЕ; NЗ =

Слайд 134. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых:
NД = NБ = 1;
NЖ =

NБ + NВ + NЕ = 1 + 2 + 3 = 6;
NЗ =

NЖ + NЕ = 6 + 3 = 9.

5. Под­ста­вим в фор­му­лу (1):
N = NК = 1 + 6 + 9 = 16. Ответ: 16

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: NД = NБ = 1; NЖ = NБ + NВ + NЕ = 1 + 2 +

Слайд 14Задача 3.
На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B,

C, D, E, F, G, H, K, L, M. По

каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

Решение

Задача 3.На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K,

Слайд 15Решение задачи 3.
1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та

— с го­ро­да M. Пусть NX — ко­ли­че­ство раз­лич­ных путей из

го­ро­да А в город X, N — общее число путей. В город M можно при­е­хать из L, G, F, H или K, по­это­му N = NM = NL + NG+NF+ NH + NK;(*)

2.Ана­ло­гич­но:
NL = NF+ NG = 5 + 5 = 10;
NG = NF = 5;
NH = NF = 5;
NK = NF + NE + NH = 5 + 1 + 5 = 11;
NF = NA + NB + NC + ND + NE = = 5.

3. До­ба­вим еще вер­ши­ны:
NB = NA = 1;
NC = NA = 1;
ND = NA = 1;
NE = NA = 1.

4. Под­ста­вим в фор­му­лу :
N = NM = 10 + 5 + 5 + 11 + 5 = 36.


Ответ: 36.

Решение задачи 3.1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та — с го­ро­да M. Пусть NX — ко­ли­че­ство

Слайд 16Решите самостоятельно:
1).
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А,

Б, В, Г, Д, Е, Ж, И, К, Л. По

каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?

Ответ: 30

B

E

Б

Д

Е

Г

Ж

К

Решите самостоятельно:1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И,

Слайд 172).
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В,

Г, Д, Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко

в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Ж?

Ответ: 11

А

Б

Е

Д

Ж

В

Г

2).На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж. По каж­дой до­ро­ге

Слайд 183).
На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C,

D, E, F, G, H, K, L, M. По каж­дой

до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

Ответ: 12

А

М

H

B

C

D

E

K

L

F

G

3).На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L,

Слайд 19Задание на дом:
На рисунке изображена схема дорог, связывающих города A,

B, C, D, E, F, G, H, K, L, M.

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города
А в город M?

B

C

D

E

F

G

H

K

L

M

А

Задание на дом:На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H,

Слайд 20Источники информации:

http://www.compress.ru/Archive/CP/2007/1/18/10.gif
http://kpolyakov.narod.ru/school/ege.htm
http://inf.reshuege.ru/test?theme=203
http://inf.reshuege.ru/get_file?id=3029





Источники информации:http://www.compress.ru/Archive/CP/2007/1/18/10.gifhttp://kpolyakov.narod.ru/school/ege.htmhttp://inf.reshuege.ru/test?theme=203http://inf.reshuege.ru/get_file?id=3029
Теги

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

Графика в Pascal Графика в Pascal 354
Введение в издательское дело Введение в издательское дело 517
Моделирование и проектирование. Разные модели одной задачи Моделирование и проектирование. Разные модели одной задачи 274
Итоговый проект Итоговый проект "Крым" 292
Редактирование и форматирование таблиц в Word Редактирование и форматирование таблиц в Word 459
Кодирование информации Кодирование информации 437
Шеткері құрылғылар Шеткері құрылғылар 511
Задачи о рыцарях и лжецах Задачи о рыцарях и лжецах 1478
Спасибо – порой хватает одного слова для выражения всех чувств Спасибо – порой хватает одного слова для выражения всех чувств 262
Логические величины, операции, выражения Логические величины, операции, выражения 525
Олимпиадные задачи Олимпиадные задачи 294
Отношения соподчинения противоречия и противоположности 6 класс Отношения соподчинения противоречия и противоположности 6 класс 300
Клавиатура Клавиатура 522
Форматирование и редактирование текстовых документов средствами MS Word 2007 Форматирование и редактирование текстовых документов средствами MS Word 2007 319
Безопасное поведение в интернете Безопасное поведение в интернете 403
Алгоритмы и исполнители (9 класс) Алгоритмы и исполнители (9 класс) 390
Алгоритмы.Виды алгоритмов, свойства алгоритмов Алгоритмы.Виды алгоритмов, свойства алгоритмов 433
Обобщение и систематизация основных понятий раздела Информационно-коммуникационные технологии 9 класс Обобщение и систематизация основных понятий раздела Информационно-коммуникационные технологии 9 класс 348
Линейный алгоритм Линейный алгоритм 437
о вреде компьютера о вреде компьютера 565

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

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

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

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

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

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

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