рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Упорядоченные и бинарные деревья

Упорядоченные и бинарные деревья - раздел Математика, Остовы графов Определим По Индукции Понятие Упорядоченного Дерева: 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... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Упорядоченные и бинарные деревья

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Остовы графов
Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являют

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

Фундаментальные циклы
Пусть G= неорграф, имеющий n вершин, m ребер и с компонент связности, T-остов графа G. В §4.8 отмечалось, что T имеет v*(G)=n-c ребер u1, … , un-c, котор

Разрезы
Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью

Связанные с графами
  Рассмотрим алгебраическую систему 2= с двухместными операциями кольцевого сложения ⊕ и умножения ⊙, задаваемыми следующими правилами: 0⊕0=1⊕1=0, 1

Раскраски графов
Пусть G= неорграф без петель. Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если ребро, то вершины и имеют различные цвета. Хроматически

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

Задачи и упражнения
1. Представить граф ( рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.   2. Составить матрицу инцидентичности для мультиграфа, изображенного

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги