On point-to-point communication networks

A point-to-point communication network is represented by (G,C), where G=(V,ε) is a directed graph with vertex set V and edge set ε, and C=[C_ij,(i,j)∈ε] is a nonnegative-valued vector. A vertex in V represents a node in the communication network, and an edge (i,j) represents a point-to-point discrete memoryless channel (DMC) from node i to node j whose capacity is C_ij. We assume that the channels in the network are independent of each other. An information source with entropy rate h is generated at source node δ and recovered at sink node t with arbitrarily small probability of error. We show that the value of a max-flow from node δ to node t in (G,C) must be greater than or equal to h. This results implies a separation theorem for network coding and channel coding in such a communication network