← Все тренажёры Теория графов: связность, деревья, остовы и планарность

Теория графов: связность, деревья, остовы и планарность

Графы, деревья, пути, циклы и планарность.

25 заданий · Теория графов

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Чему равна сумма степеней всех вершин неориентированного графа, содержащего mm рёбер (лемма о рукопожатиях)?

2

Что утверждает фундаментальное следствие из леммы о рукопожатиях?

3

Каков критерий двудольности графа согласно теореме Кёнига?

4

Сколько рёбер содержит связное дерево с nn вершинами?

5

Сколько различных помеченных деревьев можно построить на n≥2n\ge2 вершинах согласно формуле Кэли?

6

Что означает элемент (Ak)ij(A^k)_{ij} матрицы смежности AA, возведённой в степень kk?

7

Каково условие существования эйлерова цикла в связном графе (критерий Эйлера)?

8

Как формулируется формула Эйлера для связного плоского графа с VV вершинами, EE рёбрами и FF гранями (включая внешнюю)?

9

Какая пара графов является минимальными непланарными графами в теореме Понтрягина–Куратовского?

Блок 2. Краткий ответ

10

Сколько рёбер содержит полный граф K6K_6 на 6 вершинах?

целое число

11

Граф содержит 7 вершин, степени которых равны: 2,3,3,4,4,5,52, 3, 3, 4, 4, 5, 5. Сколько рёбер в этом графе?

целое число

12

Сколько различных помеченных деревьев можно построить на 4 вершинах по формуле Кэли?

целое число

13

Связный плоский граф имеет 10 вершин и 15 рёбер. Сколько граней (включая внешнюю) имеет этот граф?

целое число

14

Сколько нечётных вершин может иметь связный граф, чтобы в нем существовал открытый эйлеров путь (начинающийся и заканчивающийся в разных вершинах)?

целое число

15

Сколько рёбер необходимо удалить из связного графа с 8 вершинами и 12 рёбрами, чтобы получить остовное дерево?

целое число

Блок 3. Несколько верных вариантов

16

Какие из перечисленных условий являются эквивалентными определениями дерева для простого неориентированного графа с n≥1n\ge1 вершинами?

Отметьте все верные варианты

17

Какие утверждения об алгоритмах поиска минимального остовного дерева (MST) верны?

Отметьте все верные варианты

18

В каких из приведенных случаев связный граф гарантированно содержит эйлеров цикл?

Отметьте все верные варианты

19

Какие свойства справедливы для планарных графов?

Отметьте все верные варианты

20

Какие утверждения о гамильтоновых графах верны?

Отметьте все верные варианты

21

Какие свойства матрицы смежности AA неориентированного графа без петель являются верными?

Отметьте все верные варианты

Блок 4. Дополнение по весенним лекциям

22

Связный граф имеет ровно 6 вершин нечётной степени. Каково минимальное число цепей, на которые можно разбить все его рёбра без повторов?

целое число

23

Какой алгоритм строит эйлеров цикл, используя стек и ещё не пройденные рёбра?

24

Когда связный нетривиальный эйлеров граф произвольно вычерчиваем из вершины vv в терминологии лекции?

25

Два треугольника имеют ровно одну общую вершину vv. Из скольких вершин этого графа он произвольно вычерчиваем?

целое число

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (25)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.