А

Для решения задачи давайте разберем каждый пункт: ### №1. На рисунках изображены графы: #### 1) Определите, какие из графов являются деревьями. **Определение дерева:** Дерево — это связный ациклический граф. Это значит, что в дереве нет циклов, и между любыми двумя вершинами существует ровно один путь. - **а)** Содержит цикл (A-B-C-D-A). Не дерево. - **б)** Имеет 5 вершин и 4 ребра, связный и ациклический. Дерево. - **в)** 3 вершины, 2 ребра. Связный и ациклический. Дерево. - **г)** Содержит цикл (J-K-L-J). Не дерево. - **д)** Содержит цикл (R-S-T-Q-R). Не дерево. - **е)** Имеет 4 вершины и 3 ребра, связный и ациклический. Дерево. #### 2) Для какого дерева значение количества ребер и вершин. Количество вершин \( V \) и количество рёбер \( E \) в дереве связаны формулой: \[ E = V - 1 \] **Проверяем:** - Для рисунка б: 5 вершин и 4 ребра. \( 5 - 1 = 4 \), подходит. - Для рисунка в: 3 вершины и 2 ребра. \( 3 - 1 = 2 \), подходит. - Для рисунка е: 4 вершины и 3 ребра. \( 4 - 1 = 3 \), подходит. ### №2. Придумайте и нарисуйте: #### 1) Два неразвисимых дерева с четырьмя вершинами: **Пример 1:** 1 — 2 — 3 — 4 (цепочка) **Пример 2:** ``` 1 | 2 / \ 3 4 ``` #### 2) Два неразвисимых дерева с пятью вершинами: **Пример 1:** 1 — 2 — 3 — 4 — 5 (цепочка) **Пример 2:** ``` 1 | 2 / \ 3 4 | 5 ``` Эти примеры соответствуют условиям для деревьев: они связны, ациклически и имеют отношение между вершинами и ребрами \( E = V - 1 \).