Introduction to Graph Theory

• Graph

  A graph G consists of a set V of vertices and a set E of edges such that each edge e Î E is associated with an unordered pair of vertices.

• Graph Representations
  
  • Adjacency Matrix
  • Adjacency Linked List
  • Incidence Matrix

  Theorem :
  If G is agraph with m edges and n vertices { v_i : i = 1,.. n} , then

  S d(v_i) = 2 m .
  Corollary: In any graph, there are an even number of vertices of odd degree.

• Simple Graph

  A graph with no parallel edges or loops.

• Isomorphisms of Graphs

  Graphs G₁ and G₂ are isomorphic if there is a one-to-one, onto function f from the vertices of G₁ to the vertices of G₂ and a one-to-one , onto function g from the edges of G₁ to the edges of G₂ , so that an edge e is incident on v and w in G₁ if and only if the edge g(e) is incident on f(v) and f(w) in G₂. The pair of functions f and g is called an isomorphism of G₁ onto G₂.

  Theorem : Graphs G₁ and G₂ are isomorphic if and only if for some ordering of their vertices, their adjacency matrices are equal.

  Corollary : For simple graphs G₁ and G₂, they are isomorphic if and only if there is a one-to-one, onto function f from the vertex set of G₁ to the vertex set of G₂ satisfying the following: Vertices v and w are adjacent in G₁ if and only if the vertices f(v) and f(w) are adjacent in G₂.

• Planar Graph

  A graph is planar if it can be drawn in the plane without its edges crossing.

  Euler's Formula for Planar Graph
  

  for any planar graph G, we have :
  f = e - v + 2 where f = number of faces (contiguous region) ,
  e = number of edges and v = number of vertices .

  In any simple, connected, planar graph G , we always have e £ 3v - 6

  K₅ and K_3,3 are not planar.
  

  Kuratowski's Theorem : A graph G is planar if and only if G does not contain a subgraph homeomorphic to K₅ or K_3,3 .

• Dijkstra's Shortest-Path Algorithm
  Input : A connected weighted graph with positive weighted, vertice a and z
  Output : L(z) , the length of a shortest path from a to z .

  1.  procedure dijkstra(w,a,z,L)
  2.       L(a) := 0 
  3.       for all vertices x ¹  a do 
  4.           L(x) := ¥
  5.         T := set of all vertices
  6.      // T is the set of vertices whose shortest distance from a has 
  7.      // not been found
  8.      while  z  Î  T do 
  9.           begin 
  10.           choose v Î T with minimum L(v)
  11.           T := T - {v}
  12.           for each x Î T adjacent to v  do 
  13.              L(x) := min{ L(x), L(v) + w(v,x)}
  14.           end 
  15.   end dijkstra
  

  For input consisting of n-vertex, simple, connected, weighted graph,
  Dijkstra's Algorithm has worst-case run time Q (n²) .

  Example

• Euler Cycle (path)

  A cycle (path) in a graph G that includes all of the edges (as a consequence, also includes all the vertices) is called an Euler cycle (path).

  The necessary and sufficient condition for a graph G to have a Euler cycle is

  1. G is connected and
  2. every vertex in G has even degree

  The necessary and sufficient condition for a graph G to have a Euler path is

  1. G is connected and
  2. every vertex except two in G has even degree

• Hamiltonian Cycle

  A cycle in a graph G that contains each vertex in G exactly once, except for the starting and ending vertex that appears twice.

  A path in a graph G that contains each vertex in G exactly once is called a Hamiltonian path.

  There is no well-known necessary and sufficient condition for the exitence of a hamitonian cycle in a given graph G.

  More about Hamiltonian circuits

• The Traveling saleperson problem (TSP) :

  Given a weighted graph G, find a minimum-length Hamiltonain cycle for G.

  Some other links to the related graph topics :

• Some umsolved Combinatorial Problem

• Four Color problem
• Resource of Graph Theory

• Graph Coloring

• graph resource
• Notes on Graph from stanford
• Math library -- graph theory