List of graph theory topics

From Wikipedia, the free encyclopedia

This is a list of graph theory topics, by Wikipedia page.

See glossary of graph theory for basic terminology

Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 Trees 5 Graphs in logic 6 Mazes and labyrinths 7 Algorithms 8 Other topics 9 Networks, network theory 10 Hypergraphs

[edit] Examples and types of graphs

See also Trees

• Bipartite graph
  • Complete bipartite graph
  • Disperser
  • Expander
  • Extractor
• Bivariegated graph
• Cayley graph
• Circle graph
• Complement graph
• Complete graph
• Cubic graph
• Dense graph
• Dipole graph
• Directed graph
• Directed acyclic graph
• Interval graph
• Line graph
• Minor graph
  • Robertson–Seymour theorem
• Petersen graph
• Planar graph
  • Dual polyhedron
  • Outerplanar graph
• Random graph
• Regular graph
• Scale-free network
• Sparse graph
  • Sparse graph code
• String graph
• Total graph
• Trellis (graph)
• Turán graph
• Edge-transitive graph
• Vertex-transitive graph
• Visibility graph
  • Museum guard problem
• Wheel graph

[edit] Graph coloring

• Acyclic coloring
• Chromatic polynomial
• Cocoloring
• Complete coloring
• Edge coloring
• Exact coloring
• Four color theorem
• Fractional coloring
• Graph two-coloring
• Harmonious 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

[edit] 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

[edit] Trees

• Tree
  • Abstract syntax tree
  • B-tree
  • Binary tree
    • Binary search tree
      • Self-balancing binary search tree
        • AVL tree
        • Red-black tree
        • Splay 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
  • 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
  • Node
    • Child node
    • Parent node
    • Leaf node
    • Root node
    • Root (computing)
• 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
• Other
  • Tree structure
  • Tree data structure
  • Cayley's formula
  • König's lemma
  • MUD trees
  • 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)

[edit] Graphs in logic

• Conceptual graph
• Entitative graph
• Existential graph
• Laws of Form
• Logical graph

[edit] Mazes and labyrinths

• Labyrinth
• Maze
• Maze generation algorithm

[edit] Algorithms

• Flood fill
• Graph exploration algorithm
• Ant colony algorithm
• Max flow min cut theorem
• Breadth-first search
• Depth-first search
• Depth-limited search
• Shortest path
  • Dijkstra's algorithm
  • Bellman-Ford algorithm
  • A* algorithm
  • Floyd-Warshall algorithm
• Topological sorting
• Maximum Cardinality Search

[edit] Other topics

• Adjacency list
• Adjacency matrix
• Cliques and Independent sets
  • Clique problem
• Connected component
• Cycle space
• de Bruijn sequences
• Erdős-Gyárfás conjecture
• Extremal graph theory
  • Critical graph
  • Turán's theorem
• Frequency partition
• 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
• MacLane's planarity criterion
• Reconstruction conjecture
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Turán number
• Shannon switching game
• Snark (graph theory)
• Spectral graph theory
• Spring based algorithm
• Strongly connected component
• Vertex cover problem

[edit] Networks, network theory

See list of network theory topics

[edit] Hypergraphs

• Helly family
• Intersection (Line) Graphs of hypergraphs