254785
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 6.900 руб.;
- курсы повышения квалификации от 1.500 руб.
Престижные документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ 50%

ВНИМАНИЕ: Скидка действует ТОЛЬКО сейчас!

(Лицензия на осуществление образовательной деятельности № 5201 выдана ООО "Инфоурок")

ИнфоурокИнформатикаПрезентацииМультимедийная разработка по информатике на тему "Графы. Поиск путей в графе".

Мультимедийная разработка по информатике на тему "Графы. Поиск путей в графе".

библиотека
материалов
ГРАФЫ. ПОИСК ПУТЕЙ В ГРАФЕ. Автор: Сергеенкова И.М., ГБОУ Школа № 1191, г. Мо...
Решение задачи 2. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та –...
Смешанный граф  – это граф, содержащий как ориентированные, так и неориентир...
12 Задачи на поиск путей в Графе Задача 1. На ри­сун­ке – схема дорог, свя­зы...
Задача 2. На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д...
Задача 3. На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A...
Решение задачи 3. 1. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та...
Решите самостоятельно: Ответ: 30 1). На ри­сун­ке — схема дорог, свя­зы­ва­ю...
Ответ: 36 2). На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C,...
Ответ: 11 3). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В,...
Ответ: 12 4). На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­р...
Задание на дом: На рисунке изображена схема дорог, связывающих города A, B,...
Источники информации: http://www.compress.ru/Archive/CP/2007/1/18/10.gif htt...

Описание презентации по отдельным слайдам:

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

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

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

Решение задачи 2. Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да И. NX — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей. В "И" можно при­е­хать из Д, Ж, или З, по­это­му N = NИ = NД + NЖ + N З (1) Ана­ло­гич­но: NД = NБ; NЖ = NБ + NВ + NЕ; NЗ = NЖ + NЕ. До­ба­вим еще вер­ши­ны: NБ = NА = 1; NВ = NА + NГ = 1 + 1 = 2; NЕ = NВ + NГ = 2 + 1 = 3; NГ = NА = 1. Пре­об­ра­зу­ем пер­вые вер­ши­ны с уче­том зна­че­ний вто­рых: NД = NБ = 1; NЖ = NБ + NВ + NЕ = 1 + 2 + 3 = 6; NЗ = NЖ + NЕ = 6 + 3 = 9. Под­ста­вим в фор­му­лу (1): N = NК = 1 + 6 + 9 = 16. Ответ: 16

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

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

4 слайд 12 Задачи на поиск путей в Графе Задача 1. На ри­сун­ке – схема дорог, свя­зы
Описание слайда:

12 Задачи на поиск путей в Графе Задача 1. На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M? Ответ: 12 Решение

5 слайд Задача 2. На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д
Описание слайда:

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

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

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

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

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

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

9 слайд Ответ: 36 2). На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C,
Описание слайда:

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

10 слайд Ответ: 11 3). На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В,
Описание слайда:

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

11 слайд Ответ: 12 4). На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­р
Описание слайда:

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

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

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

13 слайд Источники информации: http://www.compress.ru/Archive/CP/2007/1/18/10.gif htt
Описание слайда:

Источники информации: http://www.compress.ru/Archive/CP/2007/1/18/10.gif http://im1-tub-ru.yandex.net/i?id=a8d63dcb87271432e78d2783001d5e0b-133-144&n=21 http://masters.donntu.edu.ua/2013/fknt/bilyk/diss/index.htm#4 http://masters.donntu.edu.ua/2013/fknt/bilyk/diss/images/4.png http://inf.reshuege.ru/test?theme=203 http://inf.reshuege.ru/get_file?id=3029

14 слайд
Описание слайда:

15 слайд
Описание слайда:

Краткое описание документа:

В презентации    содержится теоретический материал по теме "Графы. Поиск путей в графе".                                                                 

Подробно рассмотрены задачи с решениями на поиск количества путей в графе. В конце представлены задачи для самоятоятельного решения учащимися.

Материал может быть использован при изучении новой темы, а также для поддготовки  учащихся 11-х классов к ЕГЭ по информатике.

Общая информация

Номер материала: 122108

Вам будут интересны эти курсы:

Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс «Фирменный стиль» (Corel Draw, Photoshop)
Курс «Оператор персонального компьютера»
Курс «3D Studio MAX»
Курс «WEB-ВЕРСТКА (HTML, CSS)»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Курс повышение квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.