Polytree | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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. The number of distinct polytrees on unlabeled nodes, for , is 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (5)

Related concepts (11)

Related lectures (4)

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

New York2023

Properties of Network Polynomials

Christina Fragouli, Javad Ebrahimi Boroojeni

It is well known that transfer polynomials play an important role in the network code design problem. In this paper we provide a graph theoretical description of the terms of such polynomials. We consider acyclic networks with arbitrary number of receivers ...

2012

Properties of Network Polynomials

Javad Ebrahimi Boroojeni

Ieee2012

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Orientation (graph theory)

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.

Arborescence (graph theory)

In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

Unlabeled Trees Estimation

Explores the estimation of unlabeled trees and their unique reconstruction from sequences.

Connectivity in Graph Theory ME-427: Networked control systems

Covers the fundamentals of connectivity in graph theory, including paths, cycles, and spanning trees.

Large N Expansion: Vector Models PHYS-739: Conformal Field theory and Gravity

Explores the Large N expansion in vector models, focusing on matrix models, gauge theories, and the Hooft coupling.