Graph Theory Notes

Varying Applications

  • Computer networks, chemical compound distinction, shortest path problems, scheduling

Topics Covered

  • Definitions, types, terminology, representation, sub-graphs, connectivity, Hamilton and Euler definitions, shortest path, planar graphs, graph coloring

Definitions - Graph

  • Graph G = (V, E) consists of vertices V and edges E

Definitions – Edge Type

  • Directed: Ordered vertex pair (u, v)

  • Undirected: Unordered vertex pair {u, v}

Definitions – Edge Type

  • Loop: Edge joining a vertex to itself {u}

  • Multiple Edges: Edges joining same vertex pair

Definitions – Graph Type

  • Simple (Undirected) Graph: Vertices V, edges E (unordered pairs)

  • Multigraph: Vertices V, edges E, function f from E to {{u, v} | u, v ∈ V, u ≠ v}. Multiple edges if f(e1) = f(e2)

  • Pseudograph: Vertices V, edges E, function F from E to {{u, v} | u, v Î V}. Loops allowed

  • Directed Graph: Vertices V, edges E (ordered pair)

  • Directed Multigraph: Vertices V, edges E, function f from E to {{u, v} | u, v ∈ V}. Multiple edges if f(e1) = f(e2)

Terminology – Undirected graphs

  • Adjacent if {u, v} is an edge

  • Degree of Vertex (deg (v)): Number of incident edges (loop counts twice)

  • Pendant Vertex: deg (v) =1

  • Isolated Vertex: deg (k) = 0

Terminology – Directed graphs

  • u adjacent to v: (u, v) edge, u - Initial, v - Terminal

  • In-degree (deg- (u)): Edges where u is terminal

  • Out-degree (deg+ (u)): Edges where u is initial

Theorems: Undirected Graphs

Theorem 1: Handshaking theorem: 2e = Σ deg(v), v∈V
Theorem 2: Undirected graph: even number of odd degree vertices

Theorems: directed Graphs

Theorem 3: Σ deg + (u) = Σ deg - (u) = ||E||

Simple graphs – special cases

  • Complete graph: Kn, one edge between each distinct vertex pair

  • Cycle: Cn, n ≥ 3, vertices v1…vn, edges {v1, v2}…{vn, v1}

  • Wheels: Wn, add vertex to Cn, connect to all vertices

  • N-cubes: Qn, vertices: 2n bit strings, adjacent if differ by one bit

Bipartite graphs

  • V partitioned into V1, V2; edges connect V1 and V2

Complete Bipartite graphs

  • Km,n: vertex set into subsets of m and n vertices

Subgraphs

  • Graph H =(V’, E’) where V’ ⊆ V, E’ ⊆ E. G = G1 U G2, E = E1 U E2, V = V1 U V2

Representation

  • Incidence (Matrix): Edges more important than vertices

  • Adjacency (Matrix/List): Vertices more important than edges

Graph - Isomorphism

  • G1 = (V1, E2) and G2 = (V2, E2) isomorphic if there is a one-to-one correspondence f from V1 to V2, a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent in G2

Connectivity

  • Reachability among vertices

Connectivity – Path

  • Sequence of edges connecting adjacent vertices

Connectivity – Path

  • Directed Graphs: Path of length n (> 0) from u to v in G is a sequence of n edges e1, e2 , e3, …, en of G such that f (e 1) = (xo, x1), f (e2) = (x1, x2) , …, f (en) = (xn-1, xn), where x0 = u and x n = v.

  • Circuit/Cycle: u = v, length of path > 0

  • Simple Path: No repeated edge

Connectivity – Connectedness

  • Undirected Graph: Connected if there is a simple path between every vertex pair

Connectivity – Connectedness

  • Undirected Graph: Articulation Point (Cut vertex): Vertex removal increases connected components; Cut Edge: Edge removal increases connected components

Connectivity – Connectedness

  • Directed Graph: Strongly connected: path from a to b and b to a; Weakly connected: undirected path between every two vertices

Connectivity – Connectedness

  • Directed Graph: Strongly connected Components: strongly connected subgraphs

Isomorphism - revisited

  • Isomorphic invariant: simple circuit of length k > 2

Counting Paths

  • Theorem: G with adjacency matrix A, paths of length r from Vi to Vj = (i, j) th entry of Ar.

Euler - definitions

  • Eulerian path: path using each edge once; traversable graph

  • Eulerian cycle: cycle using each edge once; Eulerian graph

Euler - theorems

  1. Connected graph G is Eulerian iff connected, no odd degree vertices

  2. Connected graph G has Euler trail from a to b iff connected, a ≠ b are only odd degree nodes

Hamiltonian Graph

  • Hamiltonian path: visits each vertex once

  • Hamiltonian cycle: visits each vertex once (except start)

  • DIRAC’S Theorem: if G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2 then G has a Hamilton circuit.

  • ORE’S Theorem: if G is a simple graph with n vertices with n ≥ 3 such that deg (u) + deg (v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.

Shortest Path

  • Weighted digraph G = (V,E), W: E ® R

  • Path weight w(p) = Σ w(vi, vi+1)

Shortest-Path Problems

  • Single-source: shortest path from source s to each vertex

  • Single-pair: shortest path between two vertices

  • All-pairs: shortest paths for every vertex pair

Optimal Substructure

  • Theorem: subpaths of shortest paths are shortest paths

Relaxation

  • Relax (u,v,G): if v.d() > u.d()+G.w(u,v), v.setd(u.d()+G.w(u,v)), v.setparent(u)

Dijkstra's Algorithm

  • Non-negative edge weights, greedy

  • Maintain set S of solved vertices