List of graph theory topics

From Wikinfo

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

See glossary of graph theory for basic terminology

Contents 1 Examples 2 Coloring 3 Paths and cycles 4 Trees 5 Mazes 6 Algorithms 7 Other topics 8 Hypergraphs 8.1 References

Examples

• Complete graph
• Petersen graph

Coloring

• Graph coloring
• Bipartite graphs
  • Disperser
  • Expander
  • Extractor
• Four color theorem
  • Tait's conjecture
• Ramsey's theorem

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 (graph theory)
  • 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
• Planar graph
  • Dual polyhedron
• Grid network
• Outerplanar graph
• Cayley graph
• Cycle space
• Regular graph
• Minor (graph theory)
  • Robertson-Seymour theorem
• [[Tur�n graph]]
  • [[Tur�n's theorem]]
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Knowledge representation
  • Conceptual graph
  • Mind map

Hypergraphs

References

• Adapted from the Wikipedia article, "List_of_graph_theory_topics" http://en.wikipedia.org/wiki/List_of_graph_theory_topics, used under the GNU Free Documentation License