9 Класс. Информатика. ФГОС. Урок 8. Использование графов при решении задач

1. Задание 3 № 364

Между населёнными пунк­та­ми А, В, С, D, Е, F по­стро­е­ны дороги, протяжённость ко­то­рых при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и F. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

1) 5

2) 6

3) 7

4) 4

2. Задание 3 № 303

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и E. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

1) 13

2) 12

3) 11

4) 10

3. Задание 3 № 4908

В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

	A	B	C	D	E
A		1	4		1
B	1			3
C	4				2
D		3
E	1		2

1) 

2) 

3) 

4) 

4. Задание 3 № 942

Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны дороги, протяжённость ко­то­рых (в км) при­ве­де­на в таблице.

Определите длину крат­чай­ше­го пути между пунк­та­ми A и C. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых указана в таблице.

1) 7

2) 8

3) 9

4) 12

5. Задание 3 № 624

Учитель Иван Пет­ро­вич живёт на стан­ции Антоновка, а ра­бо­та­ет на стан­ции Дружба. Чтобы успеть с утра на уроки, он дол­жен ехать по самой ко­рот­кой дороге. Про­ана­ли­зи­руй­те таблицу и ука­жи­те длину крат­чай­ше­го пути от стан­ции Антоновка до стан­ции Дружба:

1) 6

2) 2

3) 8

4) 4

6. Задание 11 № 1062

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

7. Задание 11 № 271

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

8. Задание 11 № 572

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

9. Задание 11 № 632

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, H. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт H?

10. Задание 11 № 4798

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

Технологическая  карта урока_Информатика_9______ класс. ФГОС.

Урок_ Использование графов при решении задач.

Цели урока:

П— представление о сущности и разнообразии графических информационных моделей;

МП— владение информационным моделированием как важным методом познания;

Л— представление о сферах применения информационного моделирования.

Решаемые учебные задачи: 

1) закрепление основных понятий раздела «Модели и моделирование».

2) обобщение и систематизация представлений учащихся о графических информационных моделях;

3) рассмотрение примеров использования графов как разновидности информационных моделей.

4) применение теории графов  для решения задач;

	Этапы урока	Материал ведения урока	Деятельность учащихся	УУД на этапах урока
1	Организационный момент		Учащиеся проверяют готовность к уроку.	Личностные УУД: -  формировать навыков самоорганизации
2	Запись домашнего задания.	§ 1.3	Учащиеся записывают домашнее задание в дневники
3	Проверка домашней работы	Проверка выполнения домашнего задания	2 учащихся у доски рассказывают и объясняют как выполнили Д/З	Познавательные  УУД: - развить познавательной активности
4	Формулирование  темы и целей  урока	- Скажите, что такое граф? - Что является вершинами и ребрами графа? - Какой граф можно назвать взвешенным? - Какой граф можно назвать сематической сетью? Дерево – это граф… На прошлом уроке мы познакомились с теоретической частью графов. А сегодня решаем задачи и применяем свои знания на практике	- Граф - это схема, в которой объекты изображаются геометрическими фигурами, а связи между ними – прямыми линиями – ребрами - Граф состоит из вершин, связанных линиями ребрами - Если его вершины или ребра, характеризуются весами вершин или ребер. -Граф с циклом или граф с различными связями между вершинами. - … в котором нет циклов.	Регулятивные УУД: - уметь ставить  учебную задачу, называть цель, формулировать тему в соответствии с нормами русского языка Коммуникативные УУД: - уметь общаться со взрослыми и сверстниками
5	Объяснение темы	Запись с экрана в тетрадь	- Смотрят, слушают, записывают условия задачи, дано, найти и ход решения вместе у учителем https://inf-oge.sdamgia.ru/	Познавательные  УУД: - развитие познавательной активности
6	Закрепление, решение задач	Реши задачи с помощью графов вместе с учителем	Вариант № 5338085	Личностные УУД: - формирование навыков самостоятельной работы; -  формирование навыков самооценки
7	Самостоятельная работа по решению задач	Реши самостоятельно, используй графы, проверь себя	-решают, сравнивают ответы, выставляют оценки

Вариант № 5338085

1. Задание 3 № 364

Между населёнными пунк­та­ми А, В, С, D, Е, F по­стро­е­ны дороги, протяжённость ко­то­рых при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и F. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

1) 5

2) 6

3) 7

4) 4

Пояснение.

Найдём все ва­ри­ан­ты марш­ру­тов из A в F и вы­бе­рем самый короткий.

A-B-C-D-E-F: длина маршрута 18 км.

A-B-C-F: длина маршрута 9 км.

A-C-D-E-F: длина маршрута 15 км.

A-C-F: длина маршрута 6 км.

A-D-C-F: длина маршрута 7 км.

A-D-E-F: длина маршрута 10 км.

A-E-D-C-F: длина маршрута 8 км.

A-E-F: длина маршрута 7 км.

Кратчайший маршрут имеет длину 6 км.

Правильный ответ ука­зан под но­ме­ром 2.

Ответ: 2

2. Задание 3 № 303

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и E. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

1) 13

2) 12

3) 11

4) 10

Пояснение.

Найдём все ва­ри­ан­ты марш­ру­тов из A в E и вы­бе­рем самый короткий.

Из пунк­та A можно по­пасть в пунк­ты B, C.

Из пунк­та B можно по­пасть в пунк­ты C, E.

Из пунк­та C можно по­пасть в пункт D.

Из пунк­та D можно по­пасть в пункт E.

A—B—C—D—E: длина марш­ру­та 18 км.

A—B—E: длина марш­ру­та 12 км.

A—C—D—E: длина марш­ру­та 13 км.

А—С—В—Е: длина марш­ру­та 11 км.

Правильный ответ ука­зан под но­ме­ром 3.

Ответ: 3

3. Задание 3 № 4908

В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

	A	B	C	D	E
A		1	4		1
B	1			3
C	4				2
D		3
E	1		2

1) 

2) 

3) 

4) 

Пояснение.

Из таб­ли­цы видно, что только из пунк­та D есть всего одна дорога, которая идёт в пункт B, а из дорога из пункта A в пункт E равняется 1. Следовательно, под­хо­дит толь­ко ва­ри­ант 2.

Правильный ответ указан под номером 2.

Ответ: 2

4. Задание 3 № 942

Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны дороги, протяжённость ко­то­рых (в км) при­ве­де­на в таблице.

Определите длину крат­чай­ше­го пути между пунк­та­ми A и C. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых указана в таблице.

1) 7

2) 8

3) 9

4) 12

Пояснение.

Найдём все ва­ри­ан­ты марш­ру­тов из A в С и вы­бе­рем самый короткий.

A—B—C: длина марш­ру­та 9 км.

A—C: длина марш­ру­та 9 км.

A—D—C: длина марш­ру­та 8 км.

A—D—E—C: длина марш­ру­та 7 км.

Правильный ответ ука­зан под но­ме­ром 1.

Ответ: 1

5. Задание 3 № 624

Учитель Иван Пет­ро­вич живёт на стан­ции Антоновка, а ра­бо­та­ет на стан­ции Дружба. Чтобы успеть с утра на уроки, он дол­жен ехать по самой ко­рот­кой дороге. Про­ана­ли­зи­руй­те таблицу и ука­жи­те длину крат­чай­ше­го пути от стан­ции Антоновка до стан­ции Дружба:

1) 6

2) 2

3) 8

4) 4

Пояснение.

Найдём все ва­ри­ан­ты маршрутов из Ан­то­нов­ки в Друж­бу и вы­бе­рем самый короткий.

Из пунк­та Антоновка(А) можно по­пасть в пунк­ты Васильки(В), Ежевичная(Е).

Из пунк­та B можно по­пасть в пункт Дружба(Д).

Из пунк­та Сельская(С) можно по­пасть в пунк­ты Д, Е.

Из пунк­та Д можно по­пасть в пункт Е.

А—В—Д: длина марш­ру­та 6 км.

А—Е—Д: длина марш­ру­та 8 км.

А—Е—С—Д: длина марш­ру­та 4 км.

Правильный ответ ука­зан под но­ме­ром 4.

Ответ: 4

6. Задание 11 № 1062

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

Пояснение.

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да К. Пусть N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей.

В К можно при­е­хать из Д, В, Г или Е, по­это­му N = N_К = N_Д + N_В + N_Г + N_Е(*).

Аналогично:

N_Д = N_Б + N_В = 1 + 3 = 4;

N_В = N_Б + N_А + N_Г = 1 + 1 + 1 = 3;

N_Г = N_А = 1;

N_Е = N_Г= 1;

N_Б = N_А = 1;

N_А = 1.

Подставим в фор­му­лу (*): N = 4 + 3 + 1 + 1 = 9.

Ответ: 9.

Ответ: 9

7. Задание 11 № 271

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

Пояснение.

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да К. Пусть N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей.

В К можно при­е­хать из Е, В, Г или Ж, по­это­му N = N_К = N_Е + N_В + N_Г + N_Ж (*).

Аналогично:

N_Е = N_Б = 1;

N_В = N_А + N_Б = 1 + 1 = 2;

N_Г = N_В + N_А + N_Д = 2 + 1 + 1 = 4;

N_Ж = N_Г + N_Д = 4 + 1 = 5;

N_Б = N_А = 1;

N_Д = N_А = 1.

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

Ответ: 12

8. Задание 11 № 572

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

Пояснение.

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да H. Пусть N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да H в город X, N — общее число путей.

В H можно при­е­хать из G, E или D, по­это­му N = N_H = N_G + N_E + N_D (*).

Аналогично:

N_G = N_F = 0;

N_E = N_F + N_C + N_D = 0 + 0 + 2 = 2;

N_D = N_B + N_A = 1 + 1 = 2;

N_F = N_C = 0;

N_C = 0;

N_B = N_А + N_C = 1.

Подставим в фор­му­лу (*): N = 2 + 2 = 4.

Ответ: 4

9. Задание 11 № 632

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, H. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт H?

Пояснение.

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да H. Пусть N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да H в город X, N — общее число путей.

В H можно при­е­хать из F или G, по­это­му N = N_H = N_F + N_G (*).

Аналогично:

N_F = N_E + N_D = 2 + 2 = 4;

N_G = N_D = 2;

N_E = N_B + N_A = 1 + 1 = 2;

N_D = N_A + N_C = 1 + 1 = 2;

N_B = N_A = 1;

N_A = N_C = 1;

Подставим в фор­му­лу (*): N = 4 + 2 = 6.

Ответ: 6

10. Задание 11 № 4798

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

Пояснение.

Начнем счи­тать ко­ли­че­ство путей с конца маршрута — с го­ро­да К. Пусть N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей.

N = N_К = N_Д + N_В + N_И + N_Г + N_Е(*).

Аналогично:

N_Д = N_В = N_Б = 1;

N_Г = N_А + N_Б = 2;

N_И = N_В + N_Г = 1 + 2 = 3;

N_Е = N_Г = 2;

Подставим в фор­му­лу (*): N = 1 + 1 + 3 + 2 + 2 = 9.

Ответ: 9.

Ответ: 9