Архимедово лето. Глава пятая.

коль­цевой путь может включать в себя любое число петель, то есть до­бавочных кольцевых маршрутов. Ну-с?

— Вот чертеж, — сказала Веточка. — На нем есть два четных узла: один двойной, а другой восьмерной. Если у нас только один

clip_image012

простой кольцевой маршрут — он нарисован на этом чертеже рядом справа, — то ясно, что его можно обойти, тут и доказывать нечего: и так видно. Более сложный случай четного узла представляет собой не что иное, как несколько простых четных, то есть двойных, узлов, кото­рые слились вместе. Так как каждый из них обходится в отдельности, то, значит, можно обойти и их все вместе, по очереди и в каком хочешь порядке. Так что тут у нас не может быть никаких затруднений, исключая тот слу­чай, когда просто прозеваешь, да и уйдешь совсем из этого узла, обойдя не все петли, то есть не четыре, а только три. С какого узла мы начинаем наше путешествие, это для обхода значения не имеет. Начнем с узла а — перед нами будут три петли, соединяющиеся в узле Ъ, Мы обойдем половину верхней петли, затем из узла Ъ осталь­ные три петли и вернемся в а, закончив обход тем, что пройдем остав­шуюся непройденной половину верхней петли. Если же начинаем с узла &, то мы обходим в любом порядке все четыре наши петли. Где можно прозевать? Начиная с узла а, можно вернуться к нему, не пройдя, например, одной из петель.

— По-моему, — сказала Наташа, — вот еще что надо сказать. Когда мы уходим из начального четного узла, в нем остается нечетное число нехоженых путей, потому что по одному пути мы прошли, и он теперь использован, погашен. Таким образом, из четного числа путей один удален и число путей стало нечетным. А затем мы, проходя насквозь через остальные четные узлы, всякий раз погашаем тем са­мым в каждом четном узле два пути, а следовательно, из четного чи­сла путей вычитаем четное же число путей, а это, как ни ходи, должно неизбежно кончиться тем, что, вычитая каждый раз по двойке, мы све­дем к нулю число путей всех четных узлов, кроме начального. И тогда у нас останется единственный непройденный путь, который и приведет нас к начальному четному узлу, если он просто двойной. А если он больше чем двойной — Вовочка, извини, тут нужны еще буквы, но только немного, ты не бойся! — то есть если число путей в нем будет 2п, то мы пройдем через этот узел насквозь (п—1) раз и погасим 2(п— 1) путей. Так как один раз уже мы в нем были, когда отправлялись в наше путе­шествие, то всего мы пройдем [2 (п—1) + 1] путей, или просто (2п— 1). А у нас всего пу­тей там было 2п, и значит, нам и останется один-единственный путь, на котором дело и кончается.

Страница 8 of 13« First...89...Last »
Category: Разное