Деревья, перечисление деревьев

Лесом называется граф, не содержащий циклов. Связный лес называется деревом.

Теория перечисления графов занимается разработкой методов подсчета числа неизоморфных графов, обладающих теми или иными свойствами.

Два графа и называются изоморфными, если существует взаимооднозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих каждые две вершины в графе , равно числу ребер, соединяющих соответствующие вершины в графе . Распределение метокв графе G c n вершинами определяется как взаимооднозначное соответствие между множеством вершин графа и множеством {1, 2, …, n}. Помеченным графом называется пара , где - граф, - распределение меток.

Теорема Кэли.Существует ровно различных помеченных деревьев с вершинами.

Док-во.

Доказывается через следствие теоремы о биекции.

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

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны (кроме, может быть, ).

Теорема о свойствах деревьев.Пусть T – граф, который имеет n вершин, тогда следующие утверждения эквивалентны: 1. T является деревом; 2. T не содержит циклов и имеет n-1 ребро; 3. T связен и имеет n-1 ребро; 4. T связен и каждое его ребро является мостом; 5. Каждые 2 вершины графа T соединены ровно одной простой цепью; 6. T не содержит циклов, но, добавляя к нему любое новое ребро, мы получим ровно один цикл.

Доказательство:(1 2) Проведем индукцию по количеству ребер. Удаление любого ребра разбивает T на 2 графа, каждый из которых является деревом. Поэтому по индуктивному предположению число ребер в них меньше на 1, чем число вершин.

+ = - вершины

+ + 1 = - ребра

(2 3) Покажем, что граф связен. От противного.

Пусть граф T не связен, но каждая его компонента представляет связный граф без циклов. Из предыдущего доказательства: в каждой компоненте число вершин больше числа ребер на 1. Значит полное число вершин T больше полного числа ребер по крайней мере на 2. Это противоречит тому, что T имеет n-1 ребро.

(3 4) Видим, что удаление любого ребра приводит к графу с n вершинами и n-2 ребрами, который не может быть связен в силу слудующей теоремы.

Теорема.Если G можно представить , где - связные, , тогда - компонента связности, граф имеет k компонент связности. Пусть G имеет n вершин, m ребер и k компонент связности, G –простой, тогда выполняется неравенство:

Таким образом, получаем: .

Противоречие.

(4 5) Простая цепь – все вершины различны. Т.к. граф связен, то каждая пара его вершин соединена по крайней мере одной простой цепью (по определению связности).

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

Если же данная пара вершин соединена двумя простыми цепями, то они замыкаются в цикл, а это противоречит тому, что каждое ребро в графе является мостом.

(5 6) От противного. Пусть T сожержит цикл, тогда каждые две вершины этого цикла соединены по крайней мере двумя простыми цепями.

Добавим к графу T ребро e, тогда получим цикл, поскольку инцедентные ребру e вершины уже соединены простой цепью. Мы получим только один цикл.

(6 1) От противного. Пусть T несвязен, тогда добавление любого ребра, соединяющего одну вершину одной компоненты связности с вершиной другой компоненты, не приводит к образованию цикла, что противоречит пункту 6.

Следствие.

Пусть G – лес с n вершинами и k компонентами связности, тогда G имеет n-k ребер.