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

Москва

как вершины, или узлы графа,
а связи – как дуги, или ребра.

Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф.

Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.

Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин.

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

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

свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

Ответ:

12

Решение

Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да
А в город И?

Ответ:

16

Решение

го­ро­да И. 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

D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да
A в город M?

Ответ: 

Решение

36.

с го­ро­да 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.