91影视

(a)

Consider that, $G\left(V,E\right)$ is a graph where V and E are set of vertices and edges respectively of graph G.S is Source nose or starting node. T is Terminating or sink node. I is Internal nodes which not include S or T.

The reduced graph from multi-source, multi-sink flow to single-source, single-sink flow will be $G\text{'}\left(V\text{'},E\text{'}\right)$.

Here, $V\text{'}=\left\{s,t\right\}+VandE\text{'}=\left\{\left(s,a,鈭�\right)la鈭�S\right\}+E+\left\{\left(b,t,鈭�\right)lb鈭�T\right\}$.

Therefore, the given variation can be solved for Maximum flow s-t on graph G'.

(b)

Let there be a vertex $v鈭�V$ and C_v be the capacity(weight) of the vertex v.

Reduce from node-capacity maximum flow to simple max flow will be:

Consider, $G\text{'}\left(V\text{'},E\text{'}\right)withV\text{'}=\left\{a_{in}\overline{)a鈭�V}\right\}+\left\{a_{out}\overline{)a鈭�V}\right\}andE\text{'}=\left\{\left(a_{in},a_{out},C\overline{)a鈭�E}\right)\right\}+\left\{\left(a_{out},B_{in},C_{\left(a,b\right)}\overline{)\left(a,b\right)鈭�E}\right)\right\}$,

Therefore, The given variation can be solved for maximum flow on s_in- t_out graph G'.

(c)

Consider that $i:N鈫�e$, be the bijective mapping(means every element has being matched) between the edge of the graph and set of natural numbers. C_i,Capacity of edge i, L_i, lower bound of i, and F, Flow along the edge i .

Maximize the sum of f_{i ,} i.e.,

Maximize:$\underset{\left(ie\left(s,v\right)\right)}{鈭�}{f}_i$

Constraints:

$f_i鈮�C_i$for all$i鈭�E$ (Capacities)

$f_i鈮�L_i$for all$i鈭�E$ (Lower Bounds)

$\underset{iintov}{鈭�}{f}_i-\underset{joutofv}{鈭�}{f}_j$for all$v鈭�V-\left\{s,t\right\}$ (Conservation)

Therefore, The given variation can be solved for maximum flow.

(d)

Consider that, e_v be the loss coefficient along each of the node, such that$out-flow=\left(1-e_v\right)inflow\left(v\right)$ for all internal nodes l.

Maximize the sum of all values of f_i

Maximize:$\underset{\left(i鈭�\left(s,v\right)\right)}{鈭�}{f}_i$

Constraints:

localid="1659791095962" $f_i鈮�C_i$for all$i鈭�E$ (Capacities)

$\underset{iintov}{鈭�}\left(1-e_i\right)f_i-\underset{joutofv}{鈭�}{f}_j$for all$v鈭�V-\left\{s,t\right\}$ (Lossy Conservation).

Therefore, The given variation can be solved for maximum flow.