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

Методическая разработка "Графы. Поиск путей в графе".

Содержание

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

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

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

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

Разработка на Yii Разработка на Yii 425
Повторение по теме Алгоритм 3 класс Повторение по теме Алгоритм 3 класс 346
Иерархические и сетевые базы данных 11 класс Иерархические и сетевые базы данных 11 класс 357
Программа формирования УУД и ИКТ. Программа формирования культуры ЗОЖ Программа формирования УУД и ИКТ. Программа формирования культуры ЗОЖ 479
Информатика в начальной школе 3 класс Информатика в начальной школе 3 класс 290
Ақпарат, оның мазмұны, түрлері мен қасиеттері Ақпарат, оның мазмұны, түрлері мен қасиеттері 316
Алгоритм Алгоритм 326
Алфавитный подход к измерению информации 8 класс Алфавитный подход к измерению информации 8 класс 346
Эксцентриковый механизм и его сборка Эксцентриковый механизм и его сборка 1102
Анимация Анимация 364
Компьютер ??рыл?ыларыны? міндеттері мен м?мкіндіктері Компьютер ??рыл?ыларыны? міндеттері мен м?мкіндіктері 373
Как влияет компьютер на здоровье школьника? Как влияет компьютер на здоровье школьника? 379
Текстовые редакторы (8 класс) Текстовые редакторы (8 класс) 371
Алгоритм и его свойства. Виды алгоритмов Алгоритм и его свойства. Виды алгоритмов 404
Графические информационные объекты Графические информационные объекты 344
Современные технологии. Вред и польза 7 класс Современные технологии. Вред и польза 7 класс 542
Анализ информации представленной в виде схем Анализ информации представленной в виде схем 413
Системное администрирование Системное администрирование 373
Вёрстка и дизайн газетной статьи Вёрстка и дизайн газетной статьи 449
Представление о Power Point Представление о Power Point 264

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

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

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

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

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

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

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