Домики и колодцы: кружка

На поверх­но­сти кружки с руч­кой нари­со­вано три домика и три колодца. Попро­буйте мар­ке­ром про­ве­сти дорожки от каж­дого домика к каж­дому колодцу так, чтобы дорожки не пере­се­ка­лись.

Домики и колодцы

Есте­ственно жела­ние начать рисо­вать не на кружке, а на листочке бумаги. И если пори­со­вать раз­ные кар­тинки на листочке, то через неко­то­рое время не оста­ётся сомне­ний в том, что граф $K_{3,3}$ ($3$ домика и $3$ колодца, каж­дый домик соеди­нён дорож­кой с каж­дым колод­цем; пол­ный дву­доль­ный граф) «не пла­на­рен», т.е. не может быть нари­со­ван на плос­ко­сти без пере­се­че­ния рёбер.

Домики и колодцы

Пори­со­вав, можно убе­диться, что невозможно отме­тить на плос­ко­сти $5$ точек и соеди­нить каж­дую с каж­дой непе­ре­се­кающи­мися путями: граф $K_5$ — пол­ный граф на $5$ верши­нах — также не явля­ется пла­нар­ным.

Ясно, что раз непла­на­рен граф $K_5$, то непла­на­рен и любой содержащий его граф: напри­мер, пол­ный граф на $N$ верши­нах при $N > 5$. То же можно ска­зать про граф, содержащий $K_{3,3}$. Заме­ча­тельно, что по сути это един­ствен­ные препят­ствия к пла­нар­но­сти! Это утвер­ждает тео­рема Кура­тов­ского $(1930)$: граф явля­ется пла­нар­ным тогда и только тогда, когда он не содержит подграфа, полу­чающегося из $K_5$ или $K_{3,3}$ под­раз­би­е­нием рёбер.

Про­ве­сти послед­нюю дорожку на листочке можно, если нари­со­вать один мостик, по кото­рому одна дорога про­хо­дит над дру­гой. Но это уже будет не реше­нием задачи на плос­ко­сти, а реше­нием задачи на кружке. В каче­стве мостика можно восполь­зо­ваться руч­кой!

Домики и колодцы
Домики и колодцы

С топо­логи­че­ской точки зре­ния поверх­ность кружки явля­ется тором (поверх­но­стью буб­лика). В тор можно, как гово­рят, «вложить» граф $K_{3,3}$, можно в него вложить и граф $K_5$. И даже граф $K_7$ может быть нари­со­ван на торе — это по сути пред­став­лено в фильме Рас­краски и многогран­ники. Пере­ход от рас­кра­сок к графам такой: внутри «страны» каж­дого из $7$ цве­тов ста­вится по вершине, а рёбра про­во­дятся через участки общей гра­ницы.

Конечно, и на торе можно нари­со­вать совсем не любой граф (проще всего это понять при помощи вер­сии формулы Эйлера для тора). Из тео­ремы Роберт­со­на—­Сеймура сле­дует, что суще­ствует опи­са­ние графов, вложимых в какую-то кон­крет­ную поверх­ность, в духе тео­ремы Кура­тов­ского — предъяв­ле­нием графов, кото­рые нельзя нари­со­вать на ней. Но даже для тора минималь­ный спи­сок препят­ствий состоит уже не из двух графов, а более чем из $10\,000$ (и не все они ещё най­дены). А вот сде­лать матема­ти­че­ский суве­нир, нари­со­вав или рас­пе­ча­тав на кружке три домика и три колодца, можно уже сей­час.

Другие модели раздела «Комбинаторика, вероятность, случайность»