Заполни пропускиНайти лишнееРеши примерыКраткий ответМножественный выбор
Типы заданий
Заполни пропускиНайти лишнееРеши примерыКраткий ответМножественный выбор
Графы и деревья
9 класс · дифференцированный
Ф.И. Класс
Разберёмся, как графы и деревья помогают описывать связи и находить решения. Выполним задания от простых определений до многошагового поиска пути.
№1 · Пропуски
3 пропуска · 1 балл
1. Основные элементы графа
Заполните пропуски в определениях основных элементов графа.
Граф состоит из вершин и . Вершины графа обозначают, например, цифрами, а соединяющие их линии называют . Число рёбер, выходящих из вершины, называют её .
№2 · Лишнее
4 элемента · 1 балл
2. Признаки дерева
Найдите лишнее утверждение. Три утверждения описывают свойства дерева, одно относится к произвольному графу.
Между любыми двумя вершинами существует единственный путь.
В каждой вершине графа сходятся ровно три ребра.
В графе нет циклов.
Если удалить любое ребро, связность графа нарушится.
№3 · Примеры
4 выражения · 2 балла
3. Степени вершин
Для каждого описания вычислите степень указанной вершины. Запишите только число.
1)Степень вершины H, если H соединена с J, L, M и N
2)Степень вершины R, если R соединена с S, T и U
3)Степень вершины V, если V соединена с W и X
4)Степень вершины Y, если Y соединена только с Z
№4 · Краткий ответ
1 задача · 3 балла
4. Кратчайший путь в графе
В неориентированном графе рёбра имеют единичную длину: P соединена с Q и R; Q соединена с S; R соединена с T; S соединена с U; T соединена с U. Какова длина кратчайшего пути из P в U? Запишите число рёбер в этом пути.
№5 · Множественный выбор
1 задача · 5 баллов
5. Обход дерева и восстановление структуры
Дано дерево каталогов. Корень — каталог M. В нём находятся каталоги N и P. В каталоге N находятся файлы n1, n2 и n3. В каталоге P находится каталог Q, в котором находятся файлы q1 и q2. Выберите все верные утверждения.
У дерева 8 рёбер.
Вершина P является листом.
Между M и q2 существует путь длины 3.
У дерева 9 вершин.
Вершина M имеет степень 2.
№1 · Пропуски
3 пропуска · 1 балл
1. Основные элементы графа
Заполните пропуски в определениях основных элементов графа.
Граф состоит из вершин и . Вершины графа обозначают, например, буквами, а соединяющие их линии называют . Число рёбер, выходящих из вершины, называют её .
+5 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№2 · Лишнее
4 элемента · 1 балл
2. Признаки дерева
Найдите лишнее утверждение. Три утверждения описывают свойства дерева, одно относится к произвольному графу.
В каждой вершине графа сходятся ровно два ребра.
Между любыми двумя вершинами существует путь.
В графе нет циклов.
Если удалить любое ребро, связность графа нарушится.
№3 · Примеры
4 выражения · 2 балла
3. Степени вершин
Для каждого графа вычислите степень указанной вершины. Запишите только число.
1)Степень вершины A, если A соединена с B, C и D
2)Степень вершины K, если K соединена с M и N
3)Степень вершины P, если P соединена с Q, R, S и T
4)Степень вершины X, если X соединена только с Y
№4 · Краткий ответ
1 задача · 3 балла
4. Кратчайший путь в графе
В неориентированном графе рёбра имеют единичную длину: A соединена с B и C; B соединена с D; C соединена с E; D соединена с F; E соединена с F. Какова длина кратчайшего пути из A в F? Запишите число рёбер в этом пути.
№5 · Множественный выбор
1 задача · 5 баллов
5. Обход дерева и восстановление структуры
Дано дерево каталогов. Корень — каталог A. В нём находятся каталоги B и C. В каталоге B находятся файлы b1 и b2. В каталоге C находится каталог D, в котором находится файл d1. Выберите все верные утверждения.