ВойтиПопробовать бесплатно

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

Графы и деревья

Подтемы: Графы. Основные понятия. Виды графов, Построение оптимального пути между вершинами графа, Количество различных путей в ориентированном ациклическом графе

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

Типы заданий

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

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

Ф.И.
Класс

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

№1 · ВИДЫ ГРАФОВ

1 ПРОПУСК · 1 БАЛЛ

1. Назови граф без направлений

Заполните пропуск в определении вида графа.

Граф, в котором рёбра не имеют направления, называется графом.

№2 · СОПОСТАВЛЕНИЕ

4 ПАРЫ · 1 БАЛЛ

2. Соотнеси понятие и определение

Соедините каждый термин с его определением.

№3 · КРАТЧАЙШИЙ ПУТЬ

1 ВОПРОС · 2 БАЛЛА

3. Выбери кратчайший маршрут

На схеме показан взвешенный граф. Числа на рёбрах — их веса. Какова длина кратчайшего пути из вершины A в вершину D?

Взвешенный граф

  • 8
  • 7
  • 6
  • 9

№4 · ОРИЕНТИРОВАННЫЕ ГРАФЫ

5 УТВЕРЖДЕНИЙ · 2 БАЛЛА

4. Проверь свойства ориентированного графа

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

  1. В ориентированном графе каждое ребро имеет направление.
  2. По направленному ребру можно двигаться только в сторону его стрелки.
  3. В ориентированном графе направление ребра не влияет на путь.
  4. Ориентированный граф может содержать цикл.
  5. Любой ориентированный граф является ациклическим.

№5 · КЛАССИФИКАЦИЯ ГРАФОВ

8 КАРТОЧЕК · 2 БАЛЛА

5. Раздели графы по наличию циклов

Распределите описания по категориям: ориентированный ациклический граф или ориентированный граф с циклом.

Слова для распределения: K → L, L → M, M → K, K → N, U → V, V → U, 1 → 2, 2 → 3, 3 → 2, X → Y, Y → Z, X → Z, Z → W, P → Q, Q → R, R → S, S → P, A → B, A → C, B → D, C → D, A → B, B → C, C → A, 1 → 2, 2 → 3, 1 → 3

Ациклический граф

Граф с циклом

№6 · ПОДСЧЁТ ПУТЕЙ

3 ПРОПУСКА · 3 БАЛЛА

6. Вычисли число путей динамически

Заполните пропуски в рассуждении для ориентированного ациклического графа. Число путей в вершину равно сумме чисел путей по всем входящим рёбрам.

В графе есть рёбра A → B, A → C, B → D, C → D, B → E, C → E, D → F, E → F. Число путей из A в D равно , из A в E равно , а из A в F равно .

№7 · ОПТИМАЛЬНЫЙ ПУТЬ

4 ПАРЫ · 3 БАЛЛА

7. Соотнеси маршрут и его длину

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

№8 · АЛГОРИТМЫ НА ГРАФАХ

4 ВАРИАНТА · 2 БАЛЛА

8. Определи подходящий алгоритм

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

  • Алгоритм Дейкстры
  • Алгоритм Евклида
  • Алгоритм двоичного поиска
  • Алгоритм сортировки слиянием

№9 · ПОДСЧЁТ ПУТЕЙ В ОАГ

5 УТВЕРЖДЕНИЙ · 3 БАЛЛА

9. Проверь рассуждение о путях

Определите истинность утверждений о количестве путей в ориентированном ациклическом графе. Число путей в вершину находят слева направо по топологическому порядку, складывая значения предшественников.

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

№1 · ОСНОВНЫЕ ПОНЯТИЯ

1 ВОПРОС · 1 БАЛЛ

1. Что называют графом

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

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

№2 · ВИДЫ ГРАФОВ

4 УТВЕРЖДЕНИЯ · 1 БАЛЛ

2. Ориентированные и неориентированные графы

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

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

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

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

№3 · ТЕРМИНЫ

5 ПАР · 1 БАЛЛ

3. Термины графов

Соедините каждый термин с его точным определением.

№4 · МАТРИЦА СМЕЖНОСТИ

4 ПРОПУСКА · 2 БАЛЛА

4. Представление графа матрицей

Заполните пропуски в строке матрицы смежности неориентированного графа. Вершина A соединена с B и D, но не соединена с C. На главной диагонали стоят нули.

Вершина ABCD
A

№5 · АЛГОРИТМЫ

4 ШАГА · 1 БАЛЛ

5. Порядок поиска кратчайшего пути

Расположите шаги алгоритма поиска кратчайших расстояний от одной вершины в правильном порядке.

  1. Задать расстояние до стартовой вершины равным нулю, а до остальных — бесконечности.
  2. Обновить расстояния до соседей, если новый маршрут короче известного.
  3. Рассмотреть ещё не обработанную вершину с наименьшим известным расстоянием.
  4. Пометить выбранную вершину как обработанную и повторять действия, пока это необходимо.

№6 · КРАТЧАЙШИЙ ПУТЬ

1 ЗАДАЧА · 3 БАЛЛА

6. Оптимальный маршрут в графе

На схеме показан взвешенный неориентированный граф. Найдите длину кратчайшего пути из вершины A в вершину D. Числа на рёбрах — их веса.

Взвешенный граф

№7 · СРАВНЕНИЕ

3 ПАРЫ · 1 БАЛЛ

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

Сравните длины маршрутов. Все числа обозначают длину пути в условных единицах.

1)A-B-CA-D-C
2)P-Q-RP-S-R
3)K-L-MK-N-M

№8 · ПОДСЧЁТ ПУТЕЙ

3 ПРОПУСКА · 2 БАЛЛА

8. Количество путей в ациклическом графе

Заполните пропуски. В ориентированном ациклическом графе из S в T есть три независимых маршрута: S–A–T, S–B–T и S–C–T. Общее количество различных путей равно, через A проходит путь, а через B и C вместе проходят пути.

В ориентированном ациклическом графе из S в T есть три независимых маршрута: S–A–T, S–B–T и S–C–T. Общее количество различных путей равно , через A проходит путь, а через B и C вместе проходят пути.

№9 · СВОЙСТВА ГРАФА

4 ВАРИАНТА · 1 БАЛЛ

9. Признак ацикличности

Выберите утверждение, которое верно описывает ориентированный ациклический граф.

  • В нём отсутствуют ориентированные циклы.
  • В нём из каждой вершины обязательно выходит ровно два ребра.
  • В нём все вершины соединены с каждой другой вершиной.
  • В нём любой путь обязательно возвращается в исходную вершину.

№10 · ГРАФЫ И АЛГОРИТМЫ

1 ЗАДАЧА · 3 БАЛЛА

10. Подсчёт маршрутов по схеме

По схеме ориентированного ациклического графа определите количество различных путей из S в T. Двигаться можно только по стрелкам.

Ориентированный ациклический граф

№11 · ПОСТРОЕНИЕ ГРАФА

1 ГРАФ · 3 БАЛЛА

11. Построй ориентированный ациклический граф

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

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

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

Похожие рабочие листы

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

Макросы в ExcelПрограммированиеИзучение типов сетевых кабелей и их характеристикСканирование и распознавание документов, содержащих графикуФормы, методы и средства, структура урокаВиды деятельности в сети Интернет. Сервисы Интернета; Геоинформационные системы и геолокационные сервисы реального времени; Социальные сети. Сетевой этикет. Проблема подлинности информацииВиды деятельности в сети Интернет, сервисы, поисковые системы, сетевой этикет, проблема подлинности информации и поиск информацииСоздание веб-сайта портфолио обучающегосяРешение задач по теме электронные таблицы (без использования компьютера)Вредоносное программное обеспечение и антивирусные программы; Правовое обеспечение информационной безопасности; Средства защиты информации в компьютерах и сетях; Социальные сети. Сетевой этикетСистема, системный подход. СистематизацияОбработка информации в электронных таблицах

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

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

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

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

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

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

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

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

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

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

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