Description

Jaya Gupta(200471) Pratyush Gupta(200717)
1 Question1 → Bipartite
1.1 Pseudo Code
function dfs(G,u,sec)
. returns true if graph corresponding to vertices of the dfs tree rooted at u is . bipartite else return false
visited[u]=true
section[u]=sec
if sec == 1 then . section array store in which section (V 1,V 2) do every vertex lies
alt sec=2 . alt sec stores the section in which all the vertex adjacent to u will lie in
else alt sec=1
end if
for all (u,v) ∈ E do if visited[v] == false then ans=dfs(G,v,alt sec) if ans==false then return false
end if else if section[v]==sec then return false
end if . if the ajacent vertex lies in the same section as u return false(cant be bipartite)
end if
end for
return true
end function
function Bipartite(G) v← G.v e ← G.e
for all u ∈ V
visited[u]=false
return dfs(G,0,1) end function
1
function main
ans = Bipartite(G) if ans == true then for all u ∈ V do print(YES) print(section[u])
end for
else print(NO)
end if end function
2 Question2 →Uniqueness of Partition of vertices in sets (V 1,V 2) 2.1 Answer
• First of all since the above algorithm is just a slight modification of dfs (only few commands which takes constant time are added), the above algorithm works in O(V + E) time.
• If the graph is connected and if it is bipartite , then the partition of vertices in the two sets (V 1,V 2) is unique because if we decide the section of any one of the vertex then all the other vertices will automatically fall in their respective sections as the graph is connected.
• If the graph is unconnected then it will have several disconnected components . All the different components will be connected graphs individually. So if all those components are bipartite, then we can decide the section in which one vertex from each component will lie and all others will fall accordingly.
• So the choice of that section for one vertex each from each component is not unique and is totally upon us whether we want to keep it in set V 1 or V 2 . Hence the sections V 1,V 2 are not unique in case of disconnected graph.