Report

DAG Warm-Up Problem McNally and fellow guard Brandyn Curry, who combined for 26 second-half points, came up big for Harvard throughout the final frame. After going scoreless in the first half, Curry scored 12 straight points for the Crimson off four three-pointers during a stretch of 3:27, turning a one-point deficit into a seven-point Harvard lead. Indegree and outdegree of a vertex in a digraph • Vertex v has outdegree 3 • Vertex has indegree 2 v • Lemma. Any finite DAG has at least one node of indegree 0. • Proof. In-class exercise. Tournament Graph • A digraph is a tournament graph iff every pair of distinct nodes is connected by an edge in exactly one direction. • Theorem: A tournament graph determines a unique ranking iff it is a DAG. H P H Y D P Y D Tournament Graphs and Rankings • Theorem: A tournament graph determines a unique ranking iff it is a DAG. • What does this mean? Tournament Graphs and Rankings • Theorem: A tournament graph determines a unique ranking iff it is a DAG. • What does this mean? • That there is a unique sequence of the nodes, v1, …, vn, such that V = {v1, … vn} and for any i and j, i<j implies vi→vj. If a tournament graph G is a DAG, then G determines a unique ranking Proof by induction on |V|. The base case |V|=1 is trivial. Induction. Suppose |V|=n+1 and every tournament DAG with ≤n vertices determines a unique ranking. G has a unique vertex v of indegree 0. (Why is there a vertex of indegree 0? Why is it unique?) Let S be the set of all vertices w such that there is an edge v→w. (What vertices in V are actually in S?) The edges between nodes in S comprise a tournament DAG (why?) and hence determine a unique ranking v1, … vn. Then v, v1, … vn is a unique ranking for the vertices of G. Vertex v can only go at the beginning of the list since v→vi for i = 1, … n (why?). If a tournament graph G determines a unique ranking, then G is a DAG • Proof: Exercise