1. Найдите степени каждой вершины графа. Назовите вершину с наибольшей степенью.

Question

1. Найдите степени каждой вершины графа. Назовите вершину с наибольшей степенью.

Lol Lol Ученик (105), открыт 3 недели назад

1. Найдите степени каждой вершины графа.
Назовите вершину с наибольшей степенью.
Сколько нужно добавить рёбер в этом графе, чтобы из любого города можно было прилететь в любой другой без пересадок?
2. Сергей живёт в Санкт-Петербурге и каждый
отпуск навещает бабушку в Екатеринбурге и тётю с дядей, которые живут в Астрахани.
Назовите несколько путей, по которым
Сергей может посетить родственников и вернуться в Санкт-Петербург за одну поездку. Сколько рёбер содержит кратчайший путь? Если соединить
Екатеринбург и Астрахань авиамаршрутом (ребром), сколько рёбер будет содержать кратчайший путь в таком случае?

Answer 1

На первый вопрос нужен конкретный граф, что бы подсчитать степени вершин и компоненты связаности для более точного ответа.
Отвечу на второй вопрос.

Без нового маршрута кратчайший путь содержит 3 рёбра.

После добавления нового маршрута кратчайший путь также содержит 3 рёбра, но маршруты становятся более гибкими и могут быть выполнены быстрее за счёт дополнительного прямого соединения.