Why Graph Theory?

With the advent of computers, several problems turned out to be manifestation and application of graph theory. These are problems that are not very easy to solve for an individual with just a paper and pen. However, if the theory is known, application of this knowledge is very easy and thus the solutions are straightforward.

Discussed below are some famous problems that motivated a systematic study of graphs/networks.

Knight’s Tour: You have a knight that should move around the chess board visiting each square exactly once. Further, it should return to the same square. If you know what a hamiltonian circuit is, you can easily model the knight’s moves as a graph and solve this.

TimeTable: For m professors and n subjects, prepare an optimal timetable. Turns out to be a minimum coloring problem.

More such problems and their manifestation to graphs is discussed in this article.

Advertisements

Graph Theory – My Mindmap

This is my mindmap of what an introduction to graph theory constitutes of. Will explore some of these topics in near future.

Graph Theory

  • Concepts
    • Vertex, Path, Connectivity, Trees, Forests, Cycles
    • Matching & Coloring
    • Chromatic Number
  • Types
    • Based on connectivity: Isomorphic, Null, Bipartite Graphs, Planar (Dual, Infinite) Graphs, k-partite & k-colorable, Directed (Digraph)
    • Based on Walks: Eulerian, Hamiltonian (walks cover all edges and end at initial vertex)
    • Based on shapes: Stars, Platonic, etc…
  • Walks
    • Euler Tour & Hamilton Cycles
  • Theorems
    • Hall’s, Euler’s Formula, Brook’s, matroid theory
  • Well-known problems
    • four-color, marriage