3. A man is hiking with his three children, Alice, Bob, and Charlie, and all four must get across a rope bridge. None of the children can cross alone, and the father can only escort at most one child across at a time. Furthermore, Alice and Bob will fight if left unsupervised (i.e., if the father is on one side of the bridge with Alice and Bob on the other), and Bob and Charlie will also fight if left unsupervised. The problem is to find a sequence of crossings that gets the entire family from one side of the bridge to the other. (a) (5 points) Construct a bipartite graph with a vertex for each possible state of the problem, indicating which side of the rope bridge each family member is on, with an edge between vertices corresponding to a trip across the bridge. (b) (5 points) Find paths in the graph corresponding to two different solutions, each involving seven crossings 3. A man is hiking with his three children, Alice, Bob, and Charlie, and all four must get across a rope bridge. None of the children can cross alone, and the father can only escort at most one child across at a time. Furthermore, Alice and Bob will fight if left unsupervised (i.e., if the father is on one side of the bridge with Alice and Bob on the other), and Bob and Charlie will also fight if left unsupervised. The problem is to find a sequence of crossings that gets the entire family from one side of the bridge to the other. (a) (5 points) Construct a bipartite graph with a vertex for each possible state of the problem, indicating which side of the rope bridge each family member is on, with an edge between vertices corresponding to a trip across the bridge. (b) (5 points) Find paths in the graph corresponding to two different solutions, each involving seven crossings