Question

Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected.

Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so that no two edges in the matching share a common vertex. A vertex cover is a collection U CV of vertices so that for every edge uv E E either u EU or v EU.

1. Show that the largest size matching in a graph is no larger than the size of an arbitrary vertex cover in the graph.

2. Show that if I is an independent set then G(V – I) (namely, the graph with vertices V - I, restricted to edge with both endpoints in V - I is) a Vertex Cover.

3. Give an example for a graph so that the Maximum Matching is strictly smaller than the minimum Vertex Cover

4. A clique is a collection C of vertices U so that for every uv EC, uv E E. Say that we are given an algorithm that finds a clique of maximum size in time f(n). Give an O(n) + f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graph

Answer 1

For an undirected connected graph where every edge belongs to at least one simple cycle, it is always possible to give a direction to every edge so that the graph will be strongly connected.

A directed graph is strongly connected if there is a path between all pairs of vertices.

To get a path between every pair, give the direction of every edge in the same direction so that it makes a circle(simple loop). This way every vertices will be connected.

For eg, for this undirected graph,

we can make the following strongly connected directed graph