HOME

TheInfoList



Click Here for Items Related To - List of graph theory topics
OR:
List of graph theory topics on:   [Wikipedia]   [Google]   [Amazon]

This is a list of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
topics, by Wikipedia page. See
glossary of graph theory 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 ** Leaf node **
Root 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 co ...
**
Root (graph theory) In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equiva ...


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 gen ...
*
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 spanning trees of a ...
*
Kőnig's lemma Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computab ...
* 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) In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of X such that every prefix of a sequence in the collection also belongs to the collection. Definitions Trees The collection of all finite sequences of ...
* Euler tour technique


Graph limits

* Graphon


Graphs in logic

* Conceptual graph *
Entitative graph An existential graph is a type of diagrammatic or visual notation for logical expressions, created by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914. They include ...
* Existential graph * ''
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 An existential graph is a type of diagrammatic or visual notation for logical expressions, created by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914. They include ...


Mazes and labyrinths

*
Labyrinth In Greek mythology, the Labyrinth () is 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 h ...
*
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 lead ...
* Maze generation algorithm


Algorithms

* Ant colony algorithm *
Breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...
*
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 al ...
*
Depth-limited search In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with incr ...
* FKT algorithm * 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 (discrete mathematics), graph is a set of Edge (graph theory), edges without common vertex (graph theory), vertices. In other words, a subse ...
* 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 two ...
**
Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
**
Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex (graph theory), vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more ...
** A* algorithm **
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 po ...
* Topological sorting ** 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 ...
*
Adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
** Adjacency algebra – the algebra of polynomials in the adjacency matrix * Canadian traveller problem *
Cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
and independent sets ** Clique problem * Connected component * Cycle space * de Bruijn sequences * Degree diameter problem * Entanglement (graph measure) * Erdős–Gyárfás conjecture * Eternal dominating set *
Extremal graph theory Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence loca ...
** Critical graph **
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 clique (graph theory), complete subgraph of a given size. It is one of the central results of extremal graph theory, an a ...
* Frequency partition *
Frucht's theorem Frucht's theorem is a result in algebraic graph theory, conjectured by Dénes Kőnig in 1936 and mathematical proof, proved by Robert Frucht in 1939. It states that every finite group is the automorphism group, group of symmetries of a finite undir ...
*
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 ...
* Graph homomorphism *
Graph labeling In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph , a vertex labeling is a function of to a set ...
**
Graceful labeling In graph theory, a graceful labeling of a Graph (discrete mathematics), graph with edges is a graph labeling, labeling of its Vertex (graph theory), vertices with some subset of the integers from 0 to inclusive, such that no two vertices share ...
*
Graph partition In mathematics, a graph partition is the reduction of a Graph (discrete mathematics), graph to a smaller graph by partition of a set, partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the g ...
* Graph pebbling * Graph property * Graph reduction * Graph-structured stack * 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). Whi ...
**
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). Whi ...
**
Markov random field In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph In discrete mathematics, particularly ...
*
Tree decomposition In graph theory, a tree decomposition is a mapping of a Graph (discrete mathematics), graph into a tree (graph theory), tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. ...
( Junction tree) and
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...
* Graph triangulation (see also Chordal graph) * Perfect order *
Hidden Markov model A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or ''hidden'') Markov process (referred to as X). An HMM requires that there be an observable process Y whose outcomes depend on the outcomes of X ...
** Baum–Welch algorithm ** Viterbi algorithm *
Incidence matrix In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
* Independent set problem *
Knowledge representation Knowledge representation (KR) aims to model information in a structured manner to formally represent it as knowledge in knowledge-based systems whereas knowledge representation and reasoning (KRR, KR&R, or KR²) also aims to understand, reason, and ...
** Conceptual graph ** 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 * Reconstruction conjecture *
Scientific classification image:Hierarchical clustering diagram.png, 280px, Generalized scheme of taxonomy Taxonomy is a practice and science concerned with classification or categorization. Typically, there are two parts to it: the development of an underlying scheme o ...
**
Cladistics Cladistics ( ; from Ancient Greek 'branch') is an approach to Taxonomy (biology), biological classification in which organisms are categorized in groups ("clades") based on hypotheses of most recent common ancestry. The evidence for hypothesiz ...
** Neighbor-joining **
Phenetics In biology, phenetics (; ), also known as taximetrics, is an attempt to classify organisms based on overall similarity, usually with respect to morphology or other observable traits, regardless of their phylogeny or evolutionary relation. It is ...
* Turán number * Shannon switching game *
Spectral graph theory In mathematics, spectral graph theory is the study of the properties of a Graph (discrete mathematics), graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacen ...
* Spring-based algorithm *
Strongly connected component In the mathematics, mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachability, reachable from every other vertex. The strongly connected components of a directed graph form a partition of a s ...
* Vertex cover problem


Networks,

network theory In mathematics, computer science, and network science, network theory is a part of graph theory. It defines networks as Graph (discrete mathematics), graphs where the vertices or edges possess attributes. Network theory analyses these networks ...

''See
list of network theory topics Network theory is an area of applied mathematics. This page is a list of network theory topics. Network theorems * Max flow min cut theorem * Menger's theorem * Metcalfe's law Network properties * Centrality * Betweenness centrality * Closen ...
''


Hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
s

*
Helly family In combinatorics, a Helly family of order is a family of Set (mathematics), sets in which every minimal ''subfamily with an empty Intersection (set theory), intersection'' has or fewer sets in it. Equivalently, every finite subfamily such that ...
* Intersection (Line) Graphs of hypergraphs
Graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
*
Graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
Graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...