|
This is a list of graph theory topics, by Wikipedia page. A labeled graph with 6 vertices and 7 edges. ...
See glossary of graph theory for basic terminology Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...
[edit]
Examples and types of graphs
See also Trees [edit] In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets and such that no edge has both end-points in the same set. ...
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...
An (N, M, D, K, e)-disperser is a bipartite graph with N nodes on the left side, each with degree D, and M nodes on the right side, such that every subset of K nodes on the left side is connected to more than (1 − e) fraction of...
In combinatorics, an expander graph refers to a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. ...
Mathematics An (N,M,D,K,e)-extractor is a bipartite graph with N nodes on the left and M nodes on the right such that each node on the left has D neighbors (on the right), which has the added property that for any subset A of N of...
The Cayley graph of the free group on two generators a and b In mathematics, a Cayley graph, named after Arthur Cayley, is a graph that encodes the structure of a group. ...
In graph theory the complement or inverse of a graph is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in . ...
In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...
In the mathematical field of graph theory, a cubic graph is a graph where all vertices have degree 3. ...
A Dense graph is a graph in which the number of edges is close to the possible number of edges. ...
In graph theory, a dipole graph (or dipole) is a multigraph consisting of two vertices connected with a number of edges. ...
This article just presents the basic definitions. ...
A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...
In graph theory, an interval graph is a graph that captures the intersections among a set of intervals on the real line. ...
In graph theory, the line graph L(G) of a graph G is a graph such that each node of L(G) represents an edge of G; and any two nodes of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common...
In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ...
In graph theory, the Robertson–Seymour theorem states that the minor ordering on the finite undirected graphs is a well-quasi-ordering. ...
The Petersen graph Another drawing of the Petersen graph, with only two crossings Another drawing, with each edge the same length The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. ...
In graph theory, a planar graph is a graph that can be drawn (mathematicians say can be embedded in the plane) so that no edges intersect. ...
In geometry, polyhedra are associated into pairs called duals, where the vertices of one correspond to the faces of the other. ...
In mathematics, a random graph is a graph that is generated by some random process. ...
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...
A scale-free network is a specific kind of complex network that has attracted attention since many real-world networks fall into this category. ...
In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...
A Sparse graph code is a code which is represented by a sparse graph. ...
The Turan graph T(n,r) is the complete r-partite graph with n vertices whose partite sets differ in size at most 1. ...
In mathematics, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is some automorphism f : G → G such that f ( e1 ) = e2. ...
In mathematics, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism f : G → G such that f ( v1 ) = v2. ...
A visibility graph is a graph of intervisible locations. ...
A visibility graph is a graph of intervisible locations. ...
In the mathematical discipline of graph theory a wheel graph is a special graph which can be visualized as a wheel. ...
[edit] A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...
In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. ...
In the mathematical field of graph theory the chromatic polynomial for a given graph is a polynomial which encodes the number of different ways to vertex color the graph using n colors. ...
In graph theory, a cocoloring of a graph G is an assignment of colors to the vertices such that each color class forms an independent set in G or the complement of G. The cochromatic number z(G) of G is the least number of colors needed in any cocolorings...
In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. ...
In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. ...
In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. ...
Example of a four color map Example of a map with non-contiguous regions The four color theorem states that given any plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than four colors in such...
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. ...
A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...
In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. ...
In graph theory, list coloring is a type of graph coloring. ...
In mathematics, list edge-coloring is a type of graph coloring. ...
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ...
In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ...
In combinatorial mathematics, Sperners lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors. ...
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every partition. ...
In graph theory, a subcoloring is an assignment of colors to a graphs vertex such that each color class induces a vertex disjoint union of cliques. ...
Taits conjecture states that Every polyhedron has a Hamiltonian cycle (along the edges) through all its vertices. It was proposed in 1886 by P. G. Tait and disproved in 1946, when W. T. Tutte constructed a counterexample with 25 faces, 69 edges and 46 vertices. ...
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph. ...
In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. ...
Paths and cycles [edit] In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...
Map of Königsberg in Eulers time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges. ...
The Königsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ...
The three cottage problem is a problem in mathematical graph theory: Suppose there are three cottages that each need to be connected to the gas, water, and electric companies. ...
In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...
Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...
The Open Shortest Path First (OSPF) protocol is a link-state, hierarchical interior gateway protocol (IGP) for network routing. ...
A flooding algorithm is an algorithm for distributing material to every part of a connected network. ...
Route inspection problem, Chinese postman problem: The Chinese postman problem is to find a shortest closed path (circuit) that goes through all edges of a (connected) undirected graph. ...
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ...
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ...
A knights tour of a chessboard The Knights Tour is a mathematical problem involving a knight on a chessboard. ...
The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the traveling salesman problem, and usually comes to within twenty percent of the optimal route. ...
The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. ...
In project management, path analysis (also known as critical path analysis) is a technique to analyse events. ...
Trees - Tree
- Terminology
- Operations
- Other
[edit] A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
In computer science, an abstract syntax tree (AST) is a finite, labeled, directed tree, where the internal nodes are labeled by operators, and the leaf nodes represent the operands of the node operators. ...
B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ...
In computer science, a binary tree is a tree data structure in which each node has at most two children. ...
A binary search tree of size 9 and depth 3, with root 7 and leaves 1, 4, 7 and 13. ...
In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ...
An example of a non-AVL tree In computer science, an AVL tree is the first-invented self-balancing binary search tree. ...
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. ...
A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. ...
Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. ...
In computer science, a binary tree is an ordered tree data structure in which each node has at most two children. ...
A B*-tree is a tree data structure, a variety of B-tree that is efficient for searching at the cost of a more expensive insertion. ...
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. ...
Binary heaps are a particularly simple kind of heap data structure created using a binary tree. ...
In computer science, a binomial heap is a data structure similar to binary heap but also supporting the operation of merging two heaps quickly. ...
In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ...
A 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. ...
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
The null graph or the empty graph is the graph with no points and no lines. ...
The evolutionary tree of living things is currently supposed to run something along the lines of that listed below. ...
An exponential tree is almost identical to a [binary search tree], with the exception that the dimension of the tree is not the same at all levels. ...
Example of family tree A family tree is generally the totality of ones ancestors, or more specifically, a chart used in genealogy to show the family connections between individuals, consisting of the individuals names (usually accompanied by dates, and often also places and occupations) connected by various types of...
Safety engineering is used to assure that a life-critical system behaves as needed even when pieces fail. ...
In graph theory, a free tree is a tree that is not rooted. ...
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. ...
In graph theory, a k-ary tree is a tree in which each node has no more than k children. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
A parse tree is a tree that represents the syntactic structure of a string according to some formal grammar. ...
It has been suggested that Evolutionary tree be merged into this article or section. ...
A PQ tree is a special kind of tree data structure. ...
This article is about an R-tree data structure. ...
A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
Suffix tree for the string BANANA padded with $. Suffix links drawn dashed. ...
This page is a candidate for speedy deletion, because: it is patent nonsense. ...
A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are strings. ...
In computer science, a Patricia trie (also known as a radix tree) is a simple form of compressed trie which merges single child nodes with their parents. ...
A spanning tree (red) of a graph (black), superimposed In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree which includes every vertex of that graph. ...
The minimum spanning tree of a planar graph. ...
Borůvkas algorithm is an algorithm for finding minimum spanning trees. ...
Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...
Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...
The Steiner tree problem is a problem in combinatorial optimization. ...
The Quadtree is a tree data structure in which each internal node has up to four children. ...
This article just presents the basic definitions. ...
A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ...
A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ...
In computer science, a leaf node is a node of a tree data structure that has zero child nodes. ...
A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ...
Root or root can mean: superuser root directory, the base of a filesystems directory structure in a tree data type, the node in the tree which has no parent node This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same...
Please also consider changing this to a more descriptive stub notice. ...
In computer science, tree traversal is the process of visiting each node in a tree data structure. ...
In computer science, tree traversal is the process of visiting each node in a tree data structure. ...
In computer science, tree traversal is the process of visiting each node in a tree data structure. ...
In computer science, tree traversal is the process of visiting each node in a tree data structure. ...
In computer science, tree traversal is the process of visiting each node in a tree data structure. ...
An Ahnentafel (or Ahnenreihe), also known as the Sosa-Stradonitz System, is a list of a persons ancestors in a particular order. ...
Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ...
The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ...
Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ...
In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, tree structure, or graph. ...
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
Iterative deepening depth-first search is a states-space search strategy, that visits each node in the search tree in the same order as depth-first search but does so by gradually increasing the maximum depth limit of the search iteratively. ...
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ...
In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...
In mathematics, Cayleys formula is a result in graph theory. ...
Königs lemma or Königs infinity lemma is a theorem in graph theory due to Denes König that states the following. ...
A MUD tree or multi-user dungeon tree is a hierarchical display of derived code from source code packages. ...
In set theory, a tree is a partially ordered set (poset) (T, <) such that for each t ε T, the set {s ε T : s < t} is well-ordered by the relation <. For each t ε T, the order type of {s ε T : s < t} is called the idxheight, or height of t...
In descriptive set theory, a tree on a set is a set of finite sequences of elements of that is closed under subsequences. ...
Graphs in logic [edit] John F. Sowas Conceptual Graphs allow the graphical statement of logic propositions, or predicates. ...
An entitative graph is an element of the graphical syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic in the 1880s, taking the coverage of the formalism only as far as the propositional or sentential aspects of logic are concerned. ...
An existential graph is a type of diagrammatic or visual notation for logical expressions, invented by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882 and continued to develop the method until his death in 1914. ...
The phrase Laws of Form refers to either of two things: The book, hereinafter abbreviated LoF by G. Spencer-Brown. ...
A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ...
Mazes & Labyrinths [edit] A Roman mosaic showing Theseus and the Minotaur. ...
Public hedge maze in the English Garden at Schönbusch Park, Aschaffenburg, Germany A small maze. ...
There are a number of different maze generation algorithms, that is, automated methods for the creation of mazes. ...
[edit] Flowcharts are often used to graphically represent algorithms. ...
Flood fill, also called seed fill, is a recursive algorithm that determines connected regions in a multi-dimensional array. ...
In computer science a graph exploration algorithm specifies a possible way a graph can be traversed. ...
The ant colony optimization algorithm (ACO), introduced by Marco Dorigo in his doctoral thesis, is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ...
The max flow min cut theorem is a statement in optimization theory about maximal flows in flow networks. ...
In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, tree structure, or graph. ...
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. ...
In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...
Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...
The Bellman-Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ...
The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ...
In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshalls algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time. ...
In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes which is compatible with the partial order R induced on the nodes where x comes before y (xRy) if theres a directed path from x to y in the DAG...
Other topics [edit] In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n × n matrix where the nondiagonal entry aij is the number of edges joining vertex and vertex , and the diagonal entry aii is either twice the number of loops at vertex or just...
K5, a complete graph. ...
In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ...
In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. ...
In an undirected graph, a connected component or component is a maximal connected subgraph. ...
// The binary cycle space In graph theory, certain vector spaces over the two-element field Z2 are associated with an undirected graph; this allows one to use the tools of linear algebra to study graphs. ...
// Definition In combinatorics, a -ary de Bruijn sequence of order , , is a cyclic sequence from a given alphabet of size , for which every possible subsequence of length in is present exactly once. ...
In graph theory, the unproven Erdős-Gyárfás conjecture, made by the prolific mathematician Paul Erdős and a collaborator, claims that any graph with minimum degree 3 contains a cycle whose length is a power of 2. ...
Extremal graph theory is a branch of mathematics. ...
In general the notion of criticality can refer to any measure. ...
In graph theory, Turáns theorem is a result on the number of edges in a Ks+1-free graph. ...
Girth generally refers to the circumference of a cylindrical object, such as a tree trunk. ...
As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ...
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ...
In mathematics a graph invariant or graph property is one of the basic properties of graphs studied in graph theory. ...
In computing, graph reduction avoids duplicated computation of equivalent sub-expressions of an expression. ...
In computer science, a graph-structured stack is a directed acyclic graph where each directed path is a stack. ...
In probability theory and statistics, a graphical model (GM) represents dependencies among random variables by a graph in which each random variable is a node. ...
A Bayesian network or Bayesian belief network or just belief network is a form of probabilistic graphical model. ...
The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...
A Markov network, also called a Markov random field, is represented by: - an undirected graph , where each vertex represents a random variable and each edge represents a dependency between random variables and , - a set of potential functions , where each represents a clique in , and is the set of all possible...
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used for speed up solving problems on the original graph. ...
Junction trees are a concept from graph theory that play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. ...
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph. ...
State transitions in a hidden Markov model (example) x — hidden states y — observable outputs a — transition probabilities b — output probabilities A hidden Markov model (HMM) is a statistical model where the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine...
In computer science and statistical computing, the Baum-Welch algorithm is used to find the unknown parameters of a hidden Markov model (HMM). ...
The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ...
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. ...
In mathematics, the independent set problem (IS) is a question in graph theory and combinatorics, known to be an NP-complete problem. ...
Knowledge representation is a research and application domain in artificial intelligence, cognitive science, as well as in the knowledge management & knowledge engineering. ...
John F. Sowas Conceptual Graphs allow the graphical statement of logic propositions, or predicates. ...
A hand-drawn mind map A mind map (or mind-map) is a diagram used to represent words and ideas linked to and arranged radially around a central key word or idea. ...
In the mathematical subfield of graph theory a level structure of a graph is a special partition of the set of vertices. ...
Link popularity is a measure of the quantity and quality of other web sites that link to a specific site on the World Wide Web. ...
In graph theory, Mac Lanes planarity criterion is a characterisation of planar graphs in terms of their cycle spaces. ...
Informally, the reconstruction problem of graph theory is about the following. ...
Scientific classification or biological classification is how biologists group and categorize extinct and living species of organisms. ...
This cladogram shows the relationship among various insect groups. ...
In bioinformatics, neighbor-joining is a bottom-up clustering method used for the creation of phylogenetic trees. ...
In biology, phenetics, also known as numerical taxonomy, is an attempt to classify organisms based on overall similarity, usually in morphology or other observable traits, regardless of their phylogeny or evolutionary relation. ...
The Shannon switching game is an abstract strategy game for two players, invented by the father of information theory, Claude Shannon. ...
In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to four. ...
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. ...
The spring based algorithm is an algorithm for drawing graphs in an aesthetically pleasing way. ...
A directed graph is called strongly connected if for every pair of vertices u and v there is a path from u to v and a path from v to u. ...
In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karps 21 NP-complete problems. ...
See list of network theory topics Network theory or diktyology is a branch of applied mathematics and physics, with the same general subject matter as graph theory. ...
This is a list of network theory topics, by Wikipedia page. ...
[edit]
|
Feeds |
Contact