15 задание егэ. Моделирование графы

Моделирование Графы

МАОУ СШ № 8 г. Бор Нижегородской обл.

Кустова Юлия Евгеньевна

№

Проверяемые элементы содержания

15

Умение представлять и считывать данные в разных типах информационных

Коды проверяемых элементов содержания (по кодификатору)

моделей (схемы, карты, таблицы, графики и формулы)

Коды проверяемых требований к уровню подготовки (по кодификатору)

1.3.1

Уровень сложности задания

1.2.1

Макс. балл за выполнение задания

П

Примерное время выполнения задания (мин.)

1

3

Научись использовать графы для решения задач

Для получения ответа используем данный граф и переберем варианты.

Решение задания

1

1

Б

Е

1+4+2+5=12

1

12

2

1+1=2

К

В

А

2+1+1=4

4

Г

Ж

Д

5

4+1=5

1

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

Для начала определяем количество путей из города А в город Ж

1

1

4

10

1

2

1

1

Теперь будем определять пути из пункта Ж в пункт М, зная что попасть из пункта А в пункт Ж можно 10 способами.

Попасть в пункт И через пункт Ж можно только 10 способами

10

10

20

10

10

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

Для начала определяем количество путей из города А в город В

1

4

1

2

1

Теперь будем исключать (зачеркивать) пути, которые мы не будем использовать.

1

4

12

4

36

1

8

12

2

12

1

Ответ: 36

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

1

5

4

1

16

16

16

2

16

7

1

Ответ: 16

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

4

4

27

27

3

1

2

17

1

6

Ответ: 27

• 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

Спасибо за внимание!