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 conn ...

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, line ...

** Child node ** Parent node ** 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 genera ...

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 c ...

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 tre ...

* 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 The Euler tour technique (ETT), named after Leonhard Euler, is a method in graph theory for representing trees. The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. The tree can then be represented a ...

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 l ...

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 ...

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 s ...

Existential graph An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on graphical logic as early as 1882,Peirce, C. S., " n Junctures and Fractures in Logic (editors' title for ...

* '' Laws of Form'' *

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 grap ...

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 ...

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 le ...

* Maze generation algorithm

Algorithms

* Ant colony algorithm * 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 a ...

* 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, c ...

* Flood fill * Graph exploration algorithm *

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. Definiti ...

* Max flow min cut theorem * Maximum-cardinality search *

Shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...

** 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 i ...

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 ...

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 ...

** Pre-topological order

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 bound ...

* Entanglement (graph measure) * Erdős–Gyárfás conjecture * Eternal dominating set * Extremal graph theory ** Critical graph ** Turán's theorem *

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 i ...

* 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 graphs arising from applications such as social network analysis, c ...

* Graph homomorphism * Graph labeling **

Graceful labeling In graph theory, a graceful labeling of a graph with edges is a labeling of its vertices with some subset of the integers from 0 to inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute diff ...

* Graph partition * Graph pebbling *

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 an ...

* Graph reduction *

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 ...

* 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). Ba ...

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). Ba ...

** Markov random field * Tree decomposition ( Junction tree) and treewidth * Graph triangulation (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 ...

) * 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 ...

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 ...

Viterbi algorithm The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especiall ...

* 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 * Node influence metric * Reconstruction conjecture *

Scientific classification Taxonomy is the practice and science of categorization or classification. A taxonomy (or taxonomical classification) is a scheme of classification, especially a hierarchical classification, in which things are organized into groups or types. ...

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 cha ...

** Neighbor-joining ** Phenetics * Turán number *

Shannon switching game The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical e ...

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 matri ...

* Spring-based algorithm *

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 ...

Vertex cover problem In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...

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 de ...

''See list of network theory topics''

Hypergraphs

* Helly family * Intersection (Line) Graphs of hypergraphs

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 conn ...