Author |
Topic: cyclic graph puzzle (Read 793 times) |
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender: 
Posts: 319
|
 |
cyclic graph puzzle
« on: Dec 3rd, 2004, 8:00pm » |
 Quote  Modify
|
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!!!!
|
|
 IP Logged |
While we are postponing, life speeds by
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: cyclic graph puzzle
« Reply #1 on: Dec 7th, 2004, 11:06am » |
Quote Modify
|
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 
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: cyclic graph puzzle
« Reply #2 on: Dec 8th, 2004, 7:33am » |
Quote Modify
|
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
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print