Декомпозиция дерева (теория графов)Васина Википедия

Новости с планеты OGLE-2018-BLG-0677
Что вы не только не знали, но и не хотели знать
Ответить Пред. темаСлед. тема
Автор темы
wiki_de
Всего сообщений: 42916
Зарегистрирован: 13.01.2023
 Декомпозиция дерева (теория графов)

Сообщение wiki_de »

В теории графов «разложение дерева» — это отображение графа (теория графов)|графа в дерево (теория графов)|дерево, которое можно использовать для определения ширины дерева графа и вычисления определенные проблемы ускорились до Грпаэна.

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

== Формальное определение ==
«Древовидное разложение» G = (V,E) представляет собой пару (X,T), где T = (I,F)< / math> — дерево, а X = \{X_i~|~i \in I\ — семейство (математика)|семейство подмножеств узлов (теория графов)|множество узлов V графика, так что:

* \bigcup_{i \in I} X_i = V.
* Для всех ребер (теория графов)|ребер (v,w) \in E существует i \in I с v,w \in X_i< /математика>.
* Для всех i,j,k \in I применяется следующее: если j находится на пути от i до k< /math> в T, затем X_i \cap X_k \subseteq X_j.

== Литература ==

* * *

Категория:Основные понятия (теория графов)
Категория:Деревья и леса
Категория:Теория графов

Подробнее: https://de.wikipedia.org/wiki/Baumzerle ... entheorie)
Реклама
Ответить Пред. темаСлед. тема

Быстрый ответ, комментарий, отзыв

Изменение регистра текста: 
Смайлики
:) :( :oops: :chelo: :roll: :wink: :muza: :sorry: :angel: :read: *x) :clever:
Ещё смайлики…
   
К этому ответу прикреплено по крайней мере одно вложение.

Если вы не хотите добавлять вложения, оставьте поля пустыми.

Максимально разрешённый размер вложения: 15 МБ.

  • Похожие темы
    Ответы
    Просмотры
    Последнее сообщение
  • Частичная декомпозиция информации
    wiki_en » » в форуме Васина Википедия
    0 Ответы
    28 Просмотры
    Последнее сообщение wiki_en
  • Из дерева
    wiki_de » » в форуме Васина Википедия
    0 Ответы
    39 Просмотры
    Последнее сообщение wiki_de
  • Мюллер у дерева
    wiki_de » » в форуме Васина Википедия
    0 Ответы
    39 Просмотры
    Последнее сообщение wiki_de
  • Цветок для дерева
    wiki_de » » в форуме Васина Википедия
    0 Ответы
    42 Просмотры
    Последнее сообщение wiki_de
  • Голубая яблочная дерева
    wiki_en » » в форуме Васина Википедия
    0 Ответы
    7 Просмотры
    Последнее сообщение wiki_en