Ostrich888's blog

Doubt in Cycle Basis of graph
By Ostrich888, history, 4 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

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.

That's because this claim (as you have stated it) is wrong, probably it got mangled in the process.

The actual claim is that any Eulerian subgraph of our graph $$$G$$$ (subgraph of $$$G$$$ containing the same vertices as $$$G$$$, with any vertex having an even degree) can be represented as a linear combination of the elements in $$$S$$$. That is, given any Eulerian subgraph $$$H$$$ of $$$G$$$ we can find some cycles in $$$S$$$ such that $$$H$$$ is the XOR of these cycles.

Proof. Notice that any edge of $$$G$$$ that is not in the spanning tree is present in exactly one of the cycles in $$$S$$$. Take an Eulerian subgraph $$$H$$$ of $$$G$$$, let's express it as a XOR of some cycles in $$$S$$$. While $$$H$$$ contains an edge $$$e$$$ not in the spanning tree, we XOR $$$H$$$ with the cycle $$$C$$$ in $$$S$$$ containing $$$e$$$. Besides $$$e$$$, $$$C$$$ does not contain any other edge not in the spanning tree, so this operation will reduce the number of non-span-edges in $$$H$$$. After a finite number of steps $$$H$$$ will consist of only spanning tree edges. At this stage, since all vertices of $$$H$$$ must have even degree, $$$H$$$ will have no edges at all. This proves that it is possible to represent $$$H$$$ as a XOR of some of the cycles in $$$C$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Can't we say that every cycle of G will be an Eulerian subgraph of G. Hence claim is true.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      I think you are probably a bit confused woth the terminology and have conflated the meanings of some words. Your claim was:

      The claim is that every set of cycles in the graph is a subset of this set S

      Indeed every cycle of is an Eulerian subgraph so we can say something like

      Every cycle in the graph is the XOR of a subset of this set S

      And a set of disjoint cycles is also an Eulerian subgraph, so we can even say

      Every set of disjoint cycles is the XOR of a subset of this set S.

      Pay close attention to the words I have bolded. A set of disjoint cycles is an XOR of some subset of S, but that does not mean it is the subset of S itself.

      It may seem like a small nitpick but to me the meanings of these sentences are quite different and I think that this implies at least some confusion with the terminology.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Now, I got it.

        Thank you for your valuable time.

        → Reply