← Все тренажёры Деревья: код Прюфера, остовы и алгоритмы

Деревья: код Прюфера, остовы и алгоритмы

Кодирование деревьев, цикломатическое число и минимальный остов.

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

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

Режим
Режим

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

1

Какова длина кода Прюфера дерева на n≥2n\ge2 помеченных вершинах?

2

Какой лист удаляют на каждом шаге стандартного кодирования Прюфера?

3

Что записывают в код Прюфера при удалении листа?

4

Как связаны степень вершины и число появлений её метки в коде Прюфера?

5

Что минимизирует минимальное остовное дерево?

6

Когда Краскал добавляет очередное ребро?

7

Какое ребро выбирает Прим на очередном шаге?

8

Что гарантирует попарное различие весов рёбер связного графа?

9

Сколько фундаментальных циклов соответствует выбранному остову связного графа?

10

Что хранит ключ вершины в алгоритме Прима?

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

11

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

целое число

12

Граф имеет 8 вершин, 11 рёбер и 2 компоненты. Найдите цикломатическое число.

целое число

13

Метка 4 встречается в коде Прюфера 3 раза. Чему равна степень вершины 4?

целое число

14

Код Прюфера дерева на метках 1,2,3,41,2,3,4 равен (2,2)(2,2). Сколько в дереве листьев?

целое число

15

Треугольник имеет веса AB=1AB=1, BC=2BC=2, AC=4AC=4. Найдите вес MST.

целое число

16

Сколько помеченных деревьев существует на 5 вершинах?

целое число

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

17

Какие утверждения о коде Прюфера верны?

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

18

Какие действия входят в декодирование Прюфера?

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

19

Что верно об остовах и циклах?

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

20

Какие утверждения о MST верны?

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

21

Что утверждает лемма о безопасном ребре при построении MST?

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

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

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

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

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

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

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