NEW
Font size
WorksheetsВопросы по теории графов
Total questions: 20
Worksheet time: 10mins
Как называется множество основных объектов в графе?
Рёбра
Вершины
Петли
Что такое степень вершины?
Число рёбер, инцидентных вершине
Количество соседних графов
Мощность множества рёбер
Как называется вершина с одной инцидентной связью?
Висячая вершина
Центральная вершина
Переменная вершина
Граф без петель и кратных рёбер называется:
Направленный граф
Обыкновенный граф
Полный граф
Сумма степеней всех вершин в графе равна:
Числу рёбер
Удвоенному числу рёбер
n-1
Какой граф называется изолированным?
Вершина с одной связью
Вершина со степенью 0
Граф без рёбер
Лемма о рукопожатиях утверждает:
Сумма степеней всех вершин равна количеству петель
Четное число вершин нечётной степени
Все рёбра имеют разные концы
Два графа называются изоморфными, если:
Их рёбра совпадают
Существует взаимно-однозначное соответствие вершин, сохраняющее смежность
Они имеют одинаковые степени вершин
Какой путь называется простым?
В нём есть повторяющиеся рёбра
В нём нет повторяющихся рёбер
Как определяется расстояние между двумя вершинами?
Числом рёбер в самом длинном пути
Длиной кратчайшего пути
Мощностью подграфа
Радиус графа — это:
Среднее расстояние между вершинами
Минимальный эксцентриситет
Максимальный эксцентриситет
Диаметр графа — это:
Число всех рёбер
Наибольшее расстояние между двумя вершинами
Количество компонент связности
Какой граф называется связным?
Все рёбра пересекаются
Между любой парой вершин есть путь
В нём ровно один цикл
k-регулярный граф — это граф, где: • В графе ровно k вершин • Количество рёбер = k
Степень каждой вершины равна k
В графе ровно k вершин
Количество рёбер = k
Какой граф называется кубическим?
Степень каждой вершины равна двум
Регулярный граф степени три
Граф с тремя вершинами
Граф, где каждая вершина соединена со всеми остальными, называется:
Полный граф
Дерево
Цикл
Планарный граф
В операции над графами удаление вершины означает:
Удаление изолированной вершины
Удаление вершины и всех инцидентных ей рёбер
Сохранение только рёбер
Граф, полученный добавлением ребра, записывается как:
Г / e
Г + e
Г - e
Как называется граф, состоящий только из вершин, без рёбер?
Пустой граф
Полный граф
Двудольный граф
Подграф — это:
Особый тип дерева
Содержит подмножество вершин и рёбер исходного графа
Совокупность всех рёбер графа
