Математика, которая мне нравится

Задачи на теорию графов встречаются на школьных математических олимпиадах, начиная, по моим наблюдениям, где-то с регионального этапа. И решать такие задачи обычным школьникам, которые о графах никогда не слышали, тяжело. Приведу некоторые начальные сведения из теории графов и пару, как мне кажется, интересных задач, для решения которых понадобятся только приведенные здесь сведения.

Итак, что же такое граф?

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

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

Если две вершины графа соединены ребром, то они называются смежными, иначе — несмежными. Число ребер, выходящих из данной вершины, называется степенью этой вершины.

На рисунке слева степени вершин графа такие — , — , — , — , — , — , — , — .

Граф называется полным, если любые две его вершины смежные. Полный граф с вершинами обозначается .

Граф с вершинами называется помеченным, если его вершины занумерованы числами от до . Два помеченных графа считаются равными, если множества вершин и ребер у них совпадают.

Теорема. Число помеченных графов с вершинами равно , где .

Доказательство. Рассмотрим множество всех вершин графа и множество всех потенциально возможных его ребер. Множество содержит элементов — столько же, сколько ребер в полном графе .

Для каждого ребра из множества возможно два варианта: либо оно есть в нашем графе, либо его нет в графе. Тем самым число различных помеченных графов с вершинами равно .

А теперь задачи.

Задача 1. В игре “Спортлото-Шиш” розыгрыш главного приза проходит по следующим правилам. Каждый присутствующий в студии пишет независимо от других любое число различных пар различных натуральных чисел от до . Если у нескольких участников выписанные ими пары совпадут, то эти участники делят между собой рублей. Сколько участников должно быть в студии, чтобы приз заведомо оказался разыгранным?

Показать решение

Задача 2. После жалоб на малое число участников, выигравших главный приз в лотерее “Спортлото-Шиш” организаторы игры изменили правила. Теперь каждый присутствующий в студии пишет независимо от других различных пар различных натуральных чисел от до . Если у нескольких участников выписанные ими пары совпадут, то эти участники делят между собой рублей. Сколько теперь участников должно быть в студии, чтобы главный приз оказался разыгранным?

Показать решение

Источник: О.И. Мельников “Теория графов в занимательных задачах”, М.: Книжный дом “ЛИБРОКОМ”, 2011.