List of graph theory topics

See glossary of graph theory for basic terminology

Examples and types of graphs

• Bipartite graph
  • Disperser
  • Expander
  • Extractor
• Cayley graph
• Complete graph
• Interval graph
• Petersen graph
• Planar graph
  • Dual polyhedron
  • Outerplanar graph
• Regular graph
• Turán graph

Coloring

• Graph coloring
• Four color theorem
  • Tait's conjecture
• Ramsey's theorem
• Sperner's lemma

Paths and cycles

• Seven bridges of Königsberg
• Shortest path problem
  • Dijkstra's algorithm
    • Open shortest path first
• Flooding algorithm
• Route inspection problem
• Hamiltonian cycle problem, Hamiltonian path
  • Knight's Tour
    • How to solve the knight's tour
• Traveling salesman problem
  • Nearest neighbour algorithm

Trees

• Tree
  • Terminology
    • Root node, root (computing)
    • Leaf node
    • Child node, parent node
    • Ply
  • Tree structure
  • Tree data structure
  • AVL tree
  • B-tree
  • Binary tree
  • Binary search tree
  • Heap
    • Binary heap
    • Binomial heap
    • Fibonacci heap
  • Red-black tree
  • Splay tree
  • Tree rotation
  • Trie
  • Examples
    • Abstract syntax tree
    • Decision tree
    • Evolutionary tree
    • Family tree
    • Game tree
    • Parse tree
    • Phylogenetic tree
    • Technology tree
• Spanning tree
  • Minimum spanning tree
    • Boruvka's algorithm
    • Kruskal's algorithm
    • Prim's algorithm
• 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
• Self-balancing binary search tree
• König's lemma

Mazes

• Maze generation algorithm
• Labyrinth

Algorithms

• Flood fill
• Ant colony algorithm
• Bellman-Ford algorithm

Other topics

• Graph drawing
• Adjacency matrix
  • Link popularity
• Adjacency list
• Clique problem
• Girth
• Grid network
• Cycle space
• Minor (graph theory)
  • Robertson-Seymour theorem
• Turán's theorem
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Knowledge representation
  • Conceptual graph
  • Mind map

Hypergraphs

Referenced By