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

Содержание

Слайд 2

Граф и его элементы. Основные понятия.

Граф – это совокупность объектов со связями между

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

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

А

Б

В

Дуга графа

Дуга графа

ребро графа

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

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

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

Слайд 3

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

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

Слайд 4

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

Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух
вершин.
Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными.

Слайд 5

Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из

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

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

Слайд 6

12

Задачи на поиск путей в Графе

Задача 1.
На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих

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

Слайд 7

Решение задачи 1.

Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да

Решение задачи 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с
М.
NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "М" можно при­е­хать из C, F, L или H, по­это­му
N = NM = NC + NF + N H + N L (1)

C

F

H

L

M

Слайд 8

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 =

2. Ана­ло­гич­но: NC = NB; NF = NE; NH = NF +
NB + NA + NG = 1 + 1 + 2 = 4;
NG = NA + NK = 1 + 1 = 2;
NK = NA = 1.

Слайд 9

4. Пре­об­ра­зу­ем вер­ши­ны:
NC = NB = 1;
NF = NE = 4;
NH = NF + NG = 4 + 2

4. Пре­об­ра­зу­ем вер­ши­ны: NC = NB = 1; NF = NE =
= 6;
NL = NK = 1.

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

B

A

K

C

E

G

F

H

L

M

Ответ: 12

Слайд 10

Задача 2.

На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г,

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

Решение

Слайд 11

Решение задачи 2.

1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с

Решение задачи 2. 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та –
го­ро­да И. NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "И" можно при­е­хать из Д, Ж, или З, по­это­му N = NИ = NД + NЖ + N З (1)

Слайд 12

2. Ана­ло­гич­но:
NД = NБ; NЖ = NБ + NВ + NЕ; NЗ = NЖ + NЕ.

3. .

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

Слайд 13

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых:
NД = NБ = 1;
NЖ = NБ + NВ +

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: NД = NБ =
NЕ = 1 + 2 + 3 = 6;
NЗ = NЖ + NЕ = 6 + 3 = 9.

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

Слайд 14

Задача 3.

На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D,

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

Решение

Слайд 15

Решение задачи 3.

1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та — с

Решение задачи 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.

Слайд 16

Решите самостоятельно:

1).
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В,

Решите самостоятельно: 1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б,
Г, Д, Е, Ж, И, К, Л. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Л?

Ответ: 30

B

E

Б

Д

Е

Г

Ж

К

Слайд 17

2).
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д,

2). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г,
Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой.
Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город Ж?

Ответ: 11

А

Б

Е

Д

Ж

В

Г

Слайд 18

3).
На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E,

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

Ответ: 12

А

М

H

B

C

D

E

K

L

F

G

Слайд 19

Задание на дом:
На рисунке изображена схема дорог, связывающих города A, B, C,

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

B

C

D

E

F

G

H

K

L

M

А

Имя файла: Презентация-на-тему-Графы.-Поиск-путей-в-графе-.pptx
Количество просмотров: 343
Количество скачиваний: 0