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


ГРАФЫ.ПОИСК ПУТЕЙ В ГРАФЕ.Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Москва
style.rotation
style.rotation
style.rotation Общие сведения о Графах.Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра.Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф.Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин.



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


12Задачи на поиск путей в ГрафеЗадача 1.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?Ответ:12Решение

Решение задачи 1.1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да М. NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "М" можно при­е­хать из C, F, L или H, по­это­му N = NM = NC + NF + N H + N L (1)2. Ана­ло­гич­но:NC = NB;NF = NE;NH = NF + NG;NL = NK.3. До­ба­вим еще вер­ши­ны:NB = NA = 1;NE = NB + NA + NG = 1 + 1 + 2 = 4;NG = NA + NK = 1 + 1 = 2;NK = NA = 1. 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 Ответ: 12
Задача 2.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И?Ответ:16Решение


Решение задачи 2.Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да И. NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "И" можно при­е­хать из Д, Ж, или З, по­это­му N = NИ = NД + NЖ + N З (1)Ана­ло­гич­но:NД = NБ;NЖ = NБ + NВ + NЕ;NЗ = NЖ + NЕ.До­ба­вим еще вер­ши­ны:NБ = NА = 1;NВ = NА + NГ = 1 + 1 = 2;NЕ = NВ + NГ = 2 + 1 = 3;NГ = NА = 1.Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­том зна­че­ний вто­рых:NД = NБ = 1;NЖ = NБ + NВ + NЕ = 1 + 2 + 3 = 6; NЗ = NЖ + NЕ = 6 + 3 = 9.Под­ста­вим в фор­му­лу (1): N = NК = 1 + 6 + 9 = 16. Ответ: 16
Задача 3.На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?Ответ: Решение 36.


Решение задачи 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.
Решите самостоятельно:1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И, К, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?Ответ: 30
Ответ: 362).На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M, N, Z. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город Z?
style.rotation 3).На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Ж?Ответ: 11
4).На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?Ответ: 12
Задание на дом:На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M?FLDABСEGHKM
Источники информации:http://www.compress.ru/Archive/CP/2007/1/18/10.gifhttp://im1-tub-ru.yandex.net/i?id=a8d63dcb87271432e78d2783001d5e0b-133-144&n=21http://masters.donntu.edu.ua/2013/fknt/bilyk/diss/index.htm#4http://masters.donntu.edu.ua/2013/fknt/bilyk/diss/images/4.pnghttp://inf.reshuege.ru/test?theme=203http://inf.reshuege.ru/get_file?id=3029