2. Графы

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

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

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

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

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

Рис. 1.

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

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

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

Рис.2

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

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

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

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

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

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

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

В некоторых задачах нам потребуются графы, на рёбрах которых поставлены стрелки, указывающие на переход из одного состояния в другое. Ребро графа называется ориентированным, если одну вершину считают началом рёбра, а другую – концом. Граф, все рёбра которого ориентированы, называется ориентированным графом.

Рис. 3

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

Решение. Пусть А и В – две команды, одержавшие одинаковое число побед, например, l побед. Пусть к тому же А выиграла у В. Те l команд, у которых выиграла команда В, обозначим C₁, C₂, …, C₁ (рис.4).

Рис.4

Команда А не могла одержать победы над всеми командами С₁, С₂, ..., С_l, так как иначе она одержала бы больше чем l побед (одна победа над В уже имеется). Следовательно, среди команд С₁, С₂, ..., С_l, найдется хотя бы одна, которая одержала победу над А.

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

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

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

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

Рис. 5