wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> cyclic graph puzzle
        
(Message started by: puzzlecracker on Dec 3^rd, 2004, 8:00pm)

Title: cyclic graph puzzle
Post by puzzlecracker on Dec 3^rd, 2004, 8:00pm

You have a cyclic graph where all edges are eithre marked red or blue. The question is to construct a tree (any!!!) that will contain the least numbe of red edges.

^{I think it has to do something with spanning tree, something I don't know know much about yet!!!!}

Title: Re: cyclic graph puzzle
Post by John_Gaughan on Dec 7^th, 2004, 11:06am

I suppose a spanning tree algorithm would work. Set the red edges equal to 10000, the blue edges equal to 1, and spend about a year trying to find the optimal spanning tree ;D

Title: Re: cyclic graph puzzle
Post by puzzlecracker on Dec 8^th, 2004, 7:33am

AWESOME!!!! can you or anyone else for that matter - direct me to an easy-to-undestand and, at the same time, comprehensive reference on minimum spanning tree and its algorithms???

Title: Re: cyclic graph puzzle
Post by igni_ferroque on Dec 8^th, 2004, 2:51pm

Minimum spanning trees (http://www.ics.uci.edu/~eppstein/161/960206.html)