Тема 7. 7 деревья. Код пруфера.

 

Деревом называется всякий несвязный граф без циклов.

Граф, состоящий из изолированной вершины, тоже считается деревом.

Вершина дерева, степень которой равна 1, называется висячей.

Лесом называется граф представленный в виде объединения деревьев.

Теорема: Если у дерева n вершин, то ребер n-1.

Рассмотрим произвольное дерево с 11 вершинами, пронумерованными в произвольном порядке.

 

В результате возникает вопрос: сколько существует таких деревьев с 11 вершинами?

Английский математик Кэли нашел ответ на этот вопрос: деревьев с n вершинами можно создать столько, сколько существует последовательностей вида: , где и таких последовательностей будет n^n-2.

Немецкий математик Пруффер продолжил решать эту проблему и указал алгоритм, согласно которому любому дереву можно поставить во взаимно-однозначное соответствие – код.

Алгоритм:

1. выбираем висячую вершину с наименьшим номером.

2. удаляем ее вместе с принадлежащим ей ребром.

3. записываем номер вершины полученного дерева ближайшей к удаленной.

4. повторяем данные действия до тех пор пока не останется две висячие вершины, связанные между собой ребром.

 

1. вершина № 2

2. записываем вершину № 1

3. выбираем вершину № 3

4. записываем вершину № 1

и т.д., в результате получаем код: (1, 1, 5, 5, 6, 6, 6, 6, 5)

И наоборот, зная код можно изобразить дерево.

Алгоритм составления дерева по коду:

1. находим наименьшее натуральное число, которое не встречается в последовательности.

2. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.

3. находим следующее число

Дан код (1, 5, 5, 3, 6, 4).

Количество вершин = 8,

1. наименьшее число, не встречающееся в последовательности – 2

2. строим эту вершину и соединяем ребром с вершиной №1

3. аналогично перебираем все цифры не встречающиеся в последовательности до 8.

Тема 7.8 Понятие ориентированный граф (орграф).

 

Ребро <А,В> называется ориентированным, если одну вершину считают его началом, вторую концом

 

<А,В>

<В,А>

Граф называется ориентированным, если каждое его ребро ориентировано.

Степенью входа вершины А называется количество ребер входящих в А. Степенью выхода вершины А называется количество ребер выходящих из нее.

 

 

Рассмотрим

1. вершина А:

степень входа – 1, степень выхода – 1;

2. вершина С:

степень входа – 3, степень выхода – 0;

3. вершина D:

степень входа – 0, степень выхода – 2.

Стоком называется вершина, степень выхода которой равна 0, а степен7ь входа больше 0.

Источником называется вершина, степень выхода которой больше 0, а степень входа равна 0.

Изолированной вершиной называется вершина, у которой степень входа и степень выхода равны 0.

Путем от вершины А1 до вершины Аn называется такая последовательность ребер, ведущих от А1 до Аn <A1,A2><A2,A3>…<An-1,An>, что конец предыдущего ребра является началом следующего и ни одно ребро не встречается дважды.

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

 

S(A,B)=1

S(A,C)=2

S(C,A)=∞

Теорема: Если в графе m вершин, р – ребер, то степень входа А1+ степень входа А2+…+ степень входа Am = степень выхода А1+ степень выхода А2+…+ степень выхода Am = р