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

объектов со связями между ними. 
Объекты рассматриваются как вершины, или

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

А

Б

В

Дуга графа

Дуга графа

ребро графа

Вершина
графа

Вершина
графа

Вершина
графа

порядок двух его конечных вершин.

порядок двух его конечных вершин.
Пара вершин может соединяться двумя

и неориентированных ребра. Любой из перечисленных видов графа может содержать

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

– схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D,

Решение

B

A

K

C

E

G

F

H

L

M

марш­ру­та – с го­ро­да М.
NX — ко­ли­че­ство раз­лич­ных путей

C

F

H

L

M

еще вер­ши­ны:
NB = NA = 1;
NE = NB + NA + NG = 1 +

NG = 4 + 2 = 6;
NL = NK = 1.
5. Под­ста­вим

B

A

K

C

E

G

F

H

L

M

Ответ: 12

А, Б, В, Г, Д, Е, Ж, З, И.

Решение

конца марш­ру­та – с го­ро­да И. NX — ко­ли­че­ство раз­лич­ных

NЖ = NБ + NВ + NЕ; NЗ =

3. . До­ба­вим еще вер­ши­ны:
NБ = NА = 1;
NВ = NА + NГ = 1 + 1 = 2;
NЕ = NВ + NГ = 2 + 1 = 3;
NГ = NА = 1.

NБ = 1;
NЖ = NБ + NВ + NЕ = 1 + 2 +

5. Под­ста­вим в фор­му­лу (1):
N = NК = 1 + 6 + 9 = 16. Ответ: 16

A, B, C, D, E, F, G, H, K,

Решение

конца марш­ру­та — с го­ро­да M. Пусть NX — ко­ли­че­ство

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.

го­ро­да А, Б, В, Г, Д, Е, Ж, И,

Ответ: 30

B

E

Б

Д

Е

Г

Ж

К

Б, В, Г, Д, Е, Ж. По каж­дой до­ро­ге

Ответ: 11

А

Б

Е

Д

Ж

В

Г

B, C, D, E, F, G, H, K, L,

Ответ: 12

А

М

H

B

C

D

E

K

L

F

G

города A, B, C, D, E, F, G, H,

B

C

D

E

F

G

H

K

L

M

А