174.13K
Category: programmingprogramming

В стране Озерная. Решение задачи при помощи графа

1.

В стране Озерная
Решение задачи при помощи графа
Работу выполнили студенты группы ИС22-03:
Тохтунов Тимофей & Клюев Александр

2.

Условие задачи
В стране Озёрная 7 озёр, соединённых между собой 10
каналами, причём от любого озера можно доплыть до любого
другого. Сколько в этой стране островов?

3.

Решение задачи
• Островам
Рассмотрим
граф, Вв котором
вершины
соответствуют
островам,
Для
нашего
соответствуют
графа
= 7, Рвсе
= 10.
грани,
Подставляя
кроме
внешней
в формулу,
(она
получаема7—
рёбра—
Понятно,
что
граф
будет
и
10
бесконечно
+ Г = 2.каналам.
Отсюда
большая
следует,
во всечто
стороны
Гполученный
= 5, то
и острову
есть, рёбра
соответствовать
графаплоским
разбивают
не
связным,значит,
значит,
плоскость
может),
на 5 частей.
ихдля
4 него выполняется формула Эйлера: В— Р + Г
= 2.

4.

Ответ:
•4

5.

Спасибо за внимание
• Готовы ответить на ваши вопросы
English     Русский Rules