ART

See glossary of graph theory terms for basic terminology

Examples and types of graphs

  • Amalgamation
  • Bipartite graph
    • Complete bipartite graph
    • Disperser
    • Expander
    • Extractor
  • Bivariegated graph
  • Cage (graph theory)
  • Cayley graph
  • Circle graph
  • Clique graph
  • Cograph
  • Complement of a graph
  • Complete graph
  • Cubic graph
  • Cycle graph
  • De Bruijn graph
  • Dense graph
  • Dipole graph
  • Directed acyclic graph
  • Directed graph
  • Distance regular graph
  • Distance-transitive graph
  • Edge-transitive graph
  • Interval graph
  • Interval graph, improper
  • Interval graph, proper
  • Line graph
  • Lollipop graph
  • Minor
    • Robertson–Seymour theorem
  • Petersen graph
  • Planar graph
    • Dual polyhedron
    • Outerplanar graph
  • Random graph
  • Regular graph
  • Scale-free network
  • Snark (graph theory)
  • Sparse graph
    • Sparse graph code
  • Split graph
  • String graph
  • Strongly regular graph
  • Threshold graph
  • Total graph
  • Tree (graph theory).
    See also: § Trees
  • Trellis (graph)
  • Turán graph
  • Ultrahomogeneous graph
  • Vertex-transitive graph
  • Visibility graph
    • Museum guard problem
  • Wheel graph

Graph coloring
Main article: Graph coloring

  • Acyclic coloring
  • Chromatic polynomial
  • Cocoloring
  • Complete coloring
  • Edge coloring
  • Exact coloring
  • Four color theorem
  • Fractional coloring
  • Goldberg–Seymour conjecture
  • Graph coloring game
  • Graph two-coloring
  • Harmonious coloring
  • Incidence coloring
  • List coloring
  • List edge-coloring
  • Perfect graph
  • Ramsey's theorem
  • Sperner's lemma
  • Strong coloring
  • Subcoloring
  • Tait's conjecture
  • Total coloring
  • Uniquely colorable graph

Paths and cycles

  • Path (graph theory)
  • Seven Bridges of Königsberg
    • Eulerian path
  • Three-cottage problem
  • Shortest path problem
    • Dijkstra's algorithm
      • Open shortest path first
  • Flooding algorithm
  • Route inspection problem
  • Hamiltonian path
    • Hamiltonian path problem
    • Knight's tour
  • Traveling salesman problem
    • Nearest neighbour algorithm
    • Bottleneck traveling salesman problem
  • Path analysis (paths and cycles)

Trees
Main article: Tree (graph theory)

  • Abstract syntax tree
  • B-tree
  • Binary tree
    • Binary search tree
      • Self-balancing binary search tree
        • AVL tree
        • Red–black tree
        • Splay tree
        • T-tree
    • Binary space partitioning
    • Full binary tree
  • B*-tree
  • Heap
    • Binary heap
    • Binomial heap
    • Fibonacci heap
    • 2-3 heap
  • Kd-tree
  • Cover tree
  • Decision tree
  • Empty tree
  • Evolutionary tree
  • Exponential tree
  • Family tree
  • Fault tree
  • Free tree
  • Game tree
  • K-ary tree
  • Octree
  • Parse tree
  • Phylogenetic tree
  • Polytree
  • Positional tree
  • PQ tree
  • R-tree
  • Rooted tree
    • Ordered tree
    • Recursive tree
  • SPQR tree
  • Suffix tree
  • Technology tree
  • Trie
    • Patricia trie
  • Spanning tree
    • Minimum spanning tree
      • Boruvka's algorithm
      • Kruskal's algorithm
      • Prim's algorithm
  • Steiner tree
  • Quadtree

Terminology

Operations

  • Tree rotation
  • Tree traversal
    • Inorder traversal
    • Backward inorder traversal
    • Pre-order traversal
    • Post-order traversal
    • Ahnentafel
  • Tree search algorithm
  • A-star search algorithm
  • Best-first search
  • Breadth-first search
  • Depth-first search
    • Iterative deepening depth-first search

Graph limits

Graphs in logic

Mazes and labyrinths

Algorithms
See also: Graph algorithms and Algorithm

Other topics

  • Adjacency list
  • Adjacency matrix
    • Adjacency algebra – the algebra of polynomials in the adjacency matrix
  • Canadian traveller problem
  • Cliques and independent sets
    • Clique problem
  • Connected component
  • Cycle space
  • de Bruijn sequences
  • Degree diameter problem
  • Entanglement (graph measure)
  • Erdős–Gyárfás conjecture
  • Eternal dominating set
  • Extremal graph theory
    • Critical graph
    • Turán's theorem
  • Frequency partition
  • Frucht's theorem
  • Girth
  • Graph drawing
  • Graph homomorphism
  • Graph labeling
    • Graceful labeling
  • Graph partition
  • Graph pebbling
  • Graph property
  • Graph reduction
  • Graph-structured stack
  • Graphical model
    • Bayesian network
    • D-separation
    • Markov random field
  • Tree decomposition (Junction tree) and treewidth
  • Graph triangulation (see also Chordal graph)
  • Perfect order
  • Hidden Markov model
    • Baum–Welch algorithm
    • Viterbi algorithm
  • Incidence matrix
  • Independent set problem
  • Knowledge representation
    • Conceptual graph
    • Mind map
  • Level structure
  • Link popularity
  • Mac Lane's planarity criterion
  • Node influence metric
  • Reconstruction conjecture
  • Scientific classification
    • Cladistics
    • Neighbor-joining
    • Phenetics
  • Turán number
  • Shannon switching game
  • Spectral graph theory
  • Spring-based algorithm
  • Strongly connected component
  • Vertex cover problem

Networks, network theory

See list of network theory topics
Hypergraphs

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License