dm graph

• In-class problems
  • walks and paths
  • Walk relation
  • DAG & scheduling
  • partial orders

In-class problems¶

walks and paths¶

problem: If you were trying to walk somewhere quickly, you’d know you were in trouble if you came to the same place twice.

Theorem 10.2.3. A shortest walk from one vertex to another is a path.

Question 1: tournament digraph.

1. Prove: if a tournament diagraph is a DAG, then it has most one ranking.

   A ranking is a path that includes all the players（也就是排名顺序）

   proof 0: prove by contradiction…

   Idea 1: we should figure out which part could lead to contradiction

   Hypothesis 1: the first two common vertices in two ranking(my idea)

   方向反了，由于结构是DAG，两条同起点终点不同序的路不能证明circle的存在。

   Hypothesis 2: (u, v) (v, u) exist in two different rankings. -> a closed walk from u to u that go through v.

   有证明的可能。将u,v间的两条路合并起来，说明有circle的存在。

   Loophole: 不能证明一定会经过v

   1. approach 1: well ordering principle

   Lemma: The shortest positive length closed walk through a vertex is a cycle.

   Proof 1: suppose w is a minimum positive length walk from u to u. we claim w is a cycle.

   prove by contradiction: w is a cycle.

   • case 1: u occurs more than two times in w
   • Case 2: some vertex x != u occurs twice in w

   2)approach 2: strengthen the hypothesis

   把u->v和v->u合并会形成circle

2. Give an example of a tournament with a countably infinite number of players that has no ranking.

   为什么这会影响ranking呢？我认为是因为总有更小的数存在，这会和当前的假设违背。

Walk relation¶

problem: whether there is a way to get from one particular vertex to another.

binary relation,

我认为这只是符号证明（？）

DAG & scheduling¶

problem: topological sort

partial orders¶

Any digraph is formally the same as a binary relation whose domain and codomain are its vertices.

Definition 10.6.7. A relation that is transitive and irreflexive is called a strict partial order.