Рабочий лист на тему:

Графы

Информатика9 класс20 заданий
Множественный выборКраткий ответЗаполни пропускиСравни числаИстина / ЛожьСоединениеПоследовательностьНайти лишнееРеши задачуРеши примеры

Типы заданий

Множественный выборКраткий ответЗаполни пропускиСравни числаИстина / ЛожьСоединениеПоследовательностьНайти лишнееРеши задачуРеши примеры
Графы

9 класс · дифференцированный

Ф.И.
Класс


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

№1 · Направление

1 вопрос · 1 балл

1. Чтение направленного ребра

Выберите верное утверждение о записи A → B в ориентированном графе.

  • Из A можно перейти в B, а обратный переход по этому ребру не предполагается.
  • Из B можно перейти в A, а из A в B перейти нельзя.
  • Из A в B можно перейти только после возврата в A по другому ребру.
  • Стрелка означает, что вершины A и B не соединены.

№2 · Длина пути

1 путь · 1 балл

2. Сложение весов рёбер

Найдите длину пути A → B → C. Вес ребра A → B равен 4, а вес ребра B → C равен 7.

№3 · Матрица

3 пропуска · 1 балл

3. Обозначения весовой матрицы

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

В клетке матрицы записывают вес ребра из вершины в вершину . Если такого ребра нет, записывают .

№4 · Длина пути

2 пути · 2 балла

4. Сравнение длин маршрутов

Вычислите длины двух направленных путей и сравните их. Путь P: A → B → D имеет веса 6 и 5. Путь Q: A → C → D имеет веса 4 и 9.

1)длина пути Pдлина пути Q

№5 · Проверка алгоритма

4 утверждения · 2 балла

5. Свойства графа и пути

Определите истинность каждого утверждения, опираясь только на определения ориентированного графа, веса ребра и длины пути.

  1. Длина пути равна сумме весов входящих в него рёбер.
  2. Если существует ребро A → B, то в графе обязательно существует ребро B → A.
  3. В весовой матрице строка обычно соответствует вершине, из которой выходит ребро.
  4. В ациклическом графе обязательно есть путь между любыми двумя вершинами.

№6 · Подсчёт путей

4 пары · 2 балла

6. Связь вершины с числом путей

Соедините обозначение с его смыслом при подсчёте количества путей в направленном ациклическом графе.

№7 · Порядок действий

5 шагов · 3 балла

7. Алгоритм подсчёта маршрутов

Восстановите порядок действий для подсчёта количества путей из S в T в направленном ациклическом графе.

  1. Положить N(S) = 1.
  2. Рассматривать вершины в порядке от начальной к конечной, не возвращаясь по циклам.
  3. Для каждой следующей вершины сложить значения числа путей по всем входящим рёбрам.
  4. Записать ответ как значение N(T).
  5. Если у вершины нет входящего пути из S, принять её значение равным 0.

№8 · Пути в графе

4 варианта · 4 балла

8. Поиск лишнего маршрута

В ориентированном графе заданы рёбра S → A, S → B, A → C, B → C, C → T. Найдите запись, которая не является направленным путём из S в T.

  1. S → A → C → T
  2. S → B → C → T
  3. S → A → B → C → T
  4. S → B → C → T

№9 · Количество путей

3 вершины · 5 баллов

9. Подсчёт маршрутов в ациклическом графе

В направленном ациклическом графе заданы рёбра S → A, S → B, A → C, B → C, A → T, C → T. Сколько различных направленных путей ведёт из S в T? Используйте значения N(V): для начальной вершины положите N(S) = 1.

№10 · Сопоставление

6 пар · 5 баллов

10. Расчёты по весовой матрице и направленному графу

Сопоставь каждый граф или фрагмент весовой матрицы с результатом вычисления. Для путей учитывай направление рёбер; если указано «кратчайший путь», выбери его минимальную длину.

№1 · Длина пути

3 выражения · 1 балл

1. Сложи веса рёбер маршрута

Вычисли длину каждого пути как сумму весов его рёбер.

1)4+7
2)3+5
3)6+2+4

+10 заданий в этом листе

Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.

№2 · Матрица

2 пропуска · 1 балл

2. Заполни элементы весовой матрицы

Заполни пропуски в записи весовой матрицы: укажи вес дуги из строки в столбец.

В графе дуги имеют веса: A→B — 5, B→C — 3. В весовой матрице элемент M(A,B) = , а элемент M(B,C) = .

№3 · Матрица

1 задача · 1 балл

3. Прочитай весовую матрицу

Дана весовая матрица ориентированного графа. Найди вес дуги из вершины A в вершину C.

 A B C
A 0 4 7
B 0 0 2
C 0 0 0

№4 · Длина пути

3 выражения · 2 балла

4. Сравни длины маршрутов

Вычисли длину каждого маршрута, складывая веса его рёбер.

1)5+4+3
2)7+2+6
3)3+8+1+2

№5 · Матрица

3 пропуска · 2 балла

5. Восстанови веса дуг по матрице

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

A B C D
A 0 6 0 9
B 0 0 4 0
C 0 0 0 5
D 0 0 0 0
Вес дуги A→B равен
, вес дуги B→C равен , а вес дуги C→D равен .

№6 · Длина пути

1 задача · 2 балла

6. Найди кратчайший путь в ациклическом графе

В ориентированном графе есть дуги: A→B с весом 4, A→C с весом 2, B→D с весом 3, C→D с весом 6. Найди длину кратчайшего пути из A в D и запиши маршрут.

№7 · Количество путей

3 выражения · 2 балла

7. Посчитай число путей по правилу сложения

Вычисли количество путей из вершины A в вершину D, если пути проходят через независимые промежуточные вершины. Используй сложение количества вариантов.

1)2+3
2)1+4+2
3)3+2+1+2

№8 · Количество путей

3 пропуска · 3 балла

8. Заполни рекуррентные значения

Заполни пропуски. Количество путей в вершину равно сумме количеств путей из её непосредственных предшественников. В вершину A ведёт 1 путь, в B — 2 пути.

Вершина C получает пути из A и B, поэтому число путей в C равно 1 + 2 = . Вершина D получает пути из B и C, поэтому число путей в D равно 2 + = . Если из D есть единственная дуга в E, то число путей в E равно .

№9 · Количество путей

1 задача · 4 балла

9. Подсчитай все пути в направленном ациклическом графе

В направленном ациклическом графе заданы дуги: A→B, A→C, B→C, B→D, C→D, C→E, D→E. Сколько различных путей существует из A в E? Перечисли их или используй последовательный подсчёт количества путей в вершинах.

№10 · Длина и пути

4 выражения · 4 балла

10. Сопоставь длину кратчайшего маршрута и число маршрутов

Для каждого набора маршрутов вычисли длину кратчайшего маршрута и количество маршрутов. В ответе укажи пару «кратчайшая длина; количество маршрутов».

1)min(4+3,2+6); 2
2)min(5+1+4,3+2+6,7+3); 3
3)min(2+5,4+1+3,3+3); 3
4)min(6+2+1,3+4+2,5+5,2+2+6); 4

Создайте уникальный лист по своей теме

  • Любая тема, любой уровень
  • 20+ типов заданий
  • 100% уникальный контент
  • Со страницей ответов
  • Защита от списывания
  • Готово за 1 минуту

Другие темы по информатике для 9 класса

Чем удобны рабочие листы Нейрум

  • По действующей программеТемы и задания совпадают со школьной программой 1–11 классов. Открыли — дали классу, без правок.
  • Готово к печати, с ответамиPDF в формате A4 и ключ ответов на отдельной странице. Скачали, распечатали, раздали — без правок в Word.
  • Свой лист за минутуНе нашли нужный? ИИ-конструктор соберёт лист по вашей теме, классу и типам заданий.

Вопросы и ответы

Как скачать рабочий лист «Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе»?

Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.

Сколько заданий в листе и какие они?

В листе 20 заданий: множественный выбор, краткий ответ, заполни пропуски, сравни числа, истина / Ложь, соединение, последовательность, найти лишнее, реши задачу, реши примеры.

Соответствует ли лист ФГОС?

Да, задания ориентированы на школьную программу по информатике для 9 класса по ФГОС.

Можно ли изменить задания под свой класс?

Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.