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

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

Содержание

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

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

Слайд 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

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

Создание кроссвордов в MS WORD Создание кроссвордов в MS WORD 411
блок-схемы алгоритмов блок-схемы алгоритмов 347
Векторная графика Векторная графика 287
Моделирование движения в среде Логомиры Моделирование движения в среде Логомиры 406
Символдық және жолдық шамалармен жұмыс істеуге арналған функциялар Символдық және жолдық шамалармен жұмыс істеуге арналған функциялар 270
Турнир смекалистых 7-9 класс Турнир смекалистых 7-9 класс 374
Принтеры Принтеры 352
Учебные курсы Microsoft для средней школы Учебные курсы Microsoft для средней школы 375
Классификация вредоносных продуктов с точки зрения AVT Group Классификация вредоносных продуктов с точки зрения AVT Group 360
Виды компьютеров и их особенности Виды компьютеров и их особенности 675
Базы данных Базы данных 367
Язык PL/SQL Язык PL/SQL 469
Решение заданий на позиционные системы счисления Решение заданий на позиционные системы счисления 364
ИКТ для обучения детей со специальными потребностями ИКТ для обучения детей со специальными потребностями 331
Сложение двоичных чисел. Сложение двоичных чисел. 327
Презентация по информатике Презентация по информатике "Подготовка к ЕГЭ и ГИА.. Решение задач" 318
Информационные процессы в информационных объектах Информационные процессы в информационных объектах 314
История развития вычислительных средств История развития вычислительных средств 317
Файловая система 8 класс Файловая система 8 класс 266
Microsoft Office Access Microsoft Office Access 397

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

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

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

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

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

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

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