Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математике, и в частности в теории графов, полидерево (также называемое направленным деревом, ориентированным деревом или односвязной сетью) — это ориентированный ациклический граф, неориентированный граф-основа которого является деревом. Иными словами, если заменить его ориентированные рёбра неориентированными, получится неориентированный граф, который одновременно связен и ацикличен. Полилес (или направленный лес, ориентированный лес) — это ориентированный ациклический граф, неориентированный граф-основа которого является лесом. Иными словами, если заменить его ориентированные рёбра неориентированными, получится неориентированный граф, который ацикличен. Полидерево является примером ориентированного графа. Термин «полидерево» был введен в 1987 году Ребаном и Перлом.
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree or singly connected network) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic. A polytree is an example of an oriented graph. The term polytree was coined in 1987 by Rebane and Pearl.
Связанные структуры
Арборесценция — это направленное корневое дерево, то есть направленный ациклический граф, в котором существует единственный корневой узел, из которого к каждому другому узлу существует единственный путь. Каждая арборесценция является полидеревом, но не каждое полидерево — арборесценция. Мультидерево — это направленный ациклический граф, в котором подграф, достижимый из любого узла, образует дерево. Каждое полидерево является мультидеревом. Отношение достижимости между узлами полидерева образует частичный порядок, размерность которого не превышает трех. Если размерность порядка равна трем, то должно существовать подмножество из семи элементов , , и (для ) такое, что для каждого , либо , либо , при этом эти шесть неравенств определяют структуру полидерева на этих семи элементах. Забор или зигзагообразный частично упорядоченный набор — это частный случай полидерева, в котором лежащее в основе дерево является путем, а ребра имеют чередующуюся ориентацию вдоль этого пути. Отношение достижимости в полидереве также называют обобщенным забором.
An arborescence is a directed rooted tree, i. e. a directed acyclic graph in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence. A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree. The reachability relationship among the nodes of a polytree forms a partial order that has order dimension at most three. If the order dimension is three, there must exist a subset of seven elements , , and (for ) such that, for each , either or , with these six inequalities defining the polytree structure on these seven elements. A fence or zigzag poset is a special case of a polytree in which the underlying tree is a path and the edges have orientations that alternate along the path. The reachability ordering in a polytree has also been called a generalized fence.
Гипотеза Самнера
Предположение Самнера, названное в честь Дэвида Самнера, утверждает, что турниры являются универсальными графами для полидерев, в том смысле, что любой турнир с *n* вершинами содержит каждое полидерево с *n* вершинами в качестве подграфа. Хотя оно остается нерешенным, оно было доказано для всех достаточно больших значений *n*.
Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with vertices contains every polytree with vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of .
Приложения
Полидеревья использовались как графическая модель для вероятностного вывода. Если байесовская сеть имеет структуру полидерева, то для эффективного выполнения вывода на ней можно использовать алгоритм распространения убеждений. Контурное дерево функции вещественного значения на векторном пространстве является полидеревом, описывающим уровни этой функции. Узлами контурного дерева являются уровни, проходящие через критическую точку функции, а рёбра описывают смежные уровни, не содержащие критических точек. Ориентация ребра определяется сравнением значений функции на соответствующих уровнях.
Polytrees have been used as a graphical model for probabilistic reasoning. If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it. The contour tree of a real valued function on a vector space is a polytree that describes the level sets of the function. The nodes of the contour tree are the level sets that pass through a critical point of the function and the edges describe contiguous sets of level sets without a critical point. The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.