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 Graph Search.
Concept
Orientation (graph theory)
Summary
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. Sumner's conjecture states that every tournament with 2n – 2 vertices contains every polytree with n vertices.
The number of non-isomorphic oriented graphs with n vertices (for n = 1, 2, 3, ...) is
1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, ... .
Tournaments are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are bijective. Therefore, the same sequence of numbers also solves the graph enumeration problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.
A strong orientation is an orientation that results in a strongly connected graph. The closely related totally cyclic orientations are orientations in which every edge belongs to at least one simple cycle. An orientation of an undirected graph G is totally cyclic if and only if it is a strong orientation of every connected component of G. Robbins' theorem states that a graph has a strong orientation if and only if it is 2-edge-connected; disconnected graphs may have totally cyclic orientations, but only if they have no bridges.
An acyclic orientation is an orientation that results in a directed acyclic graph.
Official source
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.