Попробуйте нарисовать «конверт», изображенный на рис.1, одним росчерком пера, т. е. не отрывая ручки от бумаги и не проводя дважды один и тот же отрезок. Ваши попытки будут обречены на неудачу. А вот «распечатанный конверт», изображенный на рис.2, совсем нетрудно нарисовать, выполнив указанные условия. В чем здесь дело?

 

 

рис.1

рис.2

Впервые над задачей такого типа задумался Леонард Эйлер после посещения города Кенигсберга (ныне Калининград). В городе было семь мостов через реку Прегель. Их расположение указано на рис.3. Гостям города предлагали задачу: пройти по всем мостам, причем по каждому мосту ровно один раз. Никому из гостей не удавалось совершить подобное путешествие.

С

В

Рис. 3

 

Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове. Затем он соединил эти точки в соответствии с расположением мостов. Получилась следующая картинка (рис.4). Теперь задача обхода мостов свелась к задаче изображения полученной картинки одним росчерком.

Картинки, подобные этой, то есть состоящие из нескольких точек (их стали называть вершинами) и нескольких дуг, соединяющих некоторые из этих точек (их стали называть ребрами) получили название графов. С дворянским титулом их объединяет общее происхождение от латинского слова «графио» — пишу.

С

 В

А

Рис. 4

Заметим, кстати, что генеалогические деревья дворянских родов — это также графы в их математическом понимании. Если вы взглянете на географическую карту, то увидите граф, вершины которого — города, а ребра — соединяющие их линии железных дорог. Выяснилось, что графы очень удобно использовать во многих областях человеческой жизни для описания взаимосвязей между объектами, процессами или событиями. Но вернемся к кенигсбергской задаче.

Давайте ее четко сформулируем. При каком условии можно обойти все ребра графа, пройдя каждое ровно один раз? Решение оказалось очень простым. Сосчитаем, сколько ребер выходит из каждой вершины. Одни из этих чисел будут четными, а другие — нечетными. Будем и сами вершины называть четными, если из них выходит четное число ребер, и нечетными в противном случае. Эйлер доказал, что если среди вершин графа больше двух четных вершин, то этот граф можно обойти, а если их меньше двух, то нельзя.

При наличии двух четных вершин обход следует начинать в одной из них, а заканчивать в другой. У графа не может быть ровно одной нечетной вершины (это нетрудно показать), а если у него нет нечетных вершин, то обход можно начинать с любой вершины и в ней же заканчивать.

В графе на рис.1 пять вершин: одна четная и пять нечетных, следовательно, этот граф нельзя обойти. В графе на рис.2 шесть вершин: четыре четных и две нечетных. Для обхода этого графа следует начинать обход в одной из нижних вершин, а заканчивать в другой. В графе на рис.4 четыре вершины, все они нечетны, поэтому граф обойти нельзя.

Частные мастера Винтовые лестницы на второй этаж

Дренажная система водоотвода вокруг фундамента - stroidom-shop.ru

Правильное создание сайтов в Киеве https://atempl.com/r/