Report

Directed Graphs 3/6/12 1 Normal Person’s Graph y y = f(x) x 3/6/12 2 Computer Scientist’s Graph a b c d f e 3/6/12 3 Digraphs • a set, V, of vertices aka “nodes” • a set, E V×V of directed edges (v,w) E notation: vw v 3/6/12 w 4 Relations and Graphs a d b c V= {a,b,c,d} E = {(a,b), (a,c), (c,b)} 3/6/12 5 Digraphs Formally, a digraph with vertices V is the same as a binary relation on V. 3/6/12 6 Walks & Paths Walk: follow successive edges length: 5 edges (not the 6 vertices) 3/6/12 7 Walks & Paths Path: walk thru vertices without repeat vertex length: 4 edges 3/6/12 8 Walks & Paths Lemma: The shortest walk between two vertices is a path! Proof: (by contradiction) suppose path from u to v crossed itself: c u 3/6/12 v 9 Walks & Paths Lemma: The shortest walk between two vertices is a path! Proof: (by contradiction) then path without c---csuppose is path from u to v crossed itself: shorter! c u 3/6/12 v 10 Walks & Paths Digraph G defines walk + relation G + u G v iff ∃walk u to v (the positive walk relation) “+” means 1 or more 3/6/12 11 Walks & Paths Digraph G defines walk * relation G * u G v iff 1 w u to v alk 2 3 length 0 (the walk relation) “*” means “0 or more” 3/6/12 12 Cycles A cycle is a walk whose only repeat vertex is its start & end. (a single vertex is a length 0 cycle) 3/6/12 13 Cycles … v0 v1 v2 vn-1 v0 vi v0 3/6/12 vi+1 14 Closed Walks & Cycles Closed walk starts & ends at the same vertex. Lemma: The shortest positive length closed walk containing a vertex is a positive length cycle! Proof: similar 3/6/12 15 Directed Acyclic Graph DAG has no positive length cycle 3/6/12 16 lec 7M.16 Directed Acyclic Graph examples: DAG < relation on integers ⊊ relation on sets prerequisite on classes 3/6/12 17 Example: Tournament Graph • Every team plays every other H H Y P D Y P D DAG => Unique ranking 3/6/12 18