Examples and types of graphs

• Bipartite graph
  Bipartite graph
  In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
  
  
  • Complete bipartite graph
    Complete bipartite graph
    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.- Definition :...
    
    
  • Disperser
    Disperser
    A disperser is a one-sided extractor. Where an extractor requires that every event gets the same probability under the uniform distribution and the extracted distribution, only the latter is required for a disperser...
    
    
  • Expander
    Expander graph
    In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
    
    
  • Extractor
• Bivariegated graph
  Bivariegated graph
  In graph theory, a mathematical discipline which has applications in computer science, as well as in many other disciplines, a bivariegated graph is a graph whose vertex set can be partitioned into two equal parts such that each vertex is adjacent to exactly one vertex from the other set not...
  
  
• Cayley graph
  Cayley graph
  In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
  
  
• Circle graph
  Circle graph
  In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.-Algorithmic...
  
  
• Complement graph
  Complement graph
  In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
  
  
• Complete graph
  Complete graph
  In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
  
  
• Cubic graph
  Cubic graph
  In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
  
  
• De Bruijn graph
  De Bruijn graph
  In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...
  
  
• Dense graph
  Dense graph
  In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
  
  
• Dipole graph
  Dipole graph
  In graph theory, a dipole graph is a multigraph consisting of two vertices connected with a number of edges. A dipole graph containing n edges is called the order-n dipole graph, and is denoted by Dn. The order-n dipole graph is dual to the cycle graph Cn.-References:* Jonathan L. Gross and Jay...
  
  
• Directed graph
  Directed graph
  A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
  
  
• Directed acyclic graph
  Directed acyclic graph
  In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
  
  
• Interval graph
  Interval graph
  In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
  
  
• Line graph
  Line graph
  In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
  
  
• Minor graph
  Minor (graph theory)
  In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
  
  
  • Robertson–Seymour theorem
    Robertson–Seymour theorem
    In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
    
    
• Petersen graph
  Petersen graph
  In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
  
  
• Planar graph
  Planar graph
  In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
  
  
  • Dual polyhedron
    Dual polyhedron
    In geometry, polyhedra are associated into pairs called duals, where the vertices of one correspond to the faces of the other. The dual of the dual is the original polyhedron. The dual of a polyhedron with equivalent vertices is one with equivalent faces, and of one with equivalent edges is another...
    
    
  • Outerplanar graph
    Outerplanar graph
    In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
    
    
• Random graph
  Random graph
  In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
  
  
• Regular graph
  Regular graph
  In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
  
  
• Scale-free network
  Scale-free network
  A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
  
  
• Sparse graph
  • Sparse graph code
    Sparse graph code
    A Sparse graph code is a code which is represented by a sparse graph.Any linear code can be represented as a graph, where there are two sets of nodes - a set representing the transmitted bits and another set representing the constraints that the transmitted bits have to satisfy...
    
    
• String graph
  String graph
  In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the...
  
  
• Total graph
• Trellis (graph)
  Trellis (graph)
  A trellis is a graph of which the nodes are ordered into vertical slices and each node at each time is connected to at least one node at an earlier and at least one node at a later time. The earliest and latest times in the trellis have only one node.Trellises are used in encoders and decoders for...
  
  
• Turán graph
  Turán graph
  The Turán graph T is a graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets. The graph will have subsets of size \lceil n/r\rceil, and r- subsets of size \lfloor n/r\rfloor...
  
  
• Edge-transitive graph
  Edge-transitive graph
  In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
  
  
• Vertex-transitive graph
  Vertex-transitive graph
  In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
  
  
• Visibility graph
  Visibility graph
  In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them...
  
  
  • Museum guard problem
• Wheel graph
  Wheel graph
  In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...
  
  

Graph coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

• Acyclic coloring
  Acyclic coloring
  In graph theory, an acyclic coloring is a vertex coloring in which every 2-chromatic subgraph is acyclic.The acyclic chromatic number A of a graph G is the least number of colors needed in any acyclic coloring of G....
  
  
• Chromatic polynomial
  Chromatic polynomial
  The chromatic polynomial is a polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte...
  
  
• Cocoloring
  Cocoloring
  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 in the complement of G. The cochromatic number z of G is the least number of colors needed in any cocolorings of G...
  
  
• Complete coloring
  Complete coloring
  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. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper...
  
  
• Edge coloring
  Edge coloring
  In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
  
  
• Exact coloring
  Exact coloring
  In graph theory, an exact coloring is a vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. In essence, an exact coloring is a coloring that is both harmonious and complete. Graphs that admit exact colorings have been classified.- External links :* A...
  
  
• Four color theorem
  Four color theorem
  In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...
  
  
• Fractional coloring
  Fractional coloring
  Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned...
  
  
• Graph two-coloring
• Harmonious coloring
  Harmonious coloring
  In graph theory, a harmonious coloring is a vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices...
  
  
• List coloring
• List edge-coloring
• Perfect graph
  Perfect graph
  In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
  
  
• Ramsey's theorem
  Ramsey's theorem
  In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
  
  
• Sperner's lemma
  Sperner's lemma
  In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which follows from it. Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors...
  
  
• Strong coloring
  Strong coloring
  In graph theory, a strong coloring, with respect to a partition of the vertices into subsets of equal sizes, is a vertex coloring in which every color appears exactly once in every partition....
  
  
• Subcoloring
  Subcoloring
  In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques....
  
  
• Tait's conjecture
  Tait's conjecture
  In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
  
  
• Total coloring
  Total coloring
  In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
  
  
• Uniquely colorable graph
  Uniquely colorable graph
  In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible k-coloring up to permutation of the colors.-Examples:...
  
  

Paths and cycles

• Path (graph theory)
  Path (graph theory)
  In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
  
  
• Seven Bridges of Königsberg
  Seven Bridges of Königsberg
  The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....
  
  
  • Eulerian path
    Eulerian path
    In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is a Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of...
    
    
• Three-cottage problem
• Shortest path problem
  Shortest path problem
  In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
  
  
  • Dijkstra's algorithm
    Dijkstra's algorithm
    Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
    
    
    • Open shortest path first
      Open Shortest Path First
      Open Shortest Path First is an adaptive routing protocol for Internet Protocol networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system . It is defined as OSPF Version 2 in RFC 2328 for IPv4...
      
      
• Flooding algorithm
  Flooding algorithm
  A flooding algorithm is an algorithm for distributing material to every part of a connected network. The name derives from the concept of inundation by a flood....
  
  
• Route inspection problem
  Route inspection problem
  In graph theory, a branch of mathematics, the Chinese postman problem , postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a undirected graph. When the graph has an Eulerian circuit , that circuit is an optimal solution.Alan Goldman of...
  
  
• Hamiltonian path
  Hamiltonian path
  In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
  
  
  • Hamiltonian path problem
    Hamiltonian path problem
    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 . Both problems are NP-complete...
    
    
  • Knight's tour
    Knight's tour
    The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...
    
    
• Traveling salesman problem
  • Nearest neighbour algorithm
    Nearest neighbour algorithm
    The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. In it, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited...
    
    
  • Bottleneck traveling salesman problem
    Bottleneck traveling salesman problem
    The Bottleneck traveling salesman problem is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle....
    
    
• Path analysis
  Path analysis
  In statistics, path analysis is used to describe the directed dependencies among a set of variables. This includes models equivalent to any form of multiple regression analysis, factor analysis, canonical correlation analysis, discriminant analysis, as well as more general families of models in the...
  
  

Trees

• Tree
  Tree (graph theory)
  In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
  
  
  • Abstract syntax tree
    Abstract syntax tree
    In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
    
    
  • B-tree
    B-tree
    In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
    
    
  • Binary tree
    Binary tree
    In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
    
    
    • Binary search tree
      Binary search tree
      In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
      
      
      • Self-balancing binary search tree
        Self-balancing binary search tree
        In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
        
        
        • AVL tree
          AVL tree
          In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O time in both the average and worst...
          
          
        • Red-black tree
          Red-black tree
          A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
          
          
        • Splay tree
          Splay tree
          A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
          
          
        • T-tree
          T-tree
          In computer science a T-tree is a type of binary treedata structure that is used by main-memory databases, such asDatablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite....
          
          
    • Binary space partitioning
      Binary space partitioning
      In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
      
      
    • Full binary tree
  • B*-tree
  • Heap
    Heap (data structure)
    In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
    
    
    • Binary heap
      Binary heap
      A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:*The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one are fully filled, and, if the last level of...
      
      
    • Binomial heap
      Binomial heap
      In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure...
      
      
    • Fibonacci heap
      Fibonacci heap
      In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
      
      
    • 2-3 heap
      2-3 heap
      In computer science, a 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2-3 tree.Time costs for some common heap operations:...
      
      
  • Kd-tree
    Kd-tree
    In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
    
    
  • Cover tree
    Cover tree
    The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a nearest neighbor search...
    
    
  • Decision tree
    Decision tree
    A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
    
    
  • Empty tree
  • Evolutionary tree
  • Exponential tree
    Exponential tree
    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. In a normal binary search tree, each node has a dimension of 1, and has 2d children. In an exponential tree, the dimension equals the depth of the node,...
    
    
  • Family tree
    Family tree
    A family tree, or pedigree chart, is a chart representing family relationships in a conventional tree structure. The more detailed family trees used in medicine, genealogy, and social work are known as genograms.-Family tree representations:...
    
    
  • Fault tree
  • Free tree
  • Game tree
    Game tree
    In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
    
    
  • K-ary tree
    K-ary tree
    In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree.A binary tree is the special case where k=2....
    
    
  • Octree
    Octree
    An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
    
    
  • Parse tree
    Parse tree
    A concrete syntax tree or parse tree or parsing treeis an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the...
    
    
  • Phylogenetic tree
    Phylogenetic tree
    A phylogenetic tree or evolutionary tree is a branching diagram or "tree" showing the inferred evolutionary relationships among various biological species or other entities based upon similarities and differences in their physical and/or genetic characteristics...
    
    
  • Polytree
    Polytree
    In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either...
    
    
  • Positional tree
  • PQ tree
    PQ tree
    A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is...
    
    
  • R-tree
    R-tree
    R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
    
    
  • Rooted tree
    • Ordered tree
    • Recursive tree
  • SPQR tree
  • Suffix tree
    Suffix tree
    In computer science, a suffix tree is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.The suffix tree for a string S is a tree whose edges are labeled with strings, such that each suffix...
    
    
  • Technology tree
  • Trie
    Trie
    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 usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...
    
    
    • Patricia trie
  • Spanning tree
    Spanning tree (mathematics)
    In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
    
    
    • Minimum spanning tree
      Minimum spanning tree
      Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
      
      
      • Boruvka's algorithm
        Boruvka's algorithm
        Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia....
        
        
      • Kruskal's algorithm
        Kruskal's algorithm
        Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
        
        
      • Prim's algorithm
        Prim's algorithm
        In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
        
        
  • Steiner tree
    Steiner tree
    The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
    
    
  • Quadtree
    Quadtree
    A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
    
    
• Terminology
  • Node
    • Child node
    • Parent node
    • Leaf node
    • Root node
    • Root (graph theory)
• Operations
  • Tree rotation
    Tree rotation
    A tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down...
    
    
  • Tree traversal
    Tree traversal
    In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
    
    
    • Inorder traversal
    • Backward inorder traversal
    • Pre-order traversal
    • Post-order traversal
    • Ahnentafel
      Ahnentafel
      An ahnentafel or ahnenreihe is a genealogical numbering system for listing a person's direct ancestors in a fixed sequence of ascent...
      
      
  • Tree search algorithm
  • A-star search algorithm
  • Best-first search
    Best-first search
    Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function f which, in general, may depend on the description...
    
    
  • Breadth-first search
    Breadth-first search
    In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
    
    
  • Depth-first search
    Depth-first search
    Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
    
    
    • Iterative deepening depth-first search
      Iterative deepening depth-first search
      Iterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...
      
      
• Other
  • Tree structure
    Tree structure
    A tree structure 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, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...
    
    
  • Tree data structure
  • Cayley's formula
  • König's lemma
    König's lemma
    König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig . It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic,...
    
    
  • MUD trees
    MUD trees
    The MUD trees below depict hierarchies of derivation among MUD codebases. Solid lines between boxes indicate code relationships, while dotted lines indicate conceptual relationships...
    
    
  • Tree (set theory)
    Tree (set theory)
    In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...
    
     (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
    Euler tour technique
    The Euler tour technique , 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 as a Eulerian circuit of the directed graph, known as the...
    
    

Graphs in logic

• Conceptual graph
  Conceptual graph
  Conceptual graphs are 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...
  
  
• Entitative graph
  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 1880's, taking the coverage of the formalism only as far as the propositional or sentential aspects of logic are concerned...
  
  
• Existential graph
  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, and continued to develop the method until his death in 1914.-The graphs:...
  
  
• Laws of Form
  Laws of Form
  Laws of Form is a book by G. Spencer-Brown, published in 1969, that straddles the boundary between mathematics and philosophy...
  
  
• Logical graph
  Logical graph
  A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....
  
  

Algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s

• Flood fill
  Flood fill
  Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining...
  
  
• Graph exploration algorithm
• Ant colony algorithm
• Max flow min cut theorem
• Breadth-first search
  Breadth-first search
  In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
  
  
• Depth-first search
  Depth-first search
  Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
  
  
• Depth-limited search
  Depth-limited search
  In computer science depth-limited search is an algorithm to explore the vertices of a graph. It is a modification of depth-first search and is used for example in the iterative deepening depth-first search algorithm.- General :...
  
  
• FKT algorithm
  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. Counting the number of matchings, even for planar graphs, is also #P-complete...
  
  
• Shortest path
  Shortest path problem
  In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
  
  
  • Dijkstra's algorithm
    Dijkstra's algorithm
    Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
    
    
  • Bellman–Ford algorithm
  • A* algorithm
  • Floyd–Warshall algorithm
• Topological sorting
  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 edge uv, u comes before v in the ordering...
  
  
• Maximum-cardinality search

Other topics

• Adjacency list
  Adjacency list
  In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...
  
  
• Adjacency matrix
  Adjacency matrix
  In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
  
  
  • Adjacency algebra
    Adjacency algebra
    In algebraic graph theory, the adjacency algebra of a graph G is the algebra of polynomials in the adjacency matrix A of the graph...
    
     – the algebra of polynomials in the adjacency matrix
• Canadian traveller problem
  Canadian traveller problem
  In computer science and graph theory, the Canadian Traveller Problem is a generalization of the shortest path problem to graphs that are partially observable...
  
  
• Cliques
  Clique (graph theory)
  In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
  
   and independent set
  Independent set (graph theory)
  In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
  
  s
  • Clique problem
    Clique problem
    In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
    
    
• Connected component
  Connected component (graph theory)
  In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
  
  
• Cycle space
  Cycle space
  In graph theory, an area of mathematics, a cycle space is a vector space defined from an undirected graph; elements of the cycle space represent formal combinations of cycles in the graph....
  
  
• de Bruijn sequences
• Degree diameter problem
• Entanglement (graph measure)
  Entanglement (graph measure)
  In graph theory, entanglement of a directed graph is a number measuring how stronglythe cycles of the graph are intertwined. It is defined in terms of a mathematical game in which...
  
  
• Erdős–Gyárfás conjecture
  Erdos–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 any graph with minimum degree 3 contains a simple cycle whose length is a power of two...
  
  
• Extremal graph theory
  Extremal graph theory
  Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...
  
  
  • Critical graph
    Critical graph
    In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph....
    
    
  • Turán's theorem
    Turán's theorem
    In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.An n-vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly-equal size, and connecting two vertices by an edge whenever they...
    
    
• Frequency partition
  Frequency partition
  In graph theory, a discipline within mathematics, the frequency partition of a graph is a partition of its vertices grouped by their degree.For example, the degree sequence of the left-hand graph below is and its frequency partition is 6 = 3 + 2 + 1...
  
  
• Frucht's theorem
  Frucht's theorem
  Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph...
  
  
• Girth
  Girth
  In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles , its girth is defined to be infinity....
  
  
• Graph drawing
  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, cartography, and bioinformatics...
  
  
• Graph homomorphism
  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 maps adjacent vertices to adjacent vertices.-Definitions:...
  
  
• Graph labeling
  Graph labeling
  In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edges or vertices, or both, of a graph....
  
  
  • Graceful labeling
    Graceful labeling
    In graph theory, a graceful labeling of a graph with e edges is a labeling of its vertices with distinct integers between 0 and e inclusive, such that each edge is uniquely identified by the positive, or absolute difference between its endpoints. A graph which admits a graceful labeling is called a...
    
    
• Graph partition
  Graph partition
  In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
  
  
• Graph pebbling
  Graph pebbling
  Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an adjacent vertex...
  
  
• Graph property
  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:...
  
  
• Graph reduction
  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 evaluation and used in functional programming languages...
  
  
• Graph-structured stack
  Graph-structured stack
  In computer science, a graph-structured stack 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 automaton...
  
  
• Graphical model
  Graphical model
  A graphical model is a probabilistic model for which a graph denotes the conditional independence structure between random variables. They are commonly used in probability theory, statistics—particularly Bayesian statistics—and machine learning....
  
  
  • Bayesian network
    Bayesian network
    A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph . For example, a Bayesian network could represent the probabilistic...
    
    
  • D-separation
  • Markov random field
• Tree decomposition
  Tree 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...
  
   (Junction tree) and treewidth
• Graph triangulation (see also Chordal graph
  Chordal graph
  In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
  
  )
• Perfect order
• Hidden Markov model
  Hidden Markov model
  A hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved states. An HMM can be considered as the simplest dynamic Bayesian network. The mathematics behind the HMM was developed by L. E...
  
  
  • Baum Welch algorithm
  • Viterbi algorithm
    Viterbi algorithm
    The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models...
    
    
• Incidence matrix
  Incidence matrix
  In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...
  
  
• Independent set problem
• Knowledge representation
  Knowledge representation
  Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
  
  
  • Conceptual graph
    Conceptual graph
    Conceptual graphs are 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...
    
    
  • Mind map
    Mind map
    A mind map is a diagram used to represent words, ideas, tasks, or other items linked to and arranged around a central key word or idea. Especially in British English, the terms spidergram and spidergraph are more common, but they can cause confusion with the term spider diagram used in mathematics...
    
    
• Level structure
  Level structure
  In the mathematical subfield of graph theory a level structure of a graph is a partition of the set of vertices into equivalence classes of vertices with the same distance from a given root vertex.-Definition:...
  
  
• Link popularity
• MacLane's planarity criterion
• Reconstruction conjecture
  Reconstruction conjecture
  Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.-Formal statements:...
  
  
• Scientific classification
  • Cladistics
    Cladistics
    Cladistics is a method of classifying species of organisms into groups called clades, which consist of an ancestor organism and all its descendants . For example, birds, dinosaurs, crocodiles, and all descendants of their most recent common ancestor form a clade...
    
    
  • Neighbor-joining
    Neighbor-joining
    In bioinformatics, neighbor joining is a bottom-up clustering method for the creation of phenetic trees , created by Naruya Saitou and Masatoshi Nei...
    
    
  • Phenetics
    Phenetics
    In biology, phenetics, also known as taximetrics, is an attempt to classify organisms based on overall similarity, usually in morphology or other observable traits, regardless of their phylogeny or evolutionary relation. It is closely related to numerical taxonomy which is concerned with the use of...
    
    
• Turán number
  Turán number
  In mathematics, the Turán number T 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 = 2 by , and the problem for general r was introduced in...
  
  
• Shannon switching game
  Shannon switching game
  The Shannon switching game is an abstract strategy game for two players, invented by Claude Shannon, and independently invented by David Gale; it has also been known as Gale, Bridg-It, and Bird Cage....
  
  
• Snark (graph theory)
  Snark (graph theory)
  In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a...
  
  
• Spectral graph theory
  Spectral graph theory
  In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....
  
  
• Spring based algorithm
• Strongly connected component
  Strongly connected component
  A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
  
  
• Vertex cover problem