tallman@dspo.UUCP (08/22/84)
> The three houses / three utilities problem has been around for a while. > The three angry workers going to work is isomorphic, and more interesting. > Planar graph theory is sufficient. > You are looking for Kerotowski's theorem (name probably badly miss-spelled). > It states: a graph can be placed in a plane with no crossings > if and only if the graph does not contain a K3,3 or a K5. > A K3,3 is the houses/utilities construct. > A K5 is five points all interconnected. > Karl Dahlke ihnp4!ihnet!eklhad The angry workers problem is not isomorphic to the three houses/three utilities problem, because you must find a path for each to one gate, not all three. (In the utilities problem, three houses must be connected to each of three utilities: water, gas, and electricity, without any lines crossing.) There are several solutions, one of which follows ________________________ | A | aaaaaaaaaaaa | |___| a ___ a | | aaaaaaa | C | a | | |___| a | |cccccccccccccccccc a | |c aaaaaaaaaaaaaaaaaaaa | |c a ___ | |c a| B |bbbbbbbbbbbbbbbbbbb |c a|___| |c aaaaaaaaaaaaaaaaaaa | |cccccccccccccccccc a | |________________ c ___a c a c a A symmetical solution is to let C go straight out, and have A and B go around. Another "solution" is for A to go out of C's gate, around the back of the fence, in at B's gate, and finally out of his own! This only works if the gates are not considered mathematical points. Any other solutions? -- Dave Tallman - ucbvax!lbl-csam!lanl-a!dspo!tallman or dspo!tallman@LANL Los Alamos National Labs - Data Systems Project Office (DSPO) Los Alamos, New Mexico - (505) 667-8495