discrete_math1

7. Деревья, их свойства, кодирование деревьев, остовные деревья.

Определение. Связный граф без циклов называется деревом. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Свойство 1. Если две произвольные несмежные вершины дерева соединить ребром, то в нем возникнет простой цикл.

Свойство 2. В дереве любое ребро является мостом

Свойство 3. В дереве количество ребер на единицу меньше числа вершин.

Определение. Ребро дерева называется концевым ребром, если оно инцидентно концевой вершине (т.е. вершине степени 1).

Свойство 4. В любом n-вершинном дереве при существует не менее двух концевых вершин и не менее одного концевого ребра.

Свойство 5. В любом n-вершинном дереве при есть хотя бы одна неконцевая вершина.

Определение. Дерево с выделенной вершиной называется корневым деревом, а выделенная вершина – корнем дерева.

Построение кода основано на обходе дерева «в глубину», при котором каждое ребро проходится дважды: первый раз – в направлении от корня, второй раз – к корню. Каждое ребро кодируется двумя символами – 0 и 1. При этом ноль означает движение вдоль данного ребра от корня, а единица – к корню. В получающемся коде ноль и единица, соответствующие одному и тому же ребру, не обязательно стоят рядом.

Пример 1. Корнем дерева на рисунке является вершина . При его обходе «в глубину» из корня получаем последовательность вершин:v₇, v₅, v₄, v₁, v₄, v₂, v₄, v₃, v₄, v₅, v₇, v₆, v₇. Такой обход порождает код (000101011101). Заметим, что иному обходу этого же дерева v₇, v₆, v₇, v₅, v₄, v₁, v₄, v₂, v₄, v₃, v₄, v₅, v₇ соответствует другой код (010001010111).

рисунок

Определение. Остовным деревом связного графа называется дерево, получающееся из этого графа путем удаления некоторых ребер (все вершины графа при этом сохраняются).

Определение. Минимальное остовное дерево - остовное дерево минимально возможной длины. Для его построения существует алгоритм Краскала. Идея этого алгоритма состоит в том, что искомое остовное дерево «вырастает» из леса, отдельные деревья которого постепенно объединяются и на последнем шаге алгоритма объединяются в одну компоненту связности – остовное дерево. Схема алгоритма такова:

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

Содержание