Дерево задано кодом из натуральных чисел 213167. На дереве задано паросочетание {24,35,67}. Относительно него сформулированы три утверждения. Верны ли они? (1) парососочетание наибольшее (2) паросочетание максимальное (3) паросочетание совершенное. Ответ

6 ноября 2025
Высшая математика

Условие:

Дерево задано кодом из натуральных чисел 213167. На дереве задано паросочетание \{24,35,67\}. Относительно него сформулированы три утверждения. Верны ли они?
(1) парососочетание наибольшее
(2) паросочетание максимальное
(3) паросочетание совершенное.

Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0 ; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.

Решение:

Мы решим задачу пошагово. ───────────────────────────── Шаг 1. Восстановление дерева по коду Дан код из натуральных чисел 213167. Этот код означает, что у нас имеется 6 чисел, а по схеме Прюфера дерево на n вершинах кодируется списком длины n–2. Отсюда n = 6 + 2 = 8. То есть вершины дерева – 1, 2, …, 8. Правило: степень вершины = (количество вхождений вершины в код) + 1. Рассмотрим код: • код = [2, 1, 3, 1, 6, 7]. Подсчитаем, сколько раз встречается каждая вершина: – 1 встречается два раза → deg(1) = 2 + 1 = 3; – 2 встречается 1 раз → deg(2) = 1 + 1 = 2; – 3 встречается 1 раз → deg(3)...