Дано:
а) Дерево K2,3.
б) Дерево K4,4.
Найти:
1. Диаметр дерева K2,3.
2. Диаметр дерева K4,4.
Решение:
а) Для дерева K2,3:
- Вершины: A1, A2 (из первого множества) и B1, B2, B3 (из второго множества).
- Рёбра: A1 соединен с B1, B2, B3; A2 соединен с B1, B2, B3.
- Максимальное расстояние между вершинами: например, от A1 до B1 (расстояние 1) и от B1 до A2 (расстояние 2).
- Все расстояния между вершинами можно вычислить: A1-B1 (1), A1-B2 (1), A1-B3 (1), A2-B1 (1), A2-B2 (1), A2-B3 (1).
Таким образом, максимальное расстояние между двумя вершинами K2,3 равно 2.
Ответ для K2,3:
Диаметр дерева: 2.
б) Для дерева K4,4:
- Вершины: A1, A2, A3, A4 (из первого множества) и B1, B2, B3, B4 (из второго множества).
- Рёбра: каждая вершина A соединена с каждой вершиной B.
- Максимальное расстояние между вершинами: например, A1-B1 (расстояние 1), A1-B2 (расстояние 1), A1-B3 (расстояние 1), A1-B4 (расстояние 1), и так далее для остальных вершин.
В этом случае, расстояние между любыми двумя вершинами будет равно 2.
Ответ для K4,4:
Диаметр дерева: 2.