Question 6
Employees of the IITM Online Degree Program are assigned to visit the exam centers in Chennai. Vidya has been asked to arrange cabs for these employees to drop them at the centers. She has created a graph (shown below) and asked Sanaya to arrange the minimum number of cabs, but has forgotten to tell Sanaya what the nodes and the edges represent. Sanaya has assumed the following cases and found the answers accordingly.
Cases:
Case 1: Nodes represent the locations of employees and edges represent the roads connecting these locations. Each cab can pick up employees from only one location. Sanaya needs to arrange the minimum number of cabs under the assumption that each employee is willing to walk at most one road length from their current location to a neighboring location to be picked up. Case 2: Nodes represent the employees and if two employees share an edge, then they are assigned different centers. Now, Sanaya needs to arrange the minimum number of cabs such that no two employees assigned for different centers should come in the same cab. (Assume that any number of employees can come in a cab.)
Choose the correct option(s).
Case 1 would be solved by finding the maximum number of elements in independent set.
According to case 1, the minimum number of cabs required would be 2.
According to case 2, the minimum number of cabs required would be 3.
Case 2 would be solved by finding the minimum number of elements in vertex cover set.