Позначені дерева. Кількість позначених дерев

У зв'язку з теоремою 3 виникає питання про число різних дерев, які можна одержати з даного зв'язного позначеного графа.

Визначення. Граф називається позначеним, якщо його вершини відрізняються одна від іншої якими-небудь позначками. Наприклад, номерами. На мал. 4.8 граф позначений, на мал. 4.9 – ні.

Визначення. Два позначених графи вважаються однаковими (не різними), якщо між ними існує ізоморфізм, що зберігає позначки їхніх вершин. Всі позначені дерева на мал. 4.25 різні, хоча дерева з номерами (1) – (12) ізоморфні між собою, і дерева
(13) – (16) ізоморфні між собою.

Рис. 4.25

Позначені графи на мал. 4.7 і мал. 4.8 однакові. Одна з перших постановок цього питання пов'язана з дослідженням хімічних структурних формул. Тут наведений один результат, що ставиться до цієї області.

Теорема 2. (Келі) Існує точно різних позначених дерев з позначених вершин (інакше: повний позначений граф має точно різних кістяків).

На мал. 4.25 показані 16 різних позначених дерев, що виходять при .

Доведення.Висновок з теореми Кірхгофа.