Пред­по­ло­жим, что у нашей си­сте­мы дорог пе­ре­крест­ков нет, то есть име­ет­ся одна до­ро­га, со­еди­ня­ю­щая по­сле­до­ва­тель­но вер­ши­ны квад­ра­та E, F, G и H. Тогда ее длина будет не мень­ше трех сто­рон квад­ра­та (буквы «П» на рис. (а)), то есть не мень­ше 12 (до­ро­га, со­еди­ня­ю­щая со­сед­ние вер­ши­ны квад­ра­та, не мень­ше его сто­ро­ны). Зна­чит, ис­ко­мая (а в иде­а­ле крат­чай­шая) си­сте­ма дорог долж­на иметь пе­ре­крест­ки (на­при­мер, как на рис. (д)). Чтобы по­нять каким об­ра­зом можно эф­фек­тив­но общую длину дорог умень­шать, по­лез­но пре­жде об­ра­тить вни­ма­ние на не­ко­то­рые свой­ства, ко­то­ры­ми крат­чай­шая си­сте­ма дорог обя­за­на об­ла­дать:

1.  Крат­чай­шая си­сте­ма дорог со­сто­ит из от­рез­ков, со­еди­ня­ю­щих пе­ре­крест­ки и вер­ши­ны квад­ра­та. Это оче­вид­но, по­сколь­ку крат­чай­шим путем из одной точки в дру­гую яв­ля­ет­ся от­ре­зок пря­мой. От­ме­тим без до­ка­за­тель­ства, хотя и это почти оче­вид­но, что для любой си­сте­мы го­ро­дов крат­чай­шая си­сте­ма дорог их со­еди­ня­ю­щая  — это связ­ный граф без за­мкну­тых путей, реб­ра­ми ко­то­ро­го слу­жат от­рез­ки.

2.  Каж­дый пе­ре­кре­сток дол­жен быть со­еди­нен ми­ни­мум с тремя вер­ши­на­ми графа (вер­ши­на­ми квад­ра­та или пе­ре­крест­ка­ми). (Если он со­еди­нен толь­ко с двумя, то смыс­ла в нем не­мно­го: его можно уда­лить, а эти две вер­ши­ны со­еди­нить на­пря­мую; по­лу­чит­ся ко­ро­че.)

3.  Угол между лю­бы­ми двумя до­ро­га­ми, вы­хо­дя­щи­ми из од­но­го пе­ре­крест­ка (или из одной вер­ши­ны квад­ра­та) не может быть мень­ше 120°. Дей­стви­тель­но, пусть из точки A вы­хо­дят до­ро­ги AB и AC, и угол BAC мень­ше 120°. Тогда до­ро­ги AB и AC можно за­ме­нить до­ро­га­ми с мень­шей сум­мар­ной дли­ной. Если в тре­уголь­ни­ке ABC все внут­рен­ние углы мень­ше 120°, то до­ро­ги AB и AC за­ме­ним на до­ро­ги TA, TB и TC, где T  — точка То­ри­чел­ли тре­уголь­ни­ка ABC (рис. (б)). Если же, на­при­мер, угол B боль­ше 120°, то AB и AC за­ме­ним на AB и BC (рис. (в)).

4.  Из од­но­го пе­ре­крест­ка вы­хо­дят ровно три до­ро­ги под уг­ла­ми 120° (иначе длина дорог может быть умень­ше­на). Это не­мед­лен­но сле­ду­ет из свойств (2) и (3).

Пред­по­ло­жим, что си­сте­ма дорог об­ла­да­ет одним пе­ре­крест­ком. Если он со­еди­нен со всеми вер­ши­на­ми рис. (г), то длина дорог не мень­ше суммы диа­го­на­лей, ко­то­рая равна Если же он со­еди­нен толь­ко с тремя вер­ши­на­ми (рис. (д)), то T  — точка То­ри­чел­ли тре­уголь­ни­ка EFH, вер­ши­на G со­еди­не­на с F. В этом слу­чае длина дорог при­бли­зи­тель­но равна 11,7. Более того, на­ру­ше­но свой­ство (3), так как а зна­чит длину дорог можно умень­шить, до­ба­вив еще один пе­ре­кре­сток (как в слу­чае на рис. (б)).

Пусть пе­ре­крест­ков два. Из со­об­ра­же­ний сим­мет­рии рас­по­ло­жим их на па­рал­лель­ной двум сто­ро­нам оси сим­мет­рии квад­ра­та (рис. (е)) так, чтобы из каж­до­го пе­ре­крест­ка до­ро­ги вы­хо­ди­ли под уг­ла­ми 1200 (свой­ство (4)). В этом слу­чае сум­мар­ная длина дорог равна

Ответ: на­при­мер, си­сте­ма дорог с двумя пе­ре­крест­ка­ми на па­рал­лель­ной двум сто­ро­нам оси сим­мет­рии квад­ра­та (рис. (е)). Из каж­до­го пе­ре­крест­ка до­ро­ги вы­хо­дят под уг­ла­ми 120°. Их сум­мар­ная длина равна

Ком­мен­та­рий.

Си­сте­ма дорог на рис. (е) на­зы­ва­е­мая сетью Штей­не­ра дан­ных че­ты­рех точек, вер­шин квад­ра­та E, F, G и H. Без до­ка­за­тель­ства от­ме­тим, что эта си­сте­ма имеет ми­ни­маль­ную длину из всех воз­мож­ных.