Doubt in Cycle Basis of graph

Revision en3, by Ostrich888, 2020-06-29 23:49:50

Hello Everyone!

https://codeforces.net/contest/845/problem/G

The problem says that we are given a weighted connected graph in which path length is defined as xor of all weights on the path. We are given two vertices and need to find shortest path length.

In the solution, we are calculating cycle basis of graph. For this we first make a spanning tree of the graph. Let's assume we have an empty set S. Then we take all the non-spanning edges of the graph one by one and find the cycle which this edge is making with only the spanning edges and include this cycle in our set S . The claim is that every set of cycles in the graph is a subset of this set S (We can also reduce S to its basis). I am unable to get this claim.[It is wrong claim as stated in the comments.] Can somebody give me a proof of this of how is it including every cycle that exists in the graph

Can we also represent every closed walk in the graph using the subset of set S?

Thank You

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Ostrich888 2020-06-29 23:49:50 46
en2 English Ostrich888 2020-06-29 22:03:15 85 Tiny change: 'f set S?\nThank Yo' -> 'f set S?\n\n\nThank Yo'
en1 English Ostrich888 2020-06-29 21:51:00 878 Initial revision (published)