Викторина по теории графов

Что такое граф?

• Только набор линий

• Система чисел

• Только набор точек

• Система объектов и связок

Как называется граф, в котором нет циклов?

• Дерево

• Ориентированный граф

• Цикл

• Мультиграф

Что такое висячая вершина?

• Вершина с двумя ребрами

• Вершина без ребер

• Вершина с одним ребром

• Вершина с тремя ребрами

Какой граф называется эйлеровым?

• Граф с четным числом рёбер у всех вершин

• Граф с нечетным числом рёбер

• Граф без рёбер

• Граф с петлями

Что такое подграф?

• Граф с одним ребром

• Граф с петлями

• Граф без рёбер

• Граф, состоящий из подмножества вершин и рёбер

Как называется граф, в котором все вершины имеют одинаковую степень?

• Регулярный граф

• Обыкновенный граф

• Дерево

• Эйлеров граф

Что такое кратные рёбра?

• Рёбра, которые являются петлями

• Рёбра, которые не соединяют вершины

• Рёбра, соединяющие разные вершины

• Рёбра, соединяющие одну и ту же пару вершин

Какой граф называется двудольным?

• Граф, состоящий только из вершин

• Граф, в котором есть циклы

• Граф, вершины которого можно разбить на два подмножества

• Граф, в котором все рёбра направлены

Что такое лемма о рукопожатиях?

• Каждый граф имеет хотя бы одну петлю

• Сумма всех рёбер равна количеству вершин

• Каждая вершина соединена с двумя рёбрами

• Сумма степеней всех вершин равна удвоенному числу рёбер

Что такое граф-дерево?

• Связный граф без циклов

• Граф с несколькими циклами

• Граф с петлями

• Граф, состоящий только из рёбер