X
Код презентации скопируйте его
Графы. Поиск путей в графе
Скачать эту презентацию
Презентация на тему Графы. Поиск путей в графе
Скачать эту презентациюCлайд 1
Решение задачи 1. Нач нем счи тать ко ли че ство путей с конца марш ру та – с го ро да М. NX — ко ли че ство раз лич ных путей из го ро да А в город X, N — общее число путей. В "М" можно при е хать из C, F, L или H, по это му N = NM = NC + NF + N H + N L (1) C F H L M
Cлайд 2
Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра. Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной. Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф. А Б В Дуга графа Дуга графа ребро графа Вершина графа Вершина графа Вершина графа
Cлайд 3
Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин. 1 2 5 4 3 6
Cлайд 4
Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными. 1 2 3 5 4
Cлайд 5
Смешанный граф – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать одно или несколько ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями. Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин. Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество k ребер в пути называется длиной пути. Путь называют циклом, если в нем первая и последняя вершины совпадают.
Cлайд 6
12 Задачи на поиск путей в Графе Задача 1. На ри сун ке – схема дорог, свя зы ва ю щих го ро да A, B, C, D, E, F, G, H, K, L, M. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да A в город M? Решение B A K C E G F H L M
Cлайд 7
2. Ана ло гич но: 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.
Cлайд 8
4. Пре об ра зу ем вер ши ны: 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
Cлайд 9
Задача 2. На ри сун ке – схема дорог, свя зы ва ю щих го ро да А, Б, В, Г, Д, Е, Ж, З, И. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да А в город И? Решение A И Б Д В Ж З Е Г
Cлайд 10
2. Ана ло гич но: 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. Д Ж З И Б В Е Г А
Cлайд 11
4. Пре об ра зу ем пер вые вер ши ны с уче то зна че ний вто рых: 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 A И Б Д В Ж З Е Г
Cлайд 12
Задача 3. На ри сун ке изоб ра же на схема дорог, свя зы ва ю щих го ро да A, B, C, D, E, F, G, H, K, L, M. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да A в город M? Решение B C D E F L G H K M A
Cлайд 13
Решите самостоятельно: 1). На ри сун ке — схема дорог, свя зы ва ю щих го ро да А, Б, В, Г, Д, Е, Ж, И, К, Л. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да А в город Л? Ответ: 30 B E Б Д Е Г Ж К Л A
Cлайд 14
2). На ри сун ке — схема дорог, свя зы ва ю щих го ро да А, Б, В, Г, Д, Е, Ж. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да А в город Ж? Ответ: 11 А Б Е Д Ж В Г
Cлайд 15
3). На ри сун ке изоб ра же на схема до ро г, свя зы ва ю щих го ро да A, B, C, D, E, F, G, H, K, L, M. По каж дой до ро ге можно дви гать ся толь ко в одном на прав ле нии, ука зан ном стрел кой. Сколь ко су ще ству ет раз лич ных путей из го ро да A в город M? Ответ: 12 А М H B C D E K L F G
Cлайд 16
Задание на дом: На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M? B C D E F G H K L M А
Cлайд 17
Источники информации: 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
Cлайд 18
Cлайд 19
Cлайд 20
