Homework Six - quick answers

1. 27 cells, 14 black, 13 blue. Center cell is blue. HAM path must be 27 long, must start and end with black (the 14 count color). But Center cell is blue.

2. If a spanning tree S is not optimal, mimic proof that Kruskal works to show that S can always be improved upon

3. Need only show graph is connected. If x, y not directly connected, then adding {x,y} creates a circuit - indicating that there must already be an alternate path from x to y

4. As in textbook...

-- Robbie Moll - 2014-12-09

Comments

Topic revision: r1 - 2014-12-09 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort