Андрей Коняев

Главный редактор

Хорошая математическая задачка на день Пи

В день Пи вряд ли что-то может быть лучше хорошей задачи по математике. Вот вам именно такая.

Пусть дан граф на плоскости — то есть конечное множество точек, соединенных ребрами. Ребра могут быть очень кривые, но не пересекаются ни сами с собой, ни с другими ребрами. У каждого ребра есть два конца. Они оба могут быть одной вершиной — тогда ребра образуют петлю, а могут быть разными вершинами.

Степенью вершины называется количество ребер, для которых эта вершина является одним из концов. При этом петли считаются дважды. То есть, например, если нарисовать одну вершину и одну петлю, то степень вершины будет равна двум. Всюду дальше мы считаем, что степень нашей вершины как минимум два.

Наш граф разбивает плоскость на куски. У каждого куска есть граница, состоящая из вершин и ребер. Кусок будем называть гранью, а количество ребер и вершин в границе (они совпадают, конечно же) назовем порядком грани. Если, скажем, нарисовать треугольник, то он разбивает плоскость на два куска — внутренность и внешность треугольника. В обоих случаях порядок граней равен трем. Если же вспомнить петлю, о которой речь шла выше, то там получаются две грани порядка один.

Граф на плоскости называется правильным, если порядки всех граней совпадают (скажем, они равны b) и степени всех вершин тоже совпадают (они равны a). Эти два числа могут не совпадать.

Задача: описать все правильные графы на плоскости. То есть предъявить список и доказать что других нет.

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

Сложной нашу задачу делает, конечно же, отсутствие условий связности и ограничений на порядки граней. Решения присылайте по адресу pizzaforpiday@gmail.com

Ранее в этом блоге

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.