This is a list of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

topics, by Wikipedia page. See

glossary of graph theory terms This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

for basic terminology

Examples and types of graphs

Graph coloring

Paths and cycles

Trees

Terminology

Node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

** Child node **

Parent node In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...

** Leaf node ** Root node ** Root (graph theory)

Operations

Tree structure A tree structure, tree diagram, or tree model is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, although the chart is gener ...

Tree data structure In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...

Cayley's formula In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^. The formula equivalently counts the number of spanning trees ...

* Kőnig's lemma * Tree (set theory) (need not be a tree in the graph-theory sense, because there may not be a unique path between two vertices) * Tree (descriptive set theory) * Euler tour technique

Graph limits

Graphon GraphOn GO-Global is a multi-user remote access application for Windows. Overview GO-Global allows multiple users to concurrently run Microsoft Windows applications installed on a Windows server or server farm from network-connected loc ...

Graphs in logic

Conceptual graph A conceptual graph (CG) is a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa used them to represent the conceptual schemas used in database systems. The first book on CGs applied them to a wide range of ...

Entitative graph An entitative graph is an element of the diagrammatic syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic beginning in the 1880s, taking the coverage of the formalism only as far as the propositional or ...

Existential graph An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on logical graph, graphical logic as early as 1882,Peirce, C. S., "

n Junctures and Fractures in Logic N, or n, is the fourteenth letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''en'' (pronounced ), plural ''ens''. History ...

(ed ...

* ''

Laws of Form ''Laws of Form'' (hereinafter ''LoF'') is a book by G. Spencer-Brown, published in 1969, that straddles the boundary between mathematics and philosophy. ''LoF'' describes three distinct logical systems: * The "primary arithmetic" (described in Ch ...

'' *

Logical graph A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. In his papers on ''qualitative logic'', ''entitative graphs'', and ''existential graphs'' ...

Mazes and labyrinths

Labyrinth In Greek mythology, the Labyrinth (, ) was an elaborate, confusing structure designed and built by the legendary artificer Daedalus for King Minos of Crete at Knossos. Its function was to hold the Minotaur, the monster eventually killed by the ...

Maze A maze is a path or collection of paths, typically from an entrance to a goal. The word is used to refer both to branching tour puzzles through which the solver must find a route, and to simpler non-branching ("unicursal") patterns that lea ...

Maze generation algorithm Maze generation algorithms are automated methods for the creation of mazes. Graph theory based methods A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements ...

Algorithms

Ant colony algorithm In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi- ...

* Breadth-first search *

Depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...

* Depth-limited search *

FKT algorithm The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, co ...

* Flood fill *

Graph exploration algorithm In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal ...

Matching (graph theory) In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definit ...

Max flow min cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...

* Maximum-cardinality search * Shortest path ** Dijkstra's algorithm **

Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is ...

A* algorithm A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, ...

Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...

Topological sorting In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For ins ...

Pre-topological order In the field of computer science, a pre-topological order or pre-topological ordering of a directed graph is a linear ordering of its vertices such that if there is a directed path from vertex ''u'' to vertex ''v'' and ''v'' comes before ''u'' in t ...

Other topics

{{columns-list, colwidth=30em, *

Adjacency list In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is ...

Adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

Adjacency algebra In algebraic graph theory, the adjacency algebra of a graph ''G'' is the algebra of polynomials in the adjacency matrix ''A''(''G'') of the graph. It is an example of a matrix algebra and is the set of the linear combinations of powers of '' ...

– the algebra of polynomials in the adjacency matrix * Canadian traveller problem * Cliques and independent sets ** Clique problem * Connected component * Cycle space * de Bruijn sequences *

Degree diameter problem In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounded ...

Entanglement (graph measure) In graph theory, entanglement of a directed graph is a number measuring how strongly the cycles of the graph are intertwined. It is defined in terms of a mathematical game in which ''n'' cops try to capture a robber, who escapes along the edges of ...

Erdős–Gyárfás conjecture In graph theory, the unproven Erdős–Gyárfás conjecture, made in 1995 by the prolific mathematician Paul Erdős and his collaborator András Gyárfás, states that every graph with minimum degree 3 contains a simple cycle whose length is a pow ...

Eternal dominating set In graph theory, an eternal dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' of ''V'' such that ''D'' is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex ...

* Extremal graph theory **

Critical graph In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed ...

Turán's theorem In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...

Frequency partition In graph theory, a discipline within mathematics, the frequency partition of a graph ( simple graph) is a partition of its vertices grouped by their degree. For example, the degree sequence of the left-hand graph below is (3, 3, 3, 2, 2, 1) and it ...

* Frucht's theorem *

Girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

Graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

Graph homomorphism In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...

Graph labeling In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph , a vertex labelling is a function of to a set o ...

** Graceful labeling * Graph partition *

Graph pebbling Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, r ...

Graph property In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.. Definitions While graph drawing and ...

Graph reduction In computer science, graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as lazy evaluati ...

Graph-structured stack In computer science, a graph-structured stack (GSS) is a directed acyclic graph where each directed path represents a stack. The graph-structured stack is an essential part of Tomita's algorithm, where it replaces the usual stack of a pushdown au ...

* Graphical model **

Bayesian network A Bayesian network (also known as a Bayes network, Bayes net, belief network, or decision network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). Bay ...

D-separation A Bayesian network (also known as a Bayes network, Bayes net, belief network, or decision network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). Bay ...

** Markov random field *

Tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees ...

(

Junction tree In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees ...

) and treewidth *

Graph triangulation Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

(see also

Chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...

) * Perfect order *

Hidden Markov model A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...

Baum–Welch algorithm In electrical engineering, statistical computing and bioinformatics, the Baum–Welch algorithm is a special case of the expectation–maximization algorithm used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the f ...

** Viterbi algorithm * Incidence matrix *

Independent set problem In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

Knowledge representation Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...

** Mind map * Level structure * Link popularity *

Mac Lane's planarity criterion In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the c ...

Node influence metric In graph theory and network analysis, node influence metrics are measures that rank or quantify the influence of every node (also called vertex) within a graph. They are related to centrality indices. Applications include measuring the influence o ...

* Reconstruction conjecture * Scientific classification **

Cladistics Cladistics (; ) is an approach to biological classification in which organisms are categorized in groups (" clades") based on hypotheses of most recent common ancestry. The evidence for hypothesized relationships is typically shared derived char ...

** Neighbor-joining ** Phenetics *

Turán number In mathematics, the Turán number T(''n'',''k'',''r'') for ''r''-uniform hypergraphs of order ''n'' is the smallest number of ''r''-edges such that every induced subgraph on ''k'' vertices contains an edge. This number was determined for ''r''&nb ...

Shannon switching game The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory" some time before 1951. Two players take turns coloring the edges of an ...

Spectral graph theory In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix ...

Spring-based algorithm Force-directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically-pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of m ...

Strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...

* Vertex cover problem

Networks,
network theory Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be defi ...

''See list of network theory topics''

Hypergraphs

* Helly family *

Intersection (Line) Graphs of hypergraphs In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph , denoted , is the graph whose vertex set is the set of the hyperedges of , with two vertices adjacent in when their corresponding hyperedges have a nonem ...

Graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...