Thank you! Give pseudo-code for the following problems, making sure to state all

ID: 3687955 • Letter: T

Question

Thank you!

Give pseudo-code for the following problems, making sure to state all the relevant data structures and representations that you assume. Give a linear-time algorithm for determining whether a given graph is bipartite. Give an 0(V)-time algorithm for determining whether a given graph contains a cycle. Note that your algorithm should run in the allotted time for all graphs, whether sparse or dense. Give an algorithm to find the minimum number of edges that must be removed from a given undirected graph in order to make it acyclic. The diameter of a tree T is the length of the longest path between two nodes in T. Describe an efficient algorithm for computing the diameter of T with V nodes and E edges.

Explanation / Answer

A.Algorithm to test a graph is bipartite or not using BFS. In the main for loop we will check to see if any of our neighbors is the same color as us, and if so output that the graph is not bipartite. If we are able to color the whole graph in this alternating fashion with respect to our parents and not encounter a same color neighboring node then the graph must be bipartite (the two sets will be determined by node color).

ColorGraph(G):

1. start at any node S, and color it blue (opposite color will be red), put s in the queue Q.

2. while Q not empty

(a) x = pop(Queue)

(b) for every neighbor n of x

i. if n isn’t colored, color it the opposite color of x and put it in the queue.

ii. if n is colored and is the same color as x, halt and output NOT BIPARTITE

3. output G IS BIPARTITE

The running time of this algorithm is the same as BFS which is O(|V | + |E|) since the we have O(1) work |V | times with putting things in and out of the queue. We also have O(1) work for every color checking of the neighbors which happens 2|E| times (once for each side of the edge).

An undirected graph is bipartite if its vertices can be divided into two sets V0 and V1 such that every edge goes between these sets. To determine classify the vertices into V0 and V1 during breadth-fist search. After choosing the class of the root, all other choices will be forced in the connected component of the root. If therefore we observe an edge between vertices in the same class then the graph will not be bipartite.

C. Connected component having K vertices must have at most k-1 edged to be acyclic.hence simplest algorithm is to run the connected components algorithm given in class,return the number of connected components and calculate the number of edged that must be removed from there.If there are n vertices in the graph and if there are n vertices in graph and if there m connected components then there must be at most n-m edges remaining in the graph to make it acyclic.If there are e edges overall then e-n+m vertices must be removed.

Alternatively,consider modification of the connected components algorithm to cont edges and vertices in each connected component.If these counts are e & v then e-v+1 is number of edges that must be removed from this component.

D.The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

The diameter of a tree T is the largest of the following quantities:

the diameter of T’s left subtree
the diameter of T’s right subtree
the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

// lh --> Height of left subtree

//rh --> Height of right subtree

1. int lh = 0, rh = 0;

2. // ldiameter --> diameter of left subtree

//rdiameter --> Diameter of right subtree

int ldiameter = 0, rdiameter = 0;

3. if root == NULL

4. height = 0;

5.return 0; //diameter is also 0

6. ldiameter = diameterOpt(root->left, &lh); //Get the heights of left and right subtrees in lh and rh And store the returned values in ldiameter and ldiameter

7. rdiameter = diameterOpt(root->right, &rh);

/* Height of current node is max of heights of left and

right subtrees plus 1*/

8. height = max(lh, rh) + 1;

9.return max(lh + rh + 1, max(ldiameter, rdiameter));