Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между ними. Объекты рассматриваются как вершины, или узлы графа, а связи – как дуги, или ребра.Ребро графа называется дугой, если одна из его вершин считается начальной, другая –
ГРАФЫ.ПОИСК ПУТЕЙ В ГРАФЕ.Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Москва Граф и его элементы. Основные понятия. Граф – это совокупность объектов со связями между Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин. Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из 12Задачи на поиск путей в ГрафеЗадача 1.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих Решение задачи 1.Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да 2. Ана­ло­гич­но:NC = NB;NF = NE;NH = NF + NG;NL = NK.CFHLMBEGKA3. До­ба­вим еще вер­ши­ны:NB = NA = 1;NE = 4. Пре­об­ра­зу­ем вер­ши­ны:NC = NB = 1;NF = NE = 4;NH = NF + NG = 4 + 2 Задача 2.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Решение задачи 2.1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с 2. Ана­ло­гич­но: NД = NБ; NЖ = NБ + NВ + NЕ; 4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: NД = NБ = 1; NЖ = NБ + NВ + Задача 3.На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, Решение задачи 3.1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та — с Решите самостоятельно:1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, 2).На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, 3).На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, Задание на дом:На рисунке изображена схема дорог, связывающих города A, B, C, Источники информации:http://www.compress.ru/Archive/CP/2007/1/18/10.gifhttp://kpolyakov.narod.ru/school/ege.htmhttp://inf.reshuege.ru/test?theme=203http://inf.reshuege.ru/get_file?id=3029
Слайды презентации

Слайд 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. До­ба­вим

2. Ана­ло­гич­но:NC = NB;NF = NE;NH = NF + NG;NL = NK.CFHLMBEGKA3. До­ба­вим еще вер­ши­ны:NB = NA =

еще вер­ши­ны:
NB = NA = 1;
NE = 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 +

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

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

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

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

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

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

Решение

Слайд 11 Решение задачи 2.
1. Нач­нем счи­тать ко­ли­че­ство путей с

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

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

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

Слайд 12 2. Ана­ло­гич­но:
NД = NБ;

2. Ана­ло­гич­но: NД = NБ; NЖ = NБ + 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.

Слайд 13 4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых:
NД =

4. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых: NД = NБ = 1; NЖ = 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

Слайд 14 Задача 3.
На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да

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

A, B, C, D, 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,

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

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

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

Ответ: 12

А

М

H

B

C

D

E

K

L

F

G

Слайд 19 Задание на дом:
На рисунке изображена схема дорог, связывающих

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

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

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

B

C

D

E

F

G

H

K

L

M

А

  • Имя файла: grafy-poisk-putey-v-grafe.pptx
  • Количество просмотров: 160
  • Количество скачиваний: 0
- Предыдущая Методы решения творческих задач
Следующая - БЕЗОПАСНОСТЬ НА ДОРОГЕ

Похожие презентации

Студенческая жизнь Студенческая жизнь 99
Циклические конструкции Циклические конструкции 124
Информатика презентация к уроку по информатике Информатика презентация к уроку по информатике 45
Информационные ресурсы, позволяющие анализировать тексты на плагиат Информационные ресурсы, позволяющие анализировать тексты на плагиат 93
Интернет и его возможности Интернет и его возможности 118
Інтегрування віртуального персонажа в відео Інтегрування віртуального персонажа в відео 97
Великие люди России Сергей Лебедев Великие люди России Сергей Лебедев 120
Презентация по информатике на тему: Информационные модели Презентация по информатике на тему: Информационные модели 133
Операционная система MD_DOS Операционная система MD_DOS 106
Оперативная память Оперативная память 97
Программирование циклов с заданным условием окончания работы Программирование циклов с заданным условием окончания работы 124
Растровое и векторное кодирование графической информации Растровое и векторное кодирование графической информации 100
Информация. Информатика. Компьютер Информация. Информатика. Компьютер 107
Технологии и методологии проектирования ИС Технологии и методологии проектирования ИС 133
Старая Русса Старая Русса 101
Функции и процедуры Функции и процедуры 94
Этикет общения в сети Интернет Этикет общения в сети Интернет 126
Урок информатики по теме: Разработка плана создания компьютерной презентации PowerPoint, определение цели, структуры, сценария Урок информатики по теме: Разработка плана создания компьютерной презентации PowerPoint, определение цели, структуры, сценария 141
MSC.Flightloads 5.1а MSC.Flightloads 5.1а 103
Основы программирования Основы программирования 99
Устройство компьютера Устройство компьютера 94
Безопасный Интернет Безопасный Интернет 96
Создание публикации в программе Microsoft Publisher Создание публикации в программе Microsoft Publisher 138
Презентация по информатике на тему Введение в графику в языке программирования Turbo Pascal Презентация по информатике на тему Введение в графику в языке программирования Turbo Pascal 109
Буклет Что такое триггеры? компьютерная программа по информатике Буклет Что такое триггеры? компьютерная программа по информатике 179
Киберпреступность и кибертерроризм Киберпреступность и кибертерроризм 200
Информация и знания Информация и знания 112
Паскаль тілінде программалау Паскаль тілінде программалау 103
Предмет и задачи информатики Предмет и задачи информатики 129
Социальные сети: за и против Социальные сети: за и против 134