The List of graph theory topics reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

List of graph theory topics

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

See glossary of graph theory for basic terminology

Table of contents

1 Examples and types of graphs 2 Coloring 3 Paths and cycles 4 Trees 5 Mazes 6 Algorithms 7 Other topics 8 Networks 9 Hypergraphs

Examples and types of graphs

See also Trees

• Bipartite graph
  • Complete bipartite graph
  • Disperser
  • Expander
  • Extractor
• Cayley graph
• Complete graph
• Directed acyclic graph
• Interval graph
• Inverse graph
• Petersen graph
• Planar graph
  • Dual polyhedron
  • Outerplanar graph
• Regular graph
• Turán graph
• Edge-transitive graph
• Vertex-transitive graph

Coloring

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

Paths and cycles

• Seven bridges of Königsberg
• Three cottage problem
• 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
  • Bottleneck traveling salesman problem
• Path analysis

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
    • Patricia trie
  • Examples
    • Abstract syntax tree
    • Decision tree
    • Evolutionary tree
    • Family tree
    • Fault tree
    • Game tree
    • Parse tree
    • Phylogenetic tree
    • Technology tree
• Spanning tree
  • Minimum spanning tree
    • Boruvka's algorithm
    • Kruskal's algorithm
    • Prim's algorithm
• Steiner tree
• 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
• Exponential tree
• Quad tree

Mazes

• Maze generation algorithm
• Labyrinth

Algorithms

• Flood fill
• Ant colony algorithm
• Bellman-Ford algorithm
  • Max flow min cut theorem

Other topics

• Graph drawing
• Adjacency matrix
  • Link popularity
• Adjacency list
• Incidence matrix
• Clique problem, clique, independent set
• Girth
• Cycle space
• Minor (graph theory)
  • Robertson-Seymour theorem
• Extremal graph theory
  • Turán's theorem
• Spectral graph theory
• Random graph
• Erdös-Gyárfás conjecture
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Knowledge representation
  • Conceptual graph
  • Mind map
• Graph reduction
• Sparse grpah codes
• Vertex cover problem

Networks

• Bayesian network
• Sorting network
• Grid network
• Scale-free network
• Spanning tree (networks)
• Electrical network
• Network topology
• Grid network
• Star network
• Spin network
• Semantic network
• Network engineering
• Network administration
• Network management
• Network congestion avoidance
• Metcalfe's law
• Reed's law
• Petri net

Hypergraphs