Новая школа

Вот тест по теме: Путь в графе, цепи и циклы. Предмет: Математика. Класс: 7. Тип вопросов: Единственный выбор. Количество вопросов: 10. Ответы приведены в конце.

Что такое путь в неориентированном графе? A) последовательность вершин v0, v1, ..., vk, где каждое соседнее пары вершин соединено ребром и все вершины различны. B) последовательность ребер, каждая пара соседних ребер имеет общий конец. C) набор вершин без рёбер. D) путь обязательно должен начинаться и заканчиваться в одну и ту же вершину.
Какое верное различие между путём и цепью? A) Путь — последовательность вершин без повторений; цепь — последовательность рёбер без повторения рёбер. B) Путь — последовательность рёбер без повторения; цепь — последовательность вершин без повторения. C) Путь — цикл; цепь — не цикл. D) Путь всегда длиннее цепи.
Что такое цикл в графе? A) последовательность вершин, начинающаяся и заканчивающаяся в одной вершине, все промежуточные вершины различны. B) цепь, в которой можно пройти по рёбрам, возвращаясь в исходную вершину. C) любой путь, который возвращается в начальную вершину. D) граф без циклов.
В графе есть путь, состоящий из вершин v1, v2, v3, v4, v5, v6. Сколько ребер в таком пути? A) 4 B) 5 C) 6 D) 7
В неориентированном графе существует цикл из вершин A-B-C-A. Сколько уникальных вершин задействовано в этом цикле? A) 2 B) 3 C) 4 D) 5
В графе только три вершины A, B, C и рёбра AB, BC, CA. Является ли последовательность ребер AB, BC, CA цепью? A) Да B) Нет C) Только если граф связан D) Только если есть цикл
Какой тип графа может не иметь пути между некоторыми парами вершин? A) связный граф B) несвязный граф C) граф без рёбер D) граф с одним рёбром
В неориентированном ненагруженном графе кратчайший путь между двумя вершинами — это путь с минимальным количеством ребер. Выберите правильный вариант: A) минимальным количеством вершин B) минимальным количеством ребер C) минимальной суммой весов D) равным любому пути
Может ли цепь быть замкнутой (начинаться и заканчиваться в одной вершине) без повторения рёбер? A) Да, это будет цикл B) Нет C) Только в графе без рёбер D) Только если граф простой
В неориентированном графе есть вершины A, B, C, D и рёбра AB, BC, CD. Можно ли пройти от A к D без повторения рёбер? A) Да B) Нет C) Только если граф связан D) Только если есть вершина E

Ответы: 1 - A 2 - A 3 - A 4 - B 5 - B 6 - A 7 - B 8 - B 9 - A 10 - A

Пояснения к ответам (кратко):

Определение пути: последовательность вершин; соседние вершины соединены ребрами и вершины различны.
Путь: вершины без повторений; цепь: рёбра без повторения.
Цикл — циклизированная замкнутая последовательность вершин; начинается и заканчивается в одной вершине, промежуточные вершины различны.
Путь из 6 вершин имеет 5 рёбер.
Цикл A-B-C-A включает три уникальные вершины: A, B, C.
AB, BC, CA образуют trail (цепь) без повторения рёбер.
Несвязный граф может не иметь пути между некоторыми парами вершин.
В ненагруженном графе кратчайший путь минимизирует число рёбер.
Замкнутая цепь без повторения рёбер — это цикл.
Путь A-B-C-D использует три рёбра AB, BC, CD и не повторяет рёбра.

Бесплатный сервис «Учительская»

Тест на тему Путь в графе, цепи и циклы

Популярные тесты

Тест по Труду: Технологии

Вопрос 1

Вопрос 2

Вопрос 3

Вопрос 4

Вопрос 5

Вопрос 6

Вопрос 7

Вопрос 8

Вопрос 9

Вопрос 10