Реферат Курсовая Конспект
Упорядоченные и бинарные деревья - раздел Математика, Остовы графов Определим По Индукции Понятие Упорядоченного Дерева: 1) Пусто...
|
Определим по индукции понятие упорядоченного дерева:
1) пустое множество и список (a), где a-некоторый элемент, является упорядоченным деревом;
2) если T₁,T₂, … ,Tn-непустые упорядоченные деревья, a-некоторый новый элемент, то список T=(a, T₁,T₂, … ,Tn)есть упорядоченное дерево. При этом элемент aназывается корнем упорядоченного дерева T;
3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.
Если T₁,T₂, … ,Tn-упорядоченные деревья, то список (T₁,T₂, … ,Tn) называется упорядоченным лесом.
Для заданного упорядоченного дерева T определим множество S(T) его упорядоченных поддеревьев:
-если T= , то S(T)= ;
- если T=(a), то S(T)= ;
-если T=(a, T₁,T₂, … ,Tn), то S(T)= S(T1) … S(Tn) .
Непустое упорядоченное дерево T может интерпретироваться в виде системы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T) так, что:
1) если T̕-поддерево упорядоченного дерева T˝, T̕,T˝ S(T), то для соответствующих множеств X̕ и X˝ выполняется включение X̕ X˝;
2) если T̕ не является поддеревом упорядоченного дерева T˝ и T˝ не является поддеревом упорядоченного дерева T̕ (где T̕, T˝ S(T)), то соответствующие множества не пересекаются.
П р и м е р 4.10.1. Упорядоченному дереву
(1,(2,(4),(5)),(3,(6,(8),(9)),(7)))
соответствует система множеств ,изображенная на рис. 4.41.
– Конец работы –
Эта тема принадлежит разделу:
тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Упорядоченные и бинарные деревья
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов