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. An arborescence can equivalently be defined as a rooted digraph in which the path from the root to any other vertex is unique. The term arborescence comes from French. Some authors object to it on grounds that it is cumbersome to spell. There is a large number of synonyms for arborescence in graph theory, including directed rooted tree, out-arborescence, out-tree, and even branching being used to denote the same concept. Rooted tree itself has been defined by some authors as a directed graph. Furthermore, some authors define an arborescence to be a spanning directed tree of a given digraph. The same can be said about some of its synonyms, especially branching. Other authors use branching to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article, but a variation with both notions of the spanning flavor is also encountered. It's also possible to define a useful notion by reversing all the arcs of an arborescence, i.e. making them all point to the root rather than away from it. Such digraphs are also designated by a variety of terms, such as in-tree or anti-arborescence. W. T. Tutte distinguishes between the two cases by using the phrases arborescence diverging from [some root] and arborescence converging to [some root]. The number of rooted trees (or arborescences) with n nodes is given by the sequence: 0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... .

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 (3)

Related concepts (5)

Related courses (1)

Related lectures (9)

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

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

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Negar Kiyavash, Saber Salehkaleybar, Kun Zhang

A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equi ...

AAAI Press2019

A note on the data-driven capacity of P2P networks

Pascal Frossard

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met ...

2009

Connectivity in Graph Theory ME-427: Networked control systems

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

Covers self-similar groups and automorphisms of rooted trees, exploring residually finite groups and congruence subgroups.

Convolutional Codes & Viterbi Decoder EE-543: Advanced wireless receivers

Covers Convolutional Codes, Viterbi Algorithm, state and branch metric computations, and survivor path length limitations.

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.

Polytree

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.

Multitree

In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset).