Далее: Глава II. Случайные события Вверх: Глава I. Элементы комбинаторики Назад: §3. Методы комбинаторики

§4. Графы

Начало теории графов было положено Эйлером в 1736 году в его знаменитой задаче о кёнигсбергских мостах. Исследования электрических цепей, моделей кристаллов и структур молекул, развитие формальной логики побудили к изучению графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов. Проблема четырех красок - наиболее известная среди таких задач - была поставлена Де Морганом в 1850 году. В ХХ столетии теория графов получила дальнейшее развитие, которое связано с новыми ее приложениями: в теории игр и программировании, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем биологии и психологии.

В данной работе графы являются основой для иллюстрации основных результатов в теории вероятностей, что позволяет сделать рассматриваемый материал более наглядным и доступным.

Графом называется два множества с отношением инцидентности между их элементами, называемыми вершинами и ребрами. Это отношение удовлетворяет единственному требованию (аксиоме) - любое ребро инцидентно не более чем двум вершинам.

Пример 16. Построить граф, вершинами которого является множество {2, 3, 4, 5, 6}, а инцидентность задается наличием у указанных цифр делителей, отличных от единицы.

Решение. Взятые цифры обозначим на рисунке кружками, которые соединим отрезками (либо петлями) при наличии общих делителей.

Рис. 1

Этот граф содержит 5 петель - ребра, соединяющие (инцидентные) вершину саму с собой. Вершина "5" - изолированная, а подграф с вершинами {2, 3, 4, 6} является связным. Граф связный, если из любой вершины в любую другую можно "пройти" по ребрам. Циклом называется замкнутый путь из ребер, например, вершины {2, 4, 6} с соединяющими их попарно ребрами. Степенью вершины называется число ребер графа, инцидентных этой вершине.

Пример 17. Сколько различных обедов П.И. Чичиков мог насчитать из блюд, выставленных на столе у П.П. Петуха, если бы на каждый обед выбирать только одно холодное блюдо, одно первое блюдо и одно второе блюдо? На столе у П.П. Петуха на этот раз были выставлены из холодных блюд студень с хреном, свежая икра, свежепросоленная белужина; на первое - уха из стерлядей, щи с грибами; на второе - осетрина жареная, теленок, жаренный на вертеле.

Решение. Каждое блюдо изобразим кружком с первой буквой названия блюда, а соответствие блюд одного обеда - отрезками, соединяющими кружки. Возникает схема (граф), изображенный на рисунке:

Рис. 2

Граф помогает сосчитать число возможностей, их оказалось 12. Он же помогает узнать, сколько различных обедов можно составить, например, с икрой.

Математики, обратив внимание на сходство схемы на рисунке 2 с веткой дерева с листочками, назвали такие графы "деревьями".

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

Пример 18. Поступающий на физмат должен сдать три вступительных экзамена по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов?

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

Рис. 3

Таким образом, для поступления на физмат можно сдать вступительные экзамены 10 различными способами.

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

При рассмотрении цепей Маркова (далее §11) нам потребуются графы, на ребрах которых поставлены стрелки, указывающие на переход из одного состояния в другое. Ребро графа называется ориентированным, если одну вершину считают началом ребра, а другую - концом. Граф, все ребра которого ориентированы, называется ориентированным графом.

Пример 19. Турнир по волейболу проводится по круговой системе между $n$ командами. Докажите, что если какие-нибудь две команды одержали в турнире одинаковое число побед, то найдутся среди участников три команды I, II и III такие, что I выиграла у II, II выиграла у III, a III выиграла у I.

Решение. Пусть $A$ и $B$ - две команды, одержавшие одинаковое число побед, например, $l$ побед. Пусть к тому же $A$ выиграла у $B$. Те $l$ команд, у которых выиграла команда $B$, обозначим $C_{1}$, $C_{2}$, ..., $C_{l}$ (рис. 4).

Рис. 4

Команда $A$ не могла одержать победы над всеми командами $C_{1}$, $C_{2}$, ..., $C_{l}$, т.к. иначе она одержала бы больше чем $l$ побед (одна победа над $B$ уже имеется). Следовательно, среди команд $C_{1}$, $C_{2}$, ..., $C_{l}$ найдется хотя бы одна, которая одержала победу над $A$.

Из этого примера следует один из результатов теории графов о существовании ориентированных циклов в полном ориентированном графе.

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

Пример 20. Построить вероятностное дерево исходов двух подбрасываний монеты на твердую поверхность.

Решение. Поскольку каждое подбрасывание монеты может закончиться одним из двух исходов, а именно, выпадением "герба" или "решки", то вероятностное дерево выглядит следующим образом:

Рис. 5

Вопросы для самоконтроля

1. Что называется графом? Примеры.
2. Какой граф является связным?
3. Дерево исходов.
4. Эйлеровы графы, необходимые и достаточные условия.
5. Примеры Гамильтоновых графов.
6. Ориентированные графы.
7. Вероятностные графы и порядок их построения.
8. Приведите примеры вероятностных деревьев.

Задачи

I 31. Имеются три листа бумаги; некоторые из них разрезаются на 3 части, несколько новых кусков - на три более мелкие части и т.д. Сколько всего получится листков, если всего разрезано было $k$ листков?

  32. Составьте множество трехзначных чисел, которые можно записать с помощью цифр 2 и 5. Сколько таких чисел?

  33. В волейбольном турнире участвуют 19 команд. Докажите, что в любой момент найдется команда, сыгравшая четное число матчей.

  34. Найдется ли граф с пятью вершинами, степени которых все различны между собой, т.е. равны 0, 1, 2, 3, 4?

  35. Участники областного студенческого лагеря актива, познакомившись, обменялись конвертами с адресами. Докажите, что:

          а) всего было передано четное число конвертов;
          б) число студентов, обменявшихся конвертами нечетное число раз, четное.

  36. Девять школьников участвуют в шахматном турнире в один круг. В определенный момент выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один школьник еще не сыграл ни одной партии, либо в точности один сыграл все партии.

II 37. Рассматриваются всевозможные деревья с пятью вершинами, причем каждая из вершин имеет либо степень1, либо степень 2. Сколько таких деревьев существует?

  38. Построить вероятностное дерево выпадения шести очков на игральной кости при трех ее подбрасываниях.

III 39. Турнир проводится в один круг среди $n$ команд. Сколько команд могут пройти:

           а) без единого поражения;
           б) без единой победы?

  40. Извлекаем последовательно две карты с возвратом (без возврата) из колоды в 52 карты. Построить вероятностное дерево вынимания козырной карты.

Далее: Глава II. Случайные события Вверх: Глава I. Элементы комбинаторики Назад: §3. Методы комбинаторики