papa-ka-para's blog

By papa-ka-para, history, 7 years ago, In English

while learning from tutorial, I was able to understand first paragraph clearly. I can also see that we just need to find out elementary cycles in graph(which can be done with how to find primary cycles in undirected graph ? , an answer written by Aditya Prakash) .

Now I am not able to grasp how does gaussian method works. I have also tried to look into some solutions like, born2rule , rajat1603 , shubhamgoyal__ . all this solutions look very similar, which uses gaussian method.

so , can someone help me out with gaussian method ? what it actually does ? and when can we use it ?

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by papa-ka-para (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

First we find any path from node 1 to node n.Then to this path we add elementary cycles to get any path.So consider a set of values {a1,a2,a3..ak} where ai represents the xor of values present in the ith elementary cycle and let val denote the xor of values on any path from node 1 to node n.So now we basically need to choose a subset from our set so that xor of values present in this subset with val is maximum.Now its a pretty standard question which can be solved by gaussian elimination.