How Can We Optimize Road Layouts Connecting Multiple Towns?

[Natasha1]

If the vertices of a square represent four townships and are all connected by a system of roads.

To keep costs to a minimum, what is the ideal arrangement of roads?

What insights are gained from the above to find similar cost effective systems of roadways for 5 and 6 towns i.e. those represented by the vertices of a regular pentagon and hexagon respectively.

Please help...

 

[HallsofIvy]

What have you done? In particular, what "costs" are you talking about? Just the cost of building the roads? In that case, you want to keep the total length of the roads to a minimum. Have tried some examples? Suppose you put a road along each side of the square. That would connect all of the towns wouldn't it? What is the total length of those roads? Do you really need all four? What would happen if you removed one of them? That would reduce the length wouldn't it? But you would still be able to go from any town to any other.
Okay, now let's use the interior of that square. Suppose we built roads along each of the diagonals of the square? (That is, build a road from each town to the center of the square.) Would we still be able to go from any town to any other? What would be the total length of the roads?
Suppose we picked some point other than the center of the square and built roads from each town to that point? Can you use "symmetry" to argue that the total length must be longer than from each town to the center of the square?

Now, how can you generalize that to a regular pentagon or hexagon?

 

[CarlB]

To solve this rather difficult problem, it helps to think of the problem as one where all the roads are equivalent to strings each under identical tension. That is, each of the roads wants to get shorter just as much as the other roads.

Because of this fact, the only way that you can connect three roads at a point that is not one of the towns is with 120 degrees between the roads. If you had less than 120 degrees between two of the roads, it would be advantageous to to move the point where the three roads meet closer to where those two roads come from.

For your problem, you will want to show this intuitively obvious fact with calculus, but the most difficult part of the problem is to visualize all the possible ways of hooking up the towns.

Carl