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

8 Придумайте и нарисуйте в тетради:

a) два неодинаковых дерева с четырьмя вершинами;

б) три неодинаковых дерева с пятью вершинами.

а) два неодинаковых дерева с четырьмя вершинами;

Дерево в теории графов — это связный граф (из любой вершины можно попасть в любую другую), не содержащий циклов. Важное свойство дерева: если в нем $n$ вершин, то количество рёбер всегда равно $n-1$.

Для дерева с четырьмя вершинами ($n=4$) нам потребуется $n-1 = 4-1=3$ ребра. Существует ровно два структурно различных (неизоморфных) дерева с четырьмя вершинами. Их можно построить, по-разному соединив вершины.

1. Дерево-путь ($P_4$). Вершины соединены последовательно в одну линию. Если пронумеровать вершины {1, 2, 3, 4}, то рёбра будут соединять пары (1,2), (2,3) и (3,4). В этом дереве две крайние вершины имеют степень 1 (из них выходит одно ребро), а две внутренние — степень 2.

2. Дерево-звезда ($K_{1,3}$). Одна вершина является центральной и соединена со всеми остальными. Если вершина 1 — центральная, то рёбра будут (1,2), (1,3) и (1,4). В этом дереве центральная вершина имеет степень 3, а остальные три вершины — степень 1.

Эти два дерева неодинаковы, так как у них разный набор степеней вершин (у первого {1, 2, 2, 1}, а у второго {3, 1, 1, 1}), что является фундаментальным структурным отличием.

Ответ: Первое дерево — это "цепь" из четырех вершин, соединенных последовательно (1-2-3-4). Второе дерево — это "звезда", где одна центральная вершина соединена с тремя остальными.

б) три неодинаковых дерева с пятью вершинами.

Для дерева с пятью вершинами ($n=5$) количество рёбер должно быть $n-1 = 5-1=4$. Существует три неизоморфных дерева с пятью вершинами. Их можно различить по максимальной степени вершин или по длине самого длинного пути внутри дерева.

1. Дерево-путь ($P_5$). Все пять вершин соединены в одну длинную цепь. Если пронумеровать вершины {1, 2, 3, 4, 5}, рёбра будут: (1,2), (2,3), (3,4), (4,5). Максимальная степень вершины в этом дереве равна 2.

2. Дерево-звезда ($K_{1,4}$). Одна центральная вершина соединена с остальными четырьмя. Рёбра: (1,2), (1,3), (1,4), (1,5). Максимальная степень вершины равна 4.

3. Разветвлённое дерево. Это дерево можно получить, взяв путь из четырёх вершин (например, 1-2-3-4) и присоединив пятую вершину к одной из внутренних вершин пути (например, к вершине 2). Рёбра такого дерева: (1,2), (2,3), (3,4) и (2,5). Максимальная степень вершины в этом случае равна 3.

Все три дерева структурно различны, так как у них разные максимальные степени вершин (2, 4 и 3 соответственно), что доказывает их неизоморфность.

Ответ: Три неодинаковых дерева с пятью вершинами: 1) "цепь", где все 5 вершин соединены последовательно; 2) "звезда", где одна центральная вершина соединена с остальными четырьмя; 3) разветвлённое дерево, которое можно представить как путь из 4 вершин, к одной из внутренних вершин которого присоединена пятая вершина.