Контрольные задания > Задание 8. Изобразите связный граф с пятью вершинами, в котором максимальная длина цепи равна трём.
Вопрос:
Задание 8. Изобразите связный граф с пятью вершинами, в котором максимальная длина цепи равна трём.
Ответ:
Представьте себе пять точек (вершин), соединенных линиями (ребрами) так, чтобы от одной вершины до любой другой можно было добраться не более чем за три шага по этим линиям. Один из возможных вариантов: в центре графа располагается одна вершина, а остальные четыре вершины соединены только с ней. Таким образом, максимальная длина цепи (пути между двумя наиболее удаленными вершинами) будет равна трем (вершина -> центральная вершина -> вершина).
Пример графа:
* Одна центральная вершина (назовем её Ц).
* Четыре вершины вокруг: A, B, C, D.
* Ребра: Ц-A, Ц-B, Ц-C, Ц-D.