?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Difficult

Determining if a Graph is Bipartite

ALGOR-H9KWHG

For a group project, you and your partner are given a list of seminars that you need to write summaries on. In order to do this, one of you must go to each seminar in order to write a summary about it. However, some of the seminars overlap in time and you are not allowed to leave a seminar early or come in late.

Therefore, you need to find a way to divide up the seminars such that neither of you is given two overlapping seminars but between the both of you, every seminar is attended. Assume the list of seminars allows you to do this.

Which of the following methods is the most efficient way to do this that will always return the correct answer?

A

Create an undirected graph where the seminars are the nodes and there is an edge between two seminars if they overlap in time. Run Breadth-First Search, where each layer of nodes found by the algorithm is given the opposite color of the previous layer.

A layer i in Breath-First Search is all the nodes discovered for the first time in the i-th iteration of the algorithm. If none of the edges of the graph have the same color nodes at their ends, then your partner will take all of the seminars in one color and you will take all of the seminars of the other color.

B

Create a directed graph where the seminars are the nodes and there is a directed edge from one seminar to another if the first seminar starts before the second one and they overlap in time. Run a topological sort on the graph.

Give the odd numbered seminars in the resulting topological order to your partner and go to all of the even numbered seminars in the resulting topological order yourself.

C

Create an undirected graph where the seminars are the edges and the seminars connect to the same node if they overlap in time. Run Depth-First Search, where every edge you take to explore the next node is given the opposite color of the last edge you took to explore the previous node.

Your partner will take all of the seminars colored with the first color and you will take all of the seminars of the other color.

D

Randomly divide the list of seminars into two groups. If there are no overlapping seminars in either group, your partner will attend all of the seminars in one group while you attend all of the seminars in the other group.

If there is an overlapping pair of seminars in one of the groups, randomly divide the list of seminars into two different groups until you find a grouping without overlapping seminars.