Intro To discrete Math

Denition (Directed graph). A directed graph 'is given by a set of vertices V and a transition relation T Q V X V. We write g = (V, T). Behind this somewhat abstract denition, there is a simpler reality: a graph is a set of nodes connected by arrows, as depicted in Figure In that example, the graph Q; = (V5, TO) has the set of vertices VB and the transition relation To, given as follows: V0 : {(1, b,c,d,e,f, 9: ha'iaja 19} T0 = {(a,b), ((1,6), (Gag): (b: 6), (ca a): (0:9): (83d): (35f): (61f): (f.b),(f,y), (31,6):(had), (M). (3316). (he), (kw-El} 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 counterexamplas. Figure 1: A directed graph go. In English, we can write there 'is a transition from 1) to 12', which formally means (1), 'v') E T. This transition relation describes the fact that two vertices are related in emctty one step. This can be generalized to any number of steps using the following predicate: P('u,v') = Eln EN,Elvo,...,on E Koo =eAnn =e'AV2' E {1,...,n},(v.;_1,vi) ET This predicate states that there is a path between '0 and if: there are n+ 1 vertices on, . . . , on, each connected to the next by a transition ((o,,1,v,;) E T), and with the rst one so being n and the last one 1),, being v'. In that case we say that the path has length to. Exercise 1. Show that in the graph 90 given as an example: 1. P(b,f) is true. 5. P(z',k) is true. 2. P(f,b) is true. 6. P(h, k) is true. 3. P(d,d) is true. 7. P(k,c) is false (this can be hard to do 4. 13w) 1,) is true. completely formally, simply explain it)