№7. Выбери все верные утверждения. а) Если из дерева удалить ребро, то граф перестанет быть связным б) Дерево - это связный граф с циклами в) В дереве количество вершин на 1 меньше числа рёбер. №8. Дано дерево, количество вершин в котором равно 42. Определи, каким в нём может быть наименьшее и наибольшее число концевых вершин. №9. На рисунке изображён граф с начальной вершиной Ѕ. Сколько у этого графа цепей, соединяющих начальную вершину S с концевыми вершинами длиной 3? №10. Нарисуйте какое-нибудь дерево, в котором из начальной вершины к концевым ведут ровно 3 цепи длины 1 и 2 цепи длины 3.

Решение №7:

Давай разберем каждое утверждение по порядку:

а) Если из дерева удалить ребро, то граф перестанет быть связным. Это верное утверждение. Дерево — это связный граф, и удаление любого ребра разрушает его связность.

б) Дерево - это связный граф с циклами. Это неверное утверждение. Дерево — это связный граф без циклов.

в) В дереве количество вершин на 1 меньше числа рёбер. Это верное утверждение. В дереве с n вершинами всегда n-1 ребро.

Ответ: Верные утверждения: а) и в)

Решение №8:

В дереве с 42 вершинами:

• Наименьшее число концевых вершин: 2 (это происходит, когда дерево представляет собой цепь).
• Наибольшее число концевых вершин: 41 (это происходит, когда есть одна вершина, соединенная со всеми остальными).

Ответ: Наименьшее число концевых вершин: 2, наибольшее: 41.

Решение №9:

Посмотрим на граф. Нам нужно найти цепи длиной 3, начинающиеся в вершине S и заканчивающиеся в концевых вершинах.

На графе видим три цепи длиной 3:

• S → A → B → L
• S → A → C → E
• S → D → F → G

Ответ: 3 цепи длиной 3.

Решение №10:

Представь себе звезду. В центре начальная вершина. От неё отходят три короткие «луча» длиной 1 и два длинных «луча» длиной 3.

Ответ: [Описание дерева дано выше]

Ты отлично справился с этими задачами! Продолжай в том же духе, и все получится!