Теория графов Эйлера
Почему же все попытки нарисовать "конверт", изображённый на рисунке 1а, одним росчерком, то есть, не отрывая руки от бумаги и не проводя дважды один и тот же отрезок. будут обречены на неудачу.
А вот «распечатанный конверт», изображённый на рисунке 2, совсем нетрудно изобразить, выполнив указанные условия. В чём дело?
Впервые над задачами такого типа задумался Леонард Эйлер после посещения города Кенинсберга (теперь Калининград). В городе было семь мостов через реку Прегель. Их расположение указано на рисунке 3.
Гостям города предлагали задачу: пройти по всем мостам, причём по каждому мосту ровно один раз. Никому из гостей не удавалось совершить подобные путешествия.
Эйлер отметил на карте города по одной точке на каждом острове. Затем он соединил эти точки в соответствии с расположением мостов. Получилось следующая картина (рисунок 4). Теперь задача обхода мостов свелась к задаче изображения полученной картинки одним росчерком. Неудивительно, что гостям не удавалось выполнить подобное путешествие, так как решить эту задачу невозможно.
Рис. 4.
Картинки, подобные этой, то есть состоящие из нескольких точек и нескольких дуг, соединяющих некоторые из этих точек получили название графы. Происходят от латинского слова "графио" --- пишу. Выяснилось, что графы очень удобно использовать во многих областях человеческой жизни для описания взаимосвязи между объектами, процессами или событиями.
А всегда ли можно изобразить граф на плоскости, чтобы его рёбра не пересекались? Впервые этот вопрос возник при решении старой головоломки: "в трёх домиках жили три человека, неподалёку находилось три колодца: первый колодец с водой, второй - с маслом, а третий - с повидлом (рисунок 5).
Рис. 5.
Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы тропинки не пересекались. Тогда первоначальный вариант их не устраивал.
Рис. 6.
На рисунке 6 изображена очередная попытка проложить тропинки по условию задачи осталась не проведена одна тропинка. Вывод задачу решить невозможно.
Графы, которые можно изобразить на плоскости без пересечения их рёбер, принято называть плоскими.