Вопрос:

Задан граф, содержащий 130 вершин. Известно, что он связный. Верно ли, что в графе любые две вершины соединены единственным путём?

Задан граф, содержащий 130 вершин. Известно, что он связный. Верно ли, что в графе любые две вершины соединены единственным путём?
Фотография

Ответ ассистента

**Ответ: нет** **Решение:** Связный граф — это граф, в котором между любыми двумя вершинами есть хотя бы один путь. Если в связном графе любые две вершины соединены **единственным** путём, то такой граф называется **деревом**. Однако в условии не сказано, что этот граф — дерево. Связный граф может содержать циклы. Если в графе есть хотя бы один цикл, то между вершинами этого цикла (и многими другими) будет существовать более одного пути. Так как нам известно только то, что граф связный, мы не можем утверждать, что путь единственный. Следовательно, утверждение неверно.

Похожие задачи

Посмотри похожие решения — вдруг одно из них подойдёт тебе

Другие решения

Что ещё задавали пользователи