Что такое 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
  • Количество просмотров: 191
  • Количество скачиваний: 0
- Предыдущая Методы решения творческих задач
Следующая - БЕЗОПАСНОСТЬ НА ДОРОГЕ

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

Презентация по информатике: Правила ввода текста Презентация по информатике: Правила ввода текста 128
I have an IDEA. Международный алгоритм шифрования данных I have an IDEA. Международный алгоритм шифрования данных 146
Обнаружение атак - 6 Обнаружение атак - 6 140
Презентация по Энергосбережению Политика и Законодательство РФ. Характеристика энергетических ресурсов Презентация по Энергосбережению Политика и Законодательство РФ. Характеристика энергетических ресурсов 195
Создание курса факультативных занятий по теме среды ЛогоМиры Создание курса факультативных занятий по теме среды ЛогоМиры 150
Информатика и информационные технологии Информатика и информационные технологии 133
Презентация по робототехнике. Движение по линии Презентация по робототехнике. Движение по линии 271
Нейросети Нейросети 149
Понятие как форма мышления Понятие как форма мышления 134
Компьютерные вирусы и антивирусные программы Компьютерные вирусы и антивирусные программы 135
Изучаем Паскаль Изучаем Паскаль 96
Ввод-вывод Ввод-вывод 115
Предентация по информатике на тему Моделирование как метод познания Предентация по информатике на тему Моделирование как метод познания 136
Программирование линейных алгоритмов Программирование линейных алгоритмов 119
Электронная школа на платформе 1С Электронная школа на платформе 1С 170
Подводные камни С# Подводные камни С# 128
1С:подпись 1С:подпись 122
Лото-игра по теме Компьютер Лото-игра по теме Компьютер 122
Табличные информационные модели Табличные информационные модели 112
Youtube Youtube 174
Презентация по информатике на тему Исследование физических моделей в электронных таблицах (11 класс) Презентация по информатике на тему Исследование физических моделей в электронных таблицах (11 класс) 133
Развитие вычислительной техники и архитектура Развитие вычислительной техники и архитектура 116
Функции в языках объектно-ориентированного программирования Функции в языках объектно-ориентированного программирования 129
Lab works 1-4 Lab works 1-4 115
Архитектура набора команд Архитектура набора команд 159
Visual studio. Основные типы проектов Visual studio. Основные типы проектов 124
Мультфильм по информатике на тему Берегись автомобиля(5 класс) Мультфильм по информатике на тему Берегись автомобиля(5 класс) 166
Презентация по информатике на тему Свойства электронных таблиц Excel Презентация по информатике на тему Свойства электронных таблиц Excel 140
Устройства отображения информации Устройства отображения информации 144
Техника безопасности в компьютерном классе Техника безопасности в компьютерном классе 361