Графы информатика 11 класс егэ

Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Цель: подготовка к ЕГЭ по информатике и ИКТ.

Задачи:

• дать основные понятия теории графов;
• разобрать задачи встречающиеся в ЕГЭ по
  информатике и ИКТ.

Тип мастер-класса: Комбинированный.

Метод обучения:
объяснительно-иллюстративный.

Оборудование: компьютер, проектор, Презентация1.ppt,
дидактический материал «Задачи» (Приложение1).

Время проведения: 60 минут.

Структура мастер-класса:

1. Орг. момент (2 мин).
2. Изложение нового материала (48 мин).
3. Дискуссия по результатам выполняемых заданий (10
   мин).

Ход мастер-класса

1. Оргмомент.

2. Изложение нового материала.

Графы — это отличный инструмент для наглядного
решения широкого круга задач. Этот мастер класс
наглядно демонстрирует, что владея таким
надежным инструментом, как теория графов,
возможно, создать выигрышную стратегию игры, т.е.
решить задачу ЕГЭ из части С3.

Основные понятия теории графов. (Слайд №1.)

Закрепление основных понятий теории графов.
(Слайд №2.)

Область применения графов. (Слайд №3.)

Отыскание пути в графе. (Слайд №4-5.)

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

Матрицы графов. (Слайд №7.)

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

Задачи из ЕГЭ.

Слайд №8 — A10 (базовый уровень, время — 2 мин)

Тема: «Использование информационных моделей
(таблицы, диаграммы, графики). Перебор вариантов,
выбор лучшего по какому-то признаку».

Слайд №9 — C3 (высокий уровень, время — 30 мин)

Тема: «Дерево игры. Поиск выигрышной
стратегии».

3. Дискуссия по результатам выполняемых
заданий.

Используемая литература.

1. Л. Ю. Березина Графы и их применение: Пособие для
   учителей.- Москва: Просвещение, 1979 г.

КОНСПЕКТ
УРОКА

Тема:
«Решение задач на графах при подготовке к ЕГЭ»

1.     ФИО	Камбулова Татьяна Валерьевна
2.     Место работы	Муниципальное бюджетное общеобразовательное учреждение средняя общеобразовательная школа № 4 города Новошахтинска
3.     Должность	Учитель физики и информатики
4.     Предмет	Информатика
5.     Класс	11
6.     Базовый учебник	Информатика 11 класс. Базовый уровень. Семакин, Хеннер, Шеина. (ООО «БИНОМ. Лаборатория знаний»)

7.     Цели
урока:

·        
сформировать представления о
способах решения логических задач с помощью графов.

8.     Задачи
урока:

Образовательные:

·        
систематизировать и расширить
представления учащихся о графах;

·        
научиться применять метод
графов для решения логических задач;

·        
прививать познавательный
интерес к информатике.

Развивающие:

·        
развивать познавательные
процессы (внимание, восприятие, мышление);

·        
развивать коммуникативные
умения;

·        
развивать мыслительные процессы
(анализ, синтез, классификация и другие).

Воспитательные:

·        
воспитывать умение работать в группах;

·        
формировать умение воспринимать,
анализировать информацию и делать выводы.

9.     Планируемые
учебные результаты: 

Предметные:

·        
понимать, что такое граф и его
виды. Уметь решать задачи ЕГЭ на графах.

Метапредметные:

·        
уметь формулировать цель урока,
мотивировать себя и планировать свою деятельность на уроке.

Личностные:

·        
понять значение информационного
моделирования как метода усовершенствования объектов окружающей
действительности. 

10. Тип
урока:

·        
систематизации и обобщения
знаний и умений

11.  Формы
работы учащихся:

·        
фронтальная;

·        
работа в группах;

·        
индивидуальная.

12. Материалы
к уроку:

·        
конспект урока;

·        
карточки с задачами;

·        
карточки с индивидуальными
самостоятельными работами;

·        
ключи и критерии проверки.

13.
Структура и ход урока (Таблица
1)

Таблица
1

№ п/п	Этап урока	Используемые на уроке учебные пособия, ЭОР с указанием номера в приложении №2	Деятельность учителя	Деятельность ученика	Вре-мя (в мин.)
1.	Организационный этап	—	Приветствие. Создание положительного настроя. Проверка отсутствующих.	Приветствуют учителя. Настраиваются на рабочий лад.	2
2.	Проверка домашнего задания (повторить главу: «Компьютерное информационное моделирование»)	Неориентированный граф Матрица смежности неориентированного графа Ориентированный граф Матрица смежности ориентированного графа	Учитель задает вопросы по схемам, наводящие на определения.	Вспоминают понятия: «граф», «ориентированный граф», «неориентированный граф», «матрица смежности».	3
3.	Постановка цели и задач урока. Мотивация учебной деятельности учащихся. Формулировка темы урока.	П1 П2 П3 П4 П5 П6 П1 5 7 П2 4 8 П3 5 4 9 П4 10 2 П5 7 8 9 10 П6 2	Учитель демонстрирует на доске Задание В3 ЕГЭ: На рисунке схема дорог между населенными пунктами изображена в виде графа. В таблице содержатся сведения о длинах этих дорог. Что вы можете сказать по решению данной задачи?	Ученики понимают, что для решения задачи нужно соотнести таблицу и граф. Но как? Логически размышляют и обозначают для себя цель данного урока. Ученик записывает тему на доске.	5
4.	Обобщение и систематизация знаний.	Разбор задач ЕГЭ (приложение 1)	Рассмотрение различных способов использования графа при решении различных задач:	Учащиеся работают с карточками и у доски, делают записи в тетрадях	20
5.	Актуализация знаний	(Например, задача из жизни: Встретились пятеро друзей и каждый из них пожал каждому другу руку. Сколько всего рукопожатий?)	Какие возникли затруднения при решении задач на графах? Приведите примеры задач на графах из жизни.	Учащиеся отвечают на вопросы учителя и задают учителю свои вопросы	5
6.	Закрепление изученного материала.	Приложение 2	Самостоятельная работа учащихся по карточкам.	«Слабые» учащиеся работают в группах. «Сильные» учащиеся работают индивидуально.	7
8.	Подведение итогов. Выставление оценок. Рефлексия.	Смайлики	Достигли ли вы поставленных целей? Что повторили? Изучили? Узнали? Все ли задачи были решены?	Отвечают на поставленные вопросы	3

 Приложение 1

Задание 1

На рисунке схема дорог между населенными
пунктами изображена в виде графа. В таблице содержатся сведения о длинах этих
дорог.

	П1	П2	П3	П4	П5	П6
П1			5		7
П2			4		8
П3	5	4			9
П4					10	2
П5	7	8	9	10
П6				2

Таблицу и схему дорог построили независимо
друг от друга, т. е. нумерация пунктов в таблице никак не связана с буквенными
обозначениями на графе. Определите, какова длина дороги из пункта D в пункт E.
В ответе запишите целое число, как оно указано в таблице.

Решение:

Нам не известно, каким пунктам на графе
соответствуют пункты таблицы. Но мы можем это определить.

Обратите внимание на пункт F графа. Это
единственный пункт, из которого выходит только один путь. Значит в таблице это
П6.

Из F путь ведёт в Е, значит по таблице мы
можем определить, что пункт Е — это П4.

Теперь посмотрим на пункт D графа. Это
единственный пункт, из которого ведут четыре пути. Соответственно в таблице
пункт D это П5.

Нам нужно определить расстояние между
пунктами D и E, то есть между П4 и П5. Из таблицы видно, что расстояние между
ними равно 10.

Ответ: 10

Задание 2

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

Решение

Решаем задачу «с конца».

Обозначим N
– число дорог; Ni – дорога
из i-го города в данный
город.

В город М можно попасть из городов  Ж, Л,
К:

Nм=Nж+Nл+Nк
(1)

Аналогично для каждого города между городами
А и М:

Nл=
Nж
+Nи+
Nк=3+2+3=8

Nж= Nб
+Nд=1+2=3

Nк= Nе
+Nг=2+1=3

Nд= Nб
+Nв=1+1=2

Nи= Nг
+Nб=1+1=2

Nе= Nв
+Nг=1+1=2

Nб= Nа=1 

Nв= Nа=1

Nг= Nа=1

Принимаем Nа=1 – это
некое «стартовое» значение

Считаем количество дорог снизу
вверх по стрелке

Возвращаемся к формуле (1): Nм=Nж+Nл+Nк=3+8+3=14

Ответ: 14

Задание 3.

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

Решение.

Отметим
точку А, она должна быть соединена с С и D. Отмечаем точки С и D и соеди­няем
их с точкой А дугами; над каждой дугой указываем стоимость проезда. Точка С
должна быть соединена, кроме А, с точками В и Е. Точка D является соседней
только с А. Точка В должна быть соединена, кроме С, с точкой .Е. В результате
можно получить следующую схему (рис. 1.23):

Задание 4.

Между
населенными пунктами A, B, C, D, E, F, G построены дороги. Протяженность дорог
приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги
между пунктами нет. Определите
длину кратчайшего пути между пунктами A и G (при условии, что передвигаться
можно только по построенным дорогам).

	A	B	C	D	E	F	G
A		3	6				28
B	3		2
C	6	2		7			18
D			7		2	7	12
E				2		3	5
F				7	3		1
G	28		18	12	5	1

Решение:

Строим граф и находим в нем кратчайший
путь

Посчитаем длину: 3+2+7+2+3+1=18

Ответ: 18

Приложение 2. (для
работы в группах и индивидуальной работы)

Задание 1.

На рисунке схема дорог Н-ского района
изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так
как таблицу и схему рисовали независимо друг от друга, то нумерация населенных
пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите,
какова длина дороги из пункта Д в пункт К. В ответе
запишите целое число — так, как оно указано в таблице.

Ключи:

·        
Рассмотрим граф и посчитаем количество ребер из каждой вершины:

А — > 2 ребра (Г, В)

В — > 4 ребра (А, Г, К, Д)

Г — > 4 ребра (А, В, К, Д)

Б — > 2 ребра (Г, К)

К — > 5 ребер (Б, Г, В, Д, Е)

Е — > 2 ребра (К, Д)

Д — > 3 ребра (В, К, Е)

·        
Мы выделили вершины, с уникальным числом ребер: 3 ребра
соответствует только вершине Д, а 5 ребер соответствует только
вершине К.

·        
Рассмотрим таблицу и найдем те строки или столбцы, в которых 5
значений и 3 значения: Это П2 и П4.

·        
Получаем П2 соответствует Д, а П4 соответствует К.
На пересечении находится цифра 20.

Результат: 20

Источники:

1.      Сайт Сдам ЕГЭ      https://inf—ege.sdamgia.ru

2.      ЕГЭ.
Информатика : универсальный справочник / И.А. Трофимова, О.В. Яровая.  – Москва
: Эксмо, 2017. – 240 с.

3.      Информатика
: Новый полный справочник для подготовки к ЕГЭ / О.Б. Богомолова. – Москва :
АСТ : Астрель, 2016. – 412.

Задачи на графы для подготовки к ЕГЭ. Использовался сайт Константина Полякова (kpolyakov.narod.ru).

Пример задания 1:

Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

         Аэропорт вылета          Аэропорт прилета         Время вылета         Время прилета

        СОСНОВО         КРАСНЫЙ         06:20         08:35

        КРАСНЫЙ         ОКТЯБРЬ         10:25         12:35

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        БЕРЕГ         СОСНОВО         12:15         14:25

        СОСНОВО         ОКТЯБРЬ         12:45         16:35

        КРАСНЫЙ         СОСНОВО         13:15         15:40

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

        СОСНОВО         БЕРЕГ         17:35         19:30

        БЕРЕГ         ОКТЯБРЬ         19:40         21:55

Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.

1) 15:40         2) 16:35         3)17:15         4) 17:25

Решение:

1. сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

1. посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой
2. можно лететь, через КРАСНЫЙ, но, как следует из расписания,

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        …

        КРАСНЫЙ         СОСНОВО         13:15         15:40

путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ

1. можно лететь через БЕРЕГ,

        БЕРЕГ         СОСНОВО         12:15         14:25

        …

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится

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

Решение (вариант 2, граф):

1. для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
2. из аэропорта ОКТЯБРЬ есть три рейса:

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

1. построим граф, около каждого пункта запишем время прибытия

1. проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс  «БЕРЕГ-СОСНОВО», вылетающий в 12:15
2. таким образом, правильный ответ – 4 (прямой рейс).

Еще пример задания 2:

Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.

1) 1 час        2) 1,5 часа         3)3,5 часа         4) 4 часа

Решение:

1. нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):

1. разделив числитель на знаменатель, получим время движения по каждой дороге

1. ехать из А в B можно

• напрямую, это займет 4 часа, или …
• через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
  (из В в С), всего 1 + 2,5 = 3,5 часа

1. таким образом, правильный ответ – 3.

Еще пример задания:

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда  из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.

1)	2)	3)	4)
A B C D Е A 3 1 B 4 2 C 3 4 2 D 1 Е 2 2	A B C D Е A 3 1 1 B 4 C 3 4 2 D 1 Е 1 2	A B C D Е A 3 1 4 B 4 2 C 3 4 2 D 1 Е 4 2 2	A B C D Е A 1 B 4 1 C 4 4 2 D 1 4 Е 1 2

Решение (вариант 2, с рисованием схемы):

1. для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:

1)	2)	3)	4)
A B C D Е A 3 1 B 4 2 C 3 4 2 D 1 Е 2 2	A B C D Е A 3 1 1 B 4 C 3 4 2 D 1 Е 1 2	A B C D Е A 3 1 4 B 4 2 C 3 4 2 D 1 Е 4 2 2	A B C D Е A 1 B 4 1 C 4 4 2 D 1 4 Е 1 2

              

1. теперь по схемам определяем кратчайшие маршруты для каждой таблицы:

1:   или , стоимость 7

2:   или , стоимость 7

3:  , стоимость 6

4:  , стоимость 8

1. условие «не больше 6» выполняется только для таблицы 3
2. таким образом, правильный ответ – 3.

Еще пример задания:

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

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

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 9         2) 10         3) 11         4) 12

Решение (вариант 1, использование схемы):

1. построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

1. для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
2. например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):

1. новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

1. новый маршрут из D – в E (длина пути 3):

1. новый маршрут из E – в F (длина пути 2):

1. нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
2. попробуем перечислить возможные маршруты из А в Е:

А – В – Е        длина 9

А – В – С – Е         длина 7

А – В – C – D – Е         длина 9

А –C – Е         длина 8

А –C – B – Е         длина 12

А –C – D – Е         длина 10

1. из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
2. таким образом, правильный ответ – 1.

Еще пример задания^[1]:

Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

         Аэропорт вылета          Аэропорт прилета         Время вылета         Время прилета

        ВОСТОРГ         ГОРКА         16:15         18:30

        ОЗЕРНЫЙ         ЗАРЯ         13:40         15:50

        ОЗЕРНЫЙ         ВОСТОРГ        14:10         16:20

        ГОРКА        ОЗЕРНЫЙ        17:05         19:20

        ВОСТОРГ        ОЗЕРНЫЙ         11:15         13:20

        ЗАРЯ         ОЗЕРНЫЙ         16:20         18:25

        ВОСТОРГ         ЗАРЯ        14:00         16:15

        ЗАРЯ        ГОРКА        16:05         18:15

        ГОРКА        ЗАРЯ         14:10         16:25

        ОЗЕРНЫЙ         ГОРКА         18:35         19:50

Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.

1) 16:15         2) 18:15         3)18:30         4) 19:50

Решение («обратный ход»):

1. сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30:

        ВОСТОРГ         ГОРКА         16:15         18:30

1. посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:

        ЗАРЯ        ГОРКА        16:05         18:15

        ОЗЕРНЫЙ         ГОРКА         18:35         19:50

1. это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05
2. смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:

        ОЗЕРНЫЙ         ЗАРЯ         13:40         15:50

1. дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40

        ВОСТОРГ        ОЗЕРНЫЙ         11:15         13:20

1. таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении
2. поэтому оптимальный маршрут

1. и правильный ответ – 2.

	A	B	C	D
A			1	2
B			2	3
C	1	2		5
D	2	3	5

1. В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.        

1. В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».

1)	2)	3)	4)
A B C D A 2 2 B 2 4 3 C 4 4 D 2 3 4	A B C D A 2 1 1 B 2 4 C 1 4 1 D 1 1	A B C D A 1 3 6 B 1 2 4 C 3 2 D 6 4	A B C D A 3 2 1 B 3 2 C 2 2 4 D 1 4

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

	A	B	C	D	E	F
A			2	4	3	7
B					5	3
C	2					2
D	4
E	3	5
F	7	3	2

Определите длину кратчайшего пути между пунктами B и D (при условии, что передвигаться можно только по построенным дорогам).

1) 8         2) 9         3) 10         4) 11

---

[1] Крылов С.С., Ушаков Д.М.  ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь.  — М.: Экзамен, 2010.

Использование теории графов для решения заданий ЕГЭ

1. Между населенными пунктами A,B,C,D,E,Fпостроены дороги, протяженность которых приведена в таблице(отсутствие числа означает, что прямой дороги нет). Определить длину кратчайшего пути между пунктами E и F. (Передвигаться можно только по построенным дорогам). A B C D E F A 2 4 B 2 1 7 C 4 1 3 4 D 3 3 E 7 4 3 2 F 2 Решение: В этом задании исходные данные представлены в виде таблицы, которую можно рассматривать как матрицу неориентированного взвешенного графа. Вершинами данного графа являются населенные пункты A,B,C,D,E,F. Элементы данной матрицы показывают, какие населенные пункты связаны дорогами и какова их длина. Для более наглядного представления изобразим данные таблицы в виде графа. Для этого в произвольном порядке изображаем вершины, затем соединяем их ребрами и указываем вес каждого ребра. Нам надо указать длину кратчайшего пути из пункта А в пункт F.  Нарисуем этот путь с конца.

Сначала изобразим конечный пункт F. В этот пункт можно попасть только из пункта Е. Соединяем пункты Е и F  дугой и указываем вес этой дуги. Он равен двум, то есть расстоянию между пунктами  Е и F. Соответственно по графу можно увидеть, что в пункт Е можно попасть  из пунктов B, C и D. В пункт В можно попасть из А. В пункт С – из В и А. В  пункт D – из С. В пункт В попадаем из А. В пункт С – из В и А. И в пункт В из А.

Данную схему можно рассматривать как ориентированный взвешенный граф, который наглядно показывает, что есть 5 путей из пункта А в пункт F. Подсчитываем длину каждого пути 
1 путь: 2+7+2=11;
2 путь: 2+1+4+2=9;
3 путь: 4+4+2=10;
4 путь2+1+3+3+2=11;
5 путь: 4+3+3+2=12. 
Так как нам надо определить длину кратчайшего пути, то выбираем второй путь, длина которого равна 9. Данный ответ находится под цифрой 1. Поэтому в ответе надо поставить крестик в клеточке, соответствующей первому ответу.

2. У исполнителя Утроитель две команды, которым присвоены номера
1. Прибавь 1;
2. Умножь на 3.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.
Решение:
Для решения данного задания используем метод от обратного, то есть будем преобразовывать число 22 в 1. Соответственно команды исполнителя заменим командами антагонистами, то есть команду «Прибавь 1» заменим командой «Вычти 1», а «Умножь на 3» заменим командой «Раздели на 3». Ход выполнения команд можно изобразить в виде  дерева, каждая вершина которого имеет две ветки, соответствующие командам 1 и 2. Корнем этого дерева является число 22. Это дерево будет иметь 5 ярусов, так как программа должна содержать не более 5 команд. Но здесь нужно учесть один момент. Если число  делится на 3, то вершина будет иметь 2 потомка, а если нет, то одного (то есть делить на 3 мы не можем, а можем только вычитать 1). Получаем следующее дерево.

  

 Инвертируем теперь команды и преобразуем число 1 в 22.
    1+1*3+1*3+1=22.
   Учитывая номера команд, записываем программу решения данной задачи в виде  последовательности соответствующих команд. Ответ: 12121

 
Решение: (1 способ)
Условие данного задания представлено в виде ориентированного графа, вершинами которого являются названия городов, а дороги, соединяющие эти города, являются дугами графа. Для того, чтобы решить данную задачу, построим еще один ориентированный граф, но с  учетом того, по каким дорогам можно будет попасть в пункт Л.

 По графу легко подсчитать количество дорог, ведущих из города А в город Л.
 

3.У Исполнителя Кузнечик 2 команды:
1. Прибавь 3;
2. Вычти 2.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд. 
Решение:
Оформим решение данной задачи в виде дерева, вершинами которого будут являться числа, соответствующие промежуточным значениям. Данное дерево будет иметь корень, равный 1 и 5 ярусов, так как у нас должно быть ровно 5 команд.

 

 4. У исполнителя Устроитель две команды, которым присвоены номера:
1. Прибавь 1;
2. Умножь на 3.
Программа для Устроителя – это последовательность команд. 
Сколько есть программ, которые преобразуют 1 в число 29?

  При решении данной задачи следует учитывать, что если число больше 9, то умножать на 3 мы не можем, так как получится число, большее 29, следовательно, вершины с числами большими 9 будут иметь только одну ветвь, соответствующую команде +1.

  
 

   

5.Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по 2 камня в каждую из всех трех куч. Выигрывает тот, после чьего хода в какой-нибудь куче становится больше или равно 15 камней или во всех трех кучах суммарно становится больше либо равно 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок? 
Решение:    В разумной партии каждый игрок должен стараться следовать общему правилу – всегда оставлять противнику проигрышную позицию. В ходе решения задач можно заметить, что в одной партии в Камешки только один из игроков может следовать этому правилу – тот, кто первым может занять выигрышную позицию (имеет выигрышную стратегию). Если он будет ей следовать, а, значит, делать только разумные ходы и оставлять противнику только проигрышные позиции, то выиграет при любой игре противника. Если начальная позиция выигрышная, то выигрышную стратегию имеет Первый, если проигрышная – Второй.  
Изобразим решение данной задачи в виде графа.

Ответ:  при правильной стратегии игры выигрывает первый игрок. При этом первый его ход должен быть 2, 3, 4                 4, 5, 6.

Литература: 
ФИПИ (открытый банк данных)
Материалы демонстрационных вариантов ЕГЭ по информатике  2016, 2015 года
Материалы диагностической работы 2015 года.

Информатика, 11 класс. Урок № 7.

Тема — Моделирование на графах

Цели и задачи урока:

1. Получить знания о графах, их видах, свойствах.
2. Получить навыки преобразования весовой матрицы (табличной формы представления информации) в граф.
3. Сформировать навык построения путей в графе и поиска кратчайшего пути.

На уроке вы узнаете:

1. Что такое граф, как наглядное средство представления и состава системы.
2. Как применять графы при решении различных задач.
3. Как представлять информацию на графах.
4. Как находить кратчайший путь по графу.

Давайте рассмотрим, пожалуй, самую известную головоломку, придуманную аж в XVIII веке, и захватившую умы человечества на многие годы. Называется она задача о семи Кёнигсбергских мостах. В Кёнигсберге начиная с XIV было построено 7 мостов: Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост, Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый город. Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни по одному дважды?»

Десятилетиям жители города пытались решить эту задачу как практически (гуляя по городу), так и теоретически.

И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.

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

Графы делятся на:

— Неориентированные и ориентированные (когда движение по ребру возможно только в одну сторону).

— Взвешенными (когда у вершины или у ребра есть вес, отличающий его от другого) и невзвешенный.

— И другие более сложные графы (мультиграф, псевдограф, изоморфный граф и другие).

Эйлер установил, что:

1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно или не может существовать граф, который имел бы нечётное число нечётных вершин.

2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

ВЫВОД: пройти только один раз по каждому мосту невозможно.

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

Очень часто для решения задач требуется найти кратчайший путь между двумя вершинами.

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

Существует огромное количество алгоритмов, находящих кратчайший путь и один из них — это алгоритм Дейсктры.

Алгоритм заключается в том, что надо пошагово перебрать все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Для примера возьмем следующий взвешенный ориентированный граф и попытаемся найти кратчайший путь от вершины A до F. Пошагово переберём все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Первым шагом: присвоим вершине А метку равную 0, потому как эта вершина — начало. Остальным вершинам присвоим метки равные бесконечности.

Вторым шагом: выберем не вычеркнутую вершину, вес которой является минимальным («источник»). Сейчас это вершина А. Вычисляем сумму веса вершины источника и веса ребра

То есть для:

B=0+2=2

C=0+5

D=0+7

F=0+10.

Если она окажется меньше веса вершины приемника, то изменим вес этой вершины.

Третьим шагом: вычеркнем вершину-«источник».

Повторим шаги 1, 2, 3 до тех пор, пока не будут вычеркнуты все вершины.

Еще один способом нахождения кратчайшего пути может служить «метод динамического программирования».

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

Составим таблицу, в которой каждая ячейка будет соответствовать определенной ячейке. Числа в ячейках будут равны минимальному числу пошлины, которое можно получить, пройдя от начала (A) до соответствующей клетки.