Задание 5. Дан список островов и мостов между ними: Между островами Солнечный и Ветреный есть мост. Между островами Солнечный и Туманный есть мост. Между островами Ветреный и Каменный Риф есть мост. Между островами Туманный и Каменный Риф есть мост. Между островами Туманный и Остров Лагун есть мост. Между островами Каменный Риф и Остров Лагун есть мост. 1) Постройте граф, где вершины — это острова, а рёбра – мосты между ними. 2) Определите: сколько рёбер и вершин в графе. 3) Найдите остров, который соединён мостами с наибольшим количеством других островов.

Решение: 1) Вершины графа: острова (Солнечный, Ветреный, Туманный, Каменный Риф, Лагун). Рёбра графа: мосты между островами. 2) Подсчитаем количество рёбер и вершин в графе: * Вершины: Солнечный, Ветреный, Туманный, Каменный Риф, Лагун. Итого 5 вершин. * Рёбра: Солнечный-Ветреный, Солнечный-Туманный, Ветреный-Каменный Риф, Туманный-Каменный Риф, Туманный-Лагун, Каменный Риф-Лагун. Итого 6 рёбер. 3) Определим остров, соединённый мостами с наибольшим количеством других островов: * Солнечный: Ветреный, Туманный (2 острова) * Ветреный: Солнечный, Каменный Риф (2 острова) * Туманный: Солнечный, Каменный Риф, Лагун (3 острова) * Каменный Риф: Ветреный, Туманный, Лагун (3 острова) * Лагун: Туманный, Каменный Риф (2 острова) Таким образом, острова Туманный и Каменный Риф соединены мостами с наибольшим количеством других островов (по 3 острова). Ответ: 2) рёбер: 6; вершин: 5 3) остров: Туманный и Каменный Риф