Consider an acyclic directed network of n vertices, labeled i = 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.

Find an expression for the total number of edges ingoing to vertices 1...r and another for the total number of edges outgoing from vertices 1...r , in terms of the in- and out-degrees and 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.

Transcribed Image Text:

8 8

Answer rating: 100% (QA)

The number of invertices and number of outvertices are mar... View the full answer