Дерево — это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на следующем рисунке:
В дереве можно проложить маршрут между любыми двумя вершинами.
Далее приведены все возможные деревья с числом вершин от 1 до 8.
Последовательность чисел, обозначающих количество
всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1,
2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159…
Если дерево имеет р вершин, то в нем всегда будет р — 1 ребер, но для каждого значения р можно изобразить рр-2
разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857
году. Деревья образуют очень важный класс графов, так как в них все
вершины соединены минимально возможным числом ребер. Благодаря этому
деревья находят интересное применение в самых разных областях: при
проектировании электрических цепей, телефонных сетей, при поиске
маршрутов между населенными пунктами и так далее.
Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение:
«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и v существует единственный путь. Это равносильно следующему утверждению: С является связным графом, если он имеет р вершин и р — 1 ребро».
Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения р возрастает очень быстро.
Причина этому такова. Пусть G — дерево. Даны две вершины G, u и v. Так как граф G является связным, то существует по меньшей мере один путь между u и v. Если бы между этими вершинами существовало два пути, С1 и С2, то в графе G
образовался бы цикл, что невозможно. Разумеется, если между двумя
произвольными вершинами графа существует единственный путь, граф
является связным и не содержит циклов.
* * *
ДЕРЕВЬЯ И ВЕРОЯТНОСТИ
При анализе вероятностей различных событий
(например, в играх) возможные альтернативные исходы и соответствующие
вероятности часто представляют в форме дерева, где вершины соответствуют
возможным исходам, а ребра — значениям вероятностей возможных исходов.
Соответствующие расчеты выполняются на основе дерева. На рисунке
представлено дерево, соответствующее игре, в которой нужно бросить
сначала монету, затем — кубик. В теории игр, которая широко применяется в
экономике, подобные представления используют очень часто.
Для расчета вероятностей нужно четко представлять все возможные исходы.
* * *
У. УИНГФИЛД И А. А. МАРКОВ: ТЕННИС И ТЕОРИЯ ГРАФОВ
Уолтер Уингфилд (1833–1912) запатентовал игру под названием теннис в феврале 1874 года. Андрей Андреевич Марков (1856–1922)
занимался изучением последовательностей случайных событий, которые
позднее стали называться цепями Маркова. Цепь Маркова представляет собой
ориентированный граф, вершинам которого соответствуют состояния, а
дугам — переходы из одного состояния в другое в зависимости от
вероятности исходного события, но не всей последовательности
предшествующих событий. Уингфилда и Маркова объединяет работа А. Л.
Садовского и Л. Е. Садовского «Математика и спорт», в которой цепи
Маркова используются для анализа теннисных партий. Так, на рисунке
вероятности возможных исходов для каждого события соответственно равны
0,6 и 0,4.
* * *
Рассмотрим задачу, которую можно решить с помощью деревьев. Даны n городов A1, А2… Аn.
Зная затраты на установление сообщения между каждой парой городов
(стоимость строительства дорог, прокладки водо- и газопровода, линий
электропередачи, телефонных линий), определите, как можно соединить
города самым дешевым способом. Очевидно, что сеть «экономических связей»
будет деревом, так как все города должны быть связаны друг с другом и
не должно существовать циклов. Если бы в этой сети существовал цикл,
можно было бы удалить одно из его ребер и все города по-прежнему были бы
соединены между собой, но уже при меньших затратах.
Следовательно, дерево связей между n городами будет иметь n
— 1 ребро. Соединим два города, для которых стоимость прокладки всех
коммуникаций будет наименьшей. Затем соединим один из них с третьим
городом, для которого стоимость коммуникаций будет минимальной, и так
далее. Как называется множество различных графов, которые являются
деревьями?
Наверное, вы уже догадались: такое множество
называется лесом. Вопреки известной пословице, в теории графов за
деревьями лес виден.
* * *
ГРАФЫ И ГЕНЕАЛОГИЧЕСКИЕ ДЕРЕВЬЯ
Родословную человека или семьи можно представить в
четкой и упорядоченной форме с помощью графа, в вершинах которого
размещаются фотографии, имена и годы жизни родственников, а ребра графа
указывают на родственные отношения. Такое дерево может быть нисходящим и
изображать всех потомков одной супружеской пары или восходящим, на
котором будут представлены все предки конкретного человека.
В прошлом генеалогические деревья изображались в
виде настоящих деревьев с ветвями и листьями. Сегодня благодаря
использованию графов генеалогические деревья стали более понятными,
пусть и менее живописными. Многие из них представлены в цифровом виде
(различные программы для составления генеалогических деревьев можно
найти в интернете). В настоящее время в виде генеалогических деревьев
также изображают родословные собак, скаковых лошадей, боевых быков,
связи политических партий, музыкальных жанров, родственных языков и
многое другое. Быть может, читатель захочет составить свое
генеалогическое древо по прочтении этой главы.
 Современное генеалогическое древо царской семьи Романовых, составленное на компьютере, и генеалогическое древо семейства Ругон-Маккаров из произведений писателя Эмиля Золя, составленное в 1878 году.
ГРАФ МАТЕМАТИЧЕСКИХ СВЯЗЕЙ
По адресу http://genealogy.math.ndsu.nodak.edu
находится страница математического генеалогического проекта
(Mathematics Genealogy Project), на которой собраны данные о математиках
и их «потомках» — тех ученых, которые защитили докторскую диссертацию
под их руководством. Проект непрерывно пополняется данными о все новых и
новых диссертациях, и постепенно формируется дерево взаимосвязей между
всеми математиками. По состоянию на апрель 2010 года были собраны данные
о 140 982 математиках.
Главная страница проекта Mathematics Genealogy Project
|
