Answer: answer given in the explanation
Explanation:
We have n clients and k-base stations, say each client has to be connected to a base station that is located at a distance say 'r'. now the base stations doesn't have allocation for more than L clients.
To begin, let us produce a network which consists of edges and vertex
Network (N) = (V,E)
where V = [S, cl-l, - - - - cl-n, bs-l - - - - - - bs-k, t]
given that cl-l, - - - - - cl-n represents nodes for the clients
also we have that bs-l, - - - - - bs-k represents the nodes for base station
Also
E = [ (s, cl-i), (cl-i,bs-j), (bs-j,t)]
(s, cl-i) = have capacity for all cl-i (clients)
(cl-i,bs-j) = have capacity for all cl-i clients & bs-j (stations)
⇒ using Fond Fulkorson algorithm we find the max flow in N
⇒ connecting cl-i clients to bs-j stations
like (cl-i, bs-j) = 1
if f(cl-i, bs-j) = 0
⇒ say any connection were to produce a valid flow, then
if cl-i (clients) connected f(s,cl-i) = 1 (o otherwise)
if cl-i (clients) connected to bs-j(stations) f(cl-i,bs-j) = 1 (o otherwise)
f(bs-j,t) = no of clients (cl-i) connected to bs-j
⇒ on each node, the max flow value (f) is longer than the no of clients that can be connected.
⇒ create the connection between the client and base station i.e. cl-l to base bs-j iff f(cl-i, bs-j) = 1
⇒ when considering the capacity, we see that any client cannot directly connect to the base stations, and also the base stations cannot handle more than L clients, that is because the load allocated to the base statsion is L.
from this, we say f is the max no of clients (cl-i) that can be connected if we find the max flow, we can thus connect the client to the base stations easily.
cheers i hope this helps
