Задача 30795

Тема:    [ Планарные графы. Формула Эйлера ]

Сложность: 3+ Классы: 7,8,9

Условие

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

Решение

Рассмотрим плоский граф, вершины которого соответствуют озёрам, а рёбра – каналам. Пусть он разрезает плоскость на F кусков. По формуле Эйлера (задача 30759)  7 – 10 + F = 2,  то есть  F = 5.  Один из этих кусков материк, а остальные – острова.

Ответ

4 острова.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	017