We can find the solution by running Ford-Fulkerson algorithm on the above flow network and find the value of Max Flow.
If value of Max Flow is equal to sum of all the number of students from each city, then we can say that there exists a acceptable condition, such that every student from each city is seated at each table, and also no more than 3 students from the same city are sitting on the same table.
If the Max flow value is not equal to the sum of the total no. of students from every city, then there doesn't exist enough tables to accommodate the students according to the given constraint or capacity of each table isn't enough.
If the given constrained is satisfied then we can find the optimal seating arrangement, \(i.e\) which student sits on which table, we need to look at the residual graph G' that is generated after finding the Max Flow.
There would be backward edges present after the last iteration of Ford Fulkerson algorithm in the graph G', and to find the solution we need to look at backward edges that originate from table nodes towards city nodes with residual capacity of 3. Let's represent these backward edges as \(\left(T_j,\ c_i\right)\)
These backward edges of the form \(\left(T_j,\ c_i\right)\) depicts that 3 students from city \(i\) can sit on table \(T_j\).
3.
Let's assume in a Graph G there is a cycle C which is the shortest cycle between Node A and C. A shortest cycle is also a simple cycle.
d(A,B) = 1 , d(B,C) = 1 , d(C,A) = 1 So Diam(G) = maximum distance which is 1. Cycle length is 3 which satisfies the condition.
Let's assume the length of the Cycle be 2*Diam(G)+2. This means there exist a pair of vertices in C that has distance of at least Diam(G)+ 1. But their distance is lesser than that in the graph considered here. And the cycle considered here is the shortest cycle so the shortest path between these nodes must be included in the shortest cycle which means the cycle is not the shortest cycle which is a contradiction and thus at most the length can be 2*Diam(G) + 1.