Том 11. Карты метро и нейронные сети. Теория графов - страница 7
Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение:
«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и v существует единственный путь. Это равносильно следующему утверждению: С является связным графом, если он имеет р вершин и р — 1 ребро».
Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения р возрастает очень быстро.
Причина этому такова. Пусть G — дерево. Даны две вершины G, u и v. Так как граф G является связным, то существует по меньшей мере один путь между u и v. Если бы между этими вершинами существовало два пути, С>1 и С>2, то в графе G образовался бы цикл, что невозможно. Разумеется, если между двумя произвольными вершинами графа существует единственный путь, граф является связным и не содержит циклов.
* * *
ДЕРЕВЬЯ И ВЕРОЯТНОСТИ
При анализе вероятностей различных событий (например, в играх) возможные альтернативные исходы и соответствующие вероятности часто представляют в форме дерева, где вершины соответствуют возможным исходам, а ребра — значениям вероятностей возможных исходов. Соответствующие расчеты выполняются на основе дерева. На рисунке представлено дерево, соответствующее игре, в которой нужно бросить сначала монету, затем — кубик. В теории игр, которая широко применяется в экономике, подобные представления используют очень часто.
Для расчета вероятностей нужно четко представлять все возможные исходы.
* * *
У. УИНГФИЛД И А. А. МАРКОВ: ТЕННИС И ТЕОРИЯ ГРАФОВ
Уолтер Уингфилд (1833–1912) запатентовал игру под названием теннис в феврале 1874 года. Андрей Андреевич Марков (1856–1922) занимался изучением последовательностей случайных событий, которые позднее стали называться цепями Маркова. Цепь Маркова представляет собой ориентированный граф, вершинам которого соответствуют состояния, а дугам — переходы из одного состояния в другое в зависимости от вероятности исходного события, но не всей последовательности предшествующих событий. Уингфилда и Маркова объединяет работа А. Л. Садовского и Л. Е. Садовского «Математика и спорт», в которой цепи Маркова используются для анализа теннисных партий. Так, на рисунке вероятности возможных исходов для каждого события соответственно равны 0,6 и 0,4.
* * *
Рассмотрим задачу, которую можно решить с помощью деревьев. Даны n городов A>1, А>2… А>n. Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.
Следовательно, дерево связей между n городами будет иметь n — 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Как называется множество различных графов, которые являются деревьями?
Наверное, вы уже догадались: такое множество называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден.
* * *
ГРАФЫ И ГЕНЕАЛОГИЧЕСКИЕ ДЕРЕВЬЯ
Родословную человека или семьи можно представить в четкой и упорядоченной форме с помощью графа, в вершинах которого размещаются фотографии, имена и годы жизни родственников, а ребра графа указывают на родственные отношения. Такое дерево может быть нисходящим и изображать всех потомков одной супружеской пары или восходящим, на котором будут представлены все предки конкретного человека.
В прошлом генеалогические деревья изображались в виде настоящих деревьев с ветвями и листьями. Сегодня благодаря использованию графов генеалогические деревья стали более понятными, пусть и менее живописными. Многие из них представлены в цифровом виде (различные программы для составления генеалогических деревьев можно найти в интернете). В настоящее время в виде генеалогических деревьев также изображают родословные собак, скаковых лошадей, боевых быков, связи политических партий, музыкальных жанров, родственных языков и многое другое. Быть может, читатель захочет составить свое генеалогическое древо по прочтении этой главы.
