Немного о графах
Задачи на теорию графов встречаются на школьных математических олимпиадах, начиная, по моим наблюдениям, где-то с регионального этапа. И решать такие задачи обычным школьникам, которые о графах никогда не слышали, тяжело. Приведу некоторые начальные сведения из теории графов и пару, как мне кажется, интересных задач, для решения которых понадобятся только приведенные здесь сведения.
Итак, что же такое граф?
Определение. Пусть задано некоторое непустое множество и множество
пар различных элементов из
. Элементы множества
называются вершинами графа, элементы множества
называются ребрами графа, а пара
, т.е. множество вершин и множество ребер, называется графом.
Обычно в качестве множества берут множество первых
натуральных чисел, т.е. вершины графа просто нумеруют по порядку. Слева на рисунке вы видите изображение графа с
и ребрами
Если две вершины графа соединены ребром, то они называются смежными, иначе — несмежными. Число ребер, выходящих из данной вершины, называется степенью этой вершины.
На рисунке слева степени вершин графа такие —
,
—
,
—
,
—
,
—
,
—
,
—
,
—
.
Граф называется полным, если любые две его вершины смежные. Полный граф с вершинами обозначается
.
Граф с вершинами называется помеченным, если его вершины занумерованы числами от
до
. Два помеченных графа считаются равными, если множества вершин и ребер у них совпадают.
Теорема. Число помеченных графов с вершинами равно
, где
.
Доказательство. Рассмотрим множество всех вершин графа и множество
всех потенциально возможных его ребер. Множество
содержит
элементов — столько же, сколько ребер в полном графе
.
Для каждого ребра из множества
возможно два варианта: либо оно есть в нашем графе, либо его нет в графе. Тем самым число различных помеченных графов с
вершинами равно
.
А теперь задачи.
Задача 1. В игре “Спортлото-Шиш” розыгрыш главного приза проходит по следующим правилам. Каждый присутствующий в студии пишет независимо от других любое число различных пар различных натуральных чисел от до
. Если у нескольких участников выписанные ими пары совпадут, то эти участники делят между собой
рублей. Сколько участников должно быть в студии, чтобы приз заведомо оказался разыгранным?
Задача 2. После жалоб на малое число участников, выигравших главный приз в лотерее “Спортлото-Шиш” организаторы игры изменили правила. Теперь каждый присутствующий в студии пишет независимо от других различных пар различных натуральных чисел от
до
. Если у нескольких участников выписанные ими пары совпадут, то эти участники делят между собой
рублей. Сколько теперь участников должно быть в студии, чтобы главный приз оказался разыгранным?
Источник: О.И. Мельников “Теория графов в занимательных задачах”, М.: Книжный дом “ЛИБРОКОМ”, 2011.
1 Сапаров Мурад:
Мои книги по графам:Алгоритмы в теории графов, 1981, рекуррентные теоретико – графовые функции и алгоритмы их вычисления 1987 и др.
[Ответить]
16 Март 2014, 9:27