Consider an acyclic directed network of n vertices, labeled į = 1...n, and suppose the labels are assigned in the manner depicted the Figure shown, such that all edges run from vertices with higher labels to vertices with lower. (a) (b) (c) Find an expression for the total number of edges ingoing to vertices ... and another for the total number of edges outgoing from vertices 1...r, in terms of the in- and out-degrees kin and kout of the vertices. Hence find an expression for the total number of edges running to vertices 1...r from vertices r +1...n. Show that in any acyclic network the in- and out-degrees must satisfy for all r. kout ≤ i=1 - Στα (kin – kut) - 8 Figure 6.3: An acyclic directed network. In this network the vertices are laid out in such a way that all edges point downward. Networks that can be laid out in this way are called acyclic, since they possess no closed cycles of edges. An ex- ample of an acyclic network is a citation network of citations between papers, in which the vertical axis would represent date of publication, running up the figure, and all citations would necessarily point from later papers to earlier ones. edges with which to achieve this. It is less obvious but still true that if a network is acyclic it can be drawn in the manner of Fig. 6.3 with all edges pointing downward. The proof that this can be done turns out to be useful, because it also provides us with a method for determining whether a given network is acyclic.