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.\fWe define ~ as " on the SCC graph": wo= {(v, U') EV/@ | In EN, 3vo, ..., Un EV/8, vo = vAUn = v'NVi E {1, ..., n}, (vi-1, Vi) ET/@}