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

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

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

Определение. Пусть задано некоторое непустое множество

    \[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)\}.\]

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

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

    \[1\]

    \[2\]

,

    \[2\]

    \[4\]

,

    \[3\]

    \[3\]

,

    \[4\]

    \[2\]

,

    \[5\]

    \[3\]

,

    \[6\]

    \[3\]

,

    \[7\]

    \[3\]

,

    \[8\]

    \[2\]

.

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

    \[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 и др.

    [Ответить]

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

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