Given a weighted and undirected graph, we need to find if a cycle exist in this graph such that the sum of weights of all the edges in that cycle comes out to be odd.
I have read GFG article but not able to understand . It would be could I can get a dry run on this question
Hi @yashraj1399 ,
we try to solve dis question by taking into account that bipartite graph has even cycle. This is a theorem and can be easily proved . The above is true because in order to return back to initial vertice(x in V(A)) in bipartite graph(vertice set A and B), the path will be x-V(B)-V(A)-V(B)-x which will always be of even length.
Also, it is known that bipartite graph is two colorable i.e we can color whole graph into 2 colour such that no 2 adjacent vertices have same colour(since a vertex in Set A is only connected to vertices in set B). So, we can colour Set A as RED and set B as BLUE.
So, we traverse through the adjajency matrix, if colour of vertex ‘a’ is RED, colour of its neighbour should be BLUE. SO colour all d colour in dis way. If any vertex is found whose neighbour is of same colour, then its not bipartite graph and hence contains a odd cycle.
Also, u should first check whether a graph contains a cycle or not and then check if its odd or even.
Hope dis helps.
If u still hv any doubts, pls post it here.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.