Олимпиадная задача по теории графов: страна Озёрная и количество остро
В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?
Показать ответ
4 острова.
Разобрать решение
Рассмотрим плоский граф, вершины которого соответствуют озёрам, а рёбра – каналам. Пусть он разрезает плоскость на F кусков. По формуле Эйлера (задача 130759) 7 – 10 + F = 2, то есть F = 5. Один из этих кусков материк, а остальные – острова.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.