А

Для решения задачи давайте разберем каждый пункт:

№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 \).