Распечатать запись Распечатать запись

Немного о графах

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

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

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

Обычно в качестве множества V берут множество первых n натуральных чисел, т.е. вершины графа просто нумеруют по порядку. Слева на рисунке вы видите изображение графа с V=\{1,2,3,4,5,6,7,8\} и ребрами

E=\{ (1,2),(1,3),(2,3),(2,5),(2,8),(3,4),(4,6),(5,6),(5,7),(6,7),(7,8)\}.

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

На рисунке слева степени вершин графа такие 12, 24, 33, 42, 53, 63, 73, 82.

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

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

Теорема. Число помеченных графов с n вершинами равно 2^k, где k=n(n-1)/2.

Доказательство. Рассмотрим множество всех вершин графа V=\{1,2,\ldots,n\} и множество E=\{(1,2),(1,3),(1,4),\ldots,(n-1,n)\} всех потенциально возможных его ребер. Множество E содержит k=n(n-1)/2 элементов — столько же, сколько ребер в полном графе K_n.

Для каждого ребра (a,b) из множества E возможно два варианта: либо оно есть в нашем графе, либо его нет в графе. Тем самым число различных помеченных графов с n вершинами равно 2^k.

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

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

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

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

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

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

Один комментарий

  1. 1 Сапаров Мурад:

    Мои книги по графам:Алгоритмы в теории графов, 1981, рекуррентные теоретико – графовые функции и алгоритмы их вычисления 1987 и др.

    [Ответить]

Оставьте свой отзыв

Добавить изображение