Being a physicist, I'm not very familiar with the optimization problems in discrete mathematis. I don't know how to formally prove the following:
A town has n horizontal and m vertical streets aligned in a square grid so that there are n x m crossings. Neighboring crossings are distanced by a unit length. What's the smallest length of the road that one must construct so that every crossing is connected to every other by the road?
My solution is L = n x m - 1. I've constructed numerous examples and still can't find a counterexample. But I have no idea how to prove this. Any help will be greatly appreciated.
Aug 13th 2010, 06:00 AM
Two thoughts come to mind: you're dealing with the taxicab geometry here. Also, I doubt very much whether you can get every crossing without your L as a minimum, because of the fencepost problem.
Those are my thoughts.
Aug 13th 2010, 06:18 AM
Thank you for the links. I'm affraid I don't understand what you meant by "get every crossing without your L as a minimum".
Aug 13th 2010, 06:32 AM
"Get every crossing" just a rephrase of "traverse very crossing", or "connect every crossing by a road." If you think about this problem in terms of graph theory, then your crossings are vertices, and the roads are edges. If you have n vertices, you'll require a minimum of n-1 edges to connect all the vertices. In your case, with m x n crossings (vertices), you'll need m x n - 1 roads to connect all the crossings, as a minimum. Does that clarify things?
Aug 13th 2010, 06:35 AM
Yes, thank you, that was the argument I needed. I'm not used to think in terms of graph theory.
Aug 13th 2010, 06:48 AM
Just a thought here: it makes a big difference that all the crossings must be connected to all the other crossings. The basic problem in graph theory is the minimum edge cover problem. But what you're really trying to solve is a minimum connected edge cover problem, which is definitely different. Another name for this problem is the minimum spanning tree problem, where all the weights are equal. I would use the pigeon-hole principle to prove the desired result. If you use fewer edges than your L, a vertex is going to have to be omitted from the tree, right?
Aug 13th 2010, 09:01 AM
I think that proof by induction is the simplest one and will suffice.
Aug 13th 2010, 09:32 AM
Induction sounds like it would work just fine. You're planning on inducting on the number of vertices, I'm assuming?
Aug 13th 2010, 10:50 AM
Yes, I will prove by induction that the general vertices can be connected this way and then that one can always find a system of roads of that length.
Aug 13th 2010, 10:55 AM
I think that'll work for you. Just show that the number of roads can't be less than L, and then show that you can construct a path of length L that satisfies the conditions, and you'll be done. Good luck!