Discrete Math

Directed Graphs Let us first give the formal definition: Definition (Directed graph). A directed graph is given by a set of vertices V and a transition relation T C V x V. We write 9 = (V, T). Behind this somewhat abstract definition, there is a simpler reality: a graph is a set of nodes connected by arrows, as depicted in Figure 1. In that example, the graph Go = (Vo, To) has the set of vertices Vo and the transition relation To, given as follows: Vo = {a, b, c, d, e, f, g, h, i, j, k} To = {(a, b), (a, c), (a, g), (b, e), (c, a), (c, g), (e, d), (e, f), (e, i), ( f, b), (f, g), (h, c), (h, d), (i, j), (j, k), (k, g), ( k, i) } Note that this is only an example of a graph, but in this paper we are going to prove things on all graphs. This particular graph is however a good source of examples and counterexamples. Figure 1: A directed graph go. In English, we can write there is a transition from v to v', which formally means (v, v') E T. This transition relation describes the fact that two vertices are related in exactly one step. This can be generalized to any number of steps using the following predicate: P(v, v') = 3n EN, 3vo, . .., Un EV, vo = v A Un = V A Vie {1, . .., n}, (vi-1, Vi) ET This predicate states that there is a path between v and v': there are n + 1 vertices vo, . .., Un, each connected to the next by a transition ((Vi-1, vi) E T), and with the first one vo being v and the last one Un being v'. In that case we say that the path has length n.Exercise 6. Answer the following questions, each time proving your claim: 1. Is \"'69 reexive? 2. Is \"'69 symmetric? 3. Is We antisymmetric? Hint: Prove the following lemma: Lemma. For (my vertices [v], ['U'] E V/g, if [U] -> [U'] then 'U w '0'. 4. Is We transitive? 5. Is we, an equivalence relation? 6. Is We an order relation? If yes, is it total? Note: In this exercise we consider We not over a particular graph, but in general. So when the answer is yes, a proof must be for any graph, but when the answer is no, a counterexample can be from a particular graph (from Qo/ for instance)