Постройте деревья с 3; 7; 9 вершинами. (информатика)

№ Построение деревьев

⚠️

Задание обрезано: видно только начало условия и пункты а) рёбер, б) рёбер, остальные пункты не видны, поэтому оно не решено. Чтобы решить его, переснимите нижнюю часть страницы целиком, ближе и крупнее.

Постройте деревья с 3; 7; 9 вершинами.

Решение

Дерево — связный граф без циклов, у дерева с n вершинами ровно n − ребро.

вершины ( ребра): цепочка A–B–C.

вершин ( рёбер): A соединена с B и C, B с D и E, C с F и G.

вершин ( рёбер): рёбра A–B, A–C, A–D, B–E, B–F, C–G, D–H, H–I.

Во всех графах нет циклов, и все вершины связаны.

💡 Почему так

Дерево с n вершинами имеет n − ребро. Связность и отсутствие циклов проверяются по чертежу.

Ответ

Построены деревья: вершины — цепочка A–B–C ( ребра); вершин — рёбер; вершин — рёбер (чертежи выше).

№ Висячие вершины графа

Запишите все висячие вершины для графов в пунктах а–г.

Решение

Висячая вершина — вершина степени , то есть из неё выходит одно ребро.

а) Рёбра: BE, EC, CF, AF, FD. Степени: B — , E — , C — , F — , A — , D — . Висячие: A, B, D.

б) Рёбра: CD, CE, CA, EB, EF, EH. Степени: C — , E — , D, A, B, F, H — по . Висячие: A, B, D, F, H.

в) Рёбра: CB, BE, EF, FH, HD, HA. Степени: C — , B — , E — , F — , H — , D — , A — . Висячие: A, C, D.

г) Рёбра: FC, CD, FE, EA, FB, BH. Степени: F — , C — , E — , B — , D, A, H — по . Висячие: A, D, H.

Ответ

а) A, B, D
б) A, B, D, F, H
в) A, C, D
г) A, D, H

№ Число рёбер дерева

Найдите количество рёбер в деревьях, которые имеют:
а) 5 вершин;
б) 8 вершин;
в) L вершин;
г) K − 1 вершин.

Решение

У дерева число рёбер на меньше числа вершин: .

а)

б)

в)

г)

💡 Почему так

В дереве нет циклов и оно связно, поэтому рёбер ровно на одно меньше, чем вершин.

Ответ

а)
б)
в)
г)

Помогло?