Введение в теорию графов. Тематический контроль
Этот тест направлен на закрепление темы "Введение в теорию графов". Ключевые слова: вершина, степень вершины, компоненты связности, пути графа.
Задание 1
Путь, у которого начало и конец совпадают, называется...
Задание 2
Сколько компонент связности имеет связный граф?
Задание 3
Какой граф называется связным?
Задание 4
Сколько вершин соединяет каждое ребро?
Задание 5
Какова минимальная разница между количеством рёбер и количеством вершин в связном графе, где количество рёбер больше количества вершин? Если такого графа не существует, ответьте «0».
Задание 6
В чём отличие несвязного графа от связного?
Задание 7
Количество рёбер, исходящих из вершины, называется...
Задание 8
Сколько рёбер в полном графе с пятью вершинами?
Задание 9
На острове живут 100 хамелеонов: 30 красных, 40 синих и 30 зелёных. Когда встречаются два хамелеона разного цвета, они оба меняют свой цвет на третий. Каково минимальное количество встреч хамелеонов, необходимое для того, чтобы разница между количеством хамелеонов любого из двух цветов была кратна трём? (Предполагается, что встречи происходят оптимальным образом.)
Задание 10
В графе есть цикл, состоящий из 5 вершин. К этому графу добавили одно ребро, соединив две вершины, уже входящие в этот цикл. Укажите разницу между количеством вершин и количеством рёбер.
Задание 11
Какое минимальное количество вершин необходимо для графа, содержащего хотя бы один цикл длиной 3, хотя бы один цикл длиной 4 и хотя бы один цикл длиной 6?