Разделы презентаций

Графы. Поиск путей в графе 11 класс

Содержание

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

Слайды и текст этой презентации

Слайд 1ГРАФЫ.
ПОИСК ПУТЕЙ В ГРАФЕ.
Автор: Сергеенкова И.М.,
ГБОУ Школа № 1191,

г. Москва

ГРАФЫ.ПОИСК ПУТЕЙ В ГРАФЕ.Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Москва

Слайд 2Граф и его элементы. Основные понятия.
Граф – это совокупность объектов со

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

связи – как дуги, или ребра.
Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной.

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

А

Б

В

Дуга графа

Дуга графа

ребро графа

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

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

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

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

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

его конечных вершин.

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

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

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

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

Слайд 5Смешанный граф  – это граф, содержащий как ориентированные, так и неориентированных

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

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

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

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

Слайд 612
Задачи на поиск путей в Графе
Задача 1.
На ри­сун­ке – схема

дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G,

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

Решение

B

A

K

C

E

G

F

H

L

M

12Задачи на поиск путей в ГрафеЗадача 1.На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D,

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

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

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

C

F

H

L

M

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

Слайд 82. Ана­ло­гич­но:
NC = NB;
NF = NE;
NH = NF + NG;
NL = NK.
C
F
H
L
M
B
E
G
K
A
3. До­ба­вим еще вер­ши­ны:
NB =

NA = 1;
NE = NB + NA + NG = 1 + 1 + 2

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

Слайд 94. Пре­об­ра­зу­ем вер­ши­ны:
NC = NB = 1;
NF = NE = 4;
NH = NF + 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

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

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

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

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

Решение

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

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

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

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

Слайд 122. Ана­ло­гич­но:
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.
2. Ана­ло­гич­но: NД = NБ; NЖ = NБ + NВ + NЕ; NЗ =

Слайд 134. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­то зна­че­ний вто­рых:
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

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

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

C, D, E, F, G, H, K, L, M. По

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

Решение

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

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

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

Слайд 16Решите самостоятельно:
1).
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А,

Б, В, Г, Д, Е, Ж, И, К, Л. По

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

Ответ: 30

B

E

Б

Д

Е

Г

Ж

К

Решите самостоятельно:1). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, И,

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

Г, Д, Е, Ж. По каж­дой до­ро­ге можно дви­гать­ся толь­ко

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

Ответ: 11

А

Б

Е

Д

Ж

В

Г

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

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

D, E, F, G, H, K, L, M. По каж­дой

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

Ответ: 12

А

М

H

B

C

D

E

K

L

F

G

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

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

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

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

B

C

D

E

F

G

H

K

L

M

А

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

Слайд 20Источники информации:

http://www.compress.ru/Archive/CP/2007/1/18/10.gif
http://kpolyakov.narod.ru/school/ege.htm
http://inf.reshuege.ru/test?theme=203
http://inf.reshuege.ru/get_file?id=3029





Источники информации: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

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

Информационная картина мира 10 класс Информационная картина мира 10 класс 275
Развитие вычислительной техники 2 класс Развитие вычислительной техники 2 класс 224
Алгоритм. Свойства алгоритма. Алгоритм. Свойства алгоритма. 399
Кроссворд Системы, элементы системы Кроссворд Системы, элементы системы 288
Итоговый тест по информатике 11 класс Итоговый тест по информатике 11 класс 293
Презентация по теме: Презентация по теме: "Информационные процессы начальные сведения" 264
Обработка графической информации Обработка графической информации 260
Графические операторы языка Бейсик Графические операторы языка Бейсик 386
Графические возможности языка Visual Basic Графические возможности языка Visual Basic 302
Диаграммы Диаграммы 548
"Построение диаграмм и графиков" 9 класс 314
Уровни изоляции транзакций Уровни изоляции транзакций 298
Microsoft Office Microsoft Office 317
Информатика для начинающих Информатика для начинающих 370
Вероятностный подход к измерению информации. Формула Шеннона Вероятностный подход к измерению информации. Формула Шеннона 506
Платформа IT bridge Платформа IT bridge 461
Технология обработки текстовой информации Технология обработки текстовой информации 337
Трехмерное моделирование 11 класс Трехмерное моделирование 11 класс 337
долговременная память долговременная память 431
Подготовка учащихся к ОГЭ по информатике Подготовка учащихся к ОГЭ по информатике 300

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

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

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