Номер 1, страница 5, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

1 Какие из графов на рисунке 5 являются деревьями?

а) б) в) г) д) Рисунок 5

В теории графов дерево — это связный ациклический граф. Это означает, что граф является деревом, если он удовлетворяет двум ключевым условиям:

1. Связность: между любыми двумя вершинами графа существует путь.
2. Ацикличность: в графе нет циклов (замкнутых путей, где начальная и конечная вершины совпадают).

Эквивалентное условие для графа с $V$ вершинами и $E$ рёбрами: граф является деревом, если он связный и при этом $E = V - 1$.

Проанализируем каждый из представленных графов:

а)

Данный граф является связным, так как все "периферийные" вершины соединены с центральной, а значит, и друг с другом через неё. Циклы в графе отсутствуют. Следовательно, он удовлетворяет определению дерева. Проверим по формуле: число вершин $V = 7$, число рёбер $E = 6$. Равенство $E = V - 1$ выполняется ($6 = 7 - 1$).
Ответ: является деревом.

б)

Этот граф также является связным — от любой вершины можно дойти до любой другой. Замкнутых путей (циклов) в нём нет. Таким образом, это дерево. Проверим по формуле: число вершин $V = 12$, число рёбер $E = 11$. Равенство $E = V - 1$ выполняется ($11 = 12 - 1$).
Ответ: является деревом.

в)

Этот граф, представляющий собой простую цепь (путь), является связным и не содержит циклов. Следовательно, это дерево. Проверка по формуле: число вершин $V = 3$, число рёбер $E = 2$. Равенство $E = V - 1$ выполняется ($2 = 3 - 1$).
Ответ: является деревом.

г)

На рисунке изображены две отдельные, не связанные между собой части (компоненты связности). Поскольку не от каждой вершины можно добраться до каждой другой, граф является несвязным. По определению, дерево должно быть связным, поэтому этот граф не является деревом. Такой тип графа называется лесом.
Ответ: не является деревом.

д)

Этот граф является связным, однако он содержит цикл — замкнутый контур, соединяющий внешние вершины. По определению, дерево должно быть ациклическим. Наличие цикла означает, что данный граф не является деревом.
Ответ: не является деревом.