Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Компоненты связанности графа. Понятие дерева и остовного дерева.

Читайте также:
  1. I. ПОНЯТИЕ И ФУНКЦИИ КОНФЛИКТА
  2. III тон сердца. Понятие о ритме галопа. Диагностическое значение.
  3. А) Понятие государственности
  4. Административная ответственность: понятие, сущность, цели
  5. Аудит как вид финансового контроля: понятие, отличительные черты, виды, правовое регулирование.
  6. Большое спасибо, но у меня аллергия на некоторые компоненты».
  7. Бюджетное право как подотрасль финансового права: понятие, предмет, метод, система.

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

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

Подграф G 1 = (V 1, E 1) графа G = (V, E), называется остовным деревом в

графе G = (V, E), если G 1 = (V 1, E 1) — дерево и V 1 = V.

Ориентированное (направленное) дерево — ацикличный орграф (%84"ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.)"[2]

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

• существует один корень дерева T

• остальные узлы (за исключением корня) распределены среди непересекающихся множеств T 1,..., Tm, и каждое из множеств является деревом; деревья T 1,..., Tm называются поддеревьями данного корня T

Число различных деревьев, которые можно построить на n нумерованных вершинах, равно

nn − 2 (Теорема %80"КэлиHYPERLINK "http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)"[3]).

Производящая функция

для числа Tn неизоморфных корневых деревьев с n вершинами удовлетворяет функциональному уравнению

.

Производящая функция

для числа tn неизоморфных деревьев с n вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

При верна следующая асимптотика

tnC α n / n 5 / 2

где C и α определённые константы, C = 0,534948..., α = 2,95576....

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m — число рёбер дерева, то через 2 m шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код дерева) длины 2 m позволяет однозначно восстанавливать не только само дерево D, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n вершинами:

 


Дата добавления: 2015-09-06; просмотров: 125 | Нарушение авторских прав


Читайте в этой же книге: Понятие сети и потока в ней. Сечение (разрез) минимальное сечение(разрез) его пропускная способность. | Изложить алгоритм Форда – Фалкерсона. | Сформулировать и доказать теорему форда-фалкерсона | Алгебры |
<== предыдущая страница | следующая страница ==>
Компоненты связанности графа. Понятие дерева и остовного дерева.| Задача о Кёнинсбергских мостах.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)