Том 11. Карты метро и нейронные сети. Теория графов

ДЕРЕВЬЯ И ВЕРОЯТНОСТИ

При анализе вероятностей различных событий (например, в играх) возможные альтернативные исходы и соответствующие вероятности часто представляют в форме дерева, где вершины соответствуют возможным исходам, а ребра — значениям вероятностей возможных исходов. Соответствующие расчеты выполняются на основе дерева. На рисунке представлено дерево, соответствующее игре, в которой нужно бросить сначала монету, затем — кубик. В теории игр, которая широко применяется в экономике, подобные представления используют очень часто.

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

* * *

У. УИНГФИЛД И А. А. МАРКОВ: ТЕННИС И ТЕОРИЯ ГРАФОВ

Уолтер Уингфилд (1833–1912) запатентовал игру под названием теннис в феврале 1874 года. Андрей Андреевич Марков (1856–1922) занимался изучением последовательностей случайных событий, которые позднее стали называться цепями Маркова. Цепь Маркова представляет собой ориентированный граф, вершинам которого соответствуют состояния, а дугам — переходы из одного состояния в другое в зависимости от вероятности исходного события, но не всей последовательности предшествующих событий. Уингфилда и Маркова объединяет работа А. Л. Садовского и Л. Е. Садовского «Математика и спорт», в которой цепи Маркова используются для анализа теннисных партий. Так, на рисунке вероятности возможных исходов для каждого события соответственно равны 0,6 и 0,4.

* * *

Рассмотрим задачу, которую можно решить с помощью деревьев. Даны n городов A₁, А₂… А_n. Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

Следовательно, дерево связей между n городами будет иметь n — 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Как называется множество различных графов, которые являются деревьями?

Наверное, вы уже догадались: такое множество называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден.

* * *