Спирина, М.С. Дискретная математика

а 6 Рис. 2.11. Иллюстрации к задаче «О кёнигсбергских мостах»: а — условие; б — граф Например, в графе (/путь (Уг, V4, Уь V2, F5) является гамильто­ новым, а путь (У2, Уз, К», Уь У2, У5) не является гамильтоновым (рис. 2.10). Задача 18 «О кёнигсбергских мостах» (Эйлера). Необходимо обойти все 7 мостов так, чтобы на каждом побывать только один раз и вернуться к началу пути (рис. 2.11, а). Граф к задаче о мостах изображен на рис. 2.11, б. Задача Эйлера «О кёнигсбергских мостах». Историческим поводом для создания математической науки, получившей впоследствии назва­ ние «Теория графов», явилось решение в 1736 г. Л. Эйлером задачи о кёнигсбергских мостах. ВXVHI в. город Кёнигсберг располагался на двух берегах реки Преголи, имеющей два острова, соединенных с берегами и между собой семью мостами. Жители города на практике решали за­ дачу: можно ли пройти по всем семи мостам так, чтобы на каждом из них побывать по одному разу и вернуться к началу пути. Задача Кэли «О четырех красках». Принята такая формулировка этой задачи: на любой политико-административной карте раскрасить страны четырьмя красками так, чтобы никакие две страны, имеющие общую границу, не были раскрашены одинаковым цветом, причем обшей гра­ ницей не может служить одна точка. Сформулируем задачу на языке теории графов: в произвольном не­ ориентированном плоском графе G четырьмя красками раскрасить вер­ шины так, чтобы никакие две смежные вершины не были раскрашены одним цветом. Оказывается, условие задачи выполнимо для пяти красок. Даже доказано, что такая раскраска возможна для всех плоских графов с числом вершин, не превосходящим 38. Но проблема четырех красок ос­ тавалась нерешенной с 1878 г., когда английский математик Кэли при­ вел ее формулировку на заседании Английского королевского научного общества, почти век (решена в 1976 г.). Задача «О трех домах и трех колодцах». Условие этой задачи нам из­ вестно: «Проложить дорожки от трех домов к каждому из трех колодцев так, чтобы никакие две дорожки не пересекались». Эта задача была ре­ шена Куратовским в 1930 г. 78