Презентация, доклад по информатике Графы. Поиск путей в графе

Содержание

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

Слайд 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
Скачать презентацию

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

Презентация по курсу Информационные технологии Реляционные базы данных Презентация по курсу Информационные технологии Реляционные базы данных 186
Презентация по информатике на тему Средства и технологии обмена информации с помощью компьютерных сетей Презентация по информатике на тему Средства и технологии обмена информации с помощью компьютерных сетей 284
Презентация к классному часу Компьютер - друг или враг? Презентация к классному часу Компьютер - друг или враг? 185
Пернемен саяхат (5 класс) Пернемен саяхат (5 класс) 213
Алгоритмы и программирование Алгоритмы и программирование 173
Презентация по казахскому языку на тему Ақпарат, компьютері.Windows операциялық жүйесі Презентация по казахскому языку на тему Ақпарат, компьютері.Windows операциялық жүйесі 287

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

Это сайт презентаций, где можно хранить и обмениваться своими презентациями, докладами, проектами, шаблонами в формате PowerPoint с другими пользователями. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами.

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

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

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

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