к библиотеке   к оглавлению   Базовые понятия теории графов  

Задача о кёнигсбергских мостах

Рис. 1. Карта Кёнигсберга

Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти все семь мостов, стоявших тогда в городе Кёнигсберге (современный Калининград, Россия), побывав на каждом по одному разу? Перед вами план Кёнигсберга – можете попробовать!

Рис. 2. Кенигсбергские мосты

Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.

кенигсбергских мостов">

Рис. 3. Граф кенигсбергских мостов

Несколько модифицируем задачу. Каждую из рассматриваемых местностей, разделенных рекой, обозначим точкой, а соединяющие их мосты – отрезком линии (не обязательно прямой). Тогда вместо плана будем работать просто с некой фигурой, составленной из отрезков кривых и прямых. Такие фигуры в современной математике называются графами, отрезки – ребрами, а точки, которые соединяют ребра – вершинами. Тогда исходная задача эквивалентна следующей: можно ли начертить данный граф, не отрывая карандаша от бумаги, то есть таким образом, чтобы каждое его ребро пройти ровно один раз.

Такие графы, которые можно начертить, не отрывая карандаша от бумаги, называются уникурсальными (от латинского unus cursus – один путь), или эйлеровыми. Итак, задача ставится таким образом: при каких условиях граф уникурсален? Ясно, что уникурсальный граф не перестанет быть уникурсальным, если изменить длину или форму его ребер, а также изменить расположение вершин – лишь бы не менялось соединение вершин ребрами (в том смысле, что если две вершины соединены, они должны оставаться соединенными, а если разъединены – то разъединенными).

Рис. 4. Топологически эквивалентные графы

Если граф уникурсален, то и топологически эквивалентный ему граф тоже будет уникурсальным. Уникурсальность, таким образом, является топологическим свойством графа.

Во-первых, надо отличать связные графы от несвязных. Связными называются такие фигуры, что любые две точки можно соединить каким-нибудь путем, принадлежащим этой фигуре. Например, большая часть букв русского алфавита связны, но вот буква Ы – нет: невозможно перейти с ее левой половинки на правую по точкам, принадлежащим этой букве. Связность – это топологическое свойство: оно не меняется при преобразованиях фигуры без разрывов и склеек. Понятно, что если граф уникурсален, то он обязан быть связным.

Во-вторых, рассмотрим вершины графа. Будем называть индексом вершины число ребер, встречающихся в этой вершине. Теперь зададимся вопросом: чему могут равняться индексы вершин уникурсального графа.

Здесь может быть два случая: линия, вычерчивающая граф, может начинаться и заканчиваться в одной и той же точке (назовем ее «замкнутый путь»), а может в разных (назовем ее «незамкнутый путь»). Попробуйте сами нарисовать такие линии – с какими хотите самопересечениями – двойными, тройными и т. д. (для наглядности лучше, чтобы ребер было не больше 15).

Нетрудно видеть, что в замкнутом пути все вершины имеют четный индекс, а в незамкнутом – ровно две имеют нечетный (это начало и конец пути). Дело в том, что, если вершина не является начальной или конечной, то, придя в нее, надо затем из нее выйти – таким образом, сколько ребер входят в нее, столько же выходят из нее, а всего число входящих и исходящих ребер будет четным. Если начальная вершина совпадает с конечной, то ее индекс также четен: сколько ребер из нее вышло, столько же и вошло. А если начальная точка не совпадает с конечной, то их индексы нечетные: из начальной точки нужно один раз выйти, а затем, если в нее и вернемся, то выйти снова, если еще раз вернемся – опять выйти, и т. д.; а в конечную нужно придти, а если из нее потом и выходим, то опять нужно вернуться, и т. д.

Итак, чтобы граф был уникурсальным, необходимо, чтобы все его вершины имели четный индекс либо чтобы число вершин с нечетным индексом равнялось двум.

Теперь посмотрите еще раз на граф задачи о кенигсбергских мостах.

Посчитайте индексы его вершин и убедитесь, что он никак не может быть уникурсальным. Вот поэтому-то у вас ничего не получалось, когда вы хотели обойти все мосты...

Возникает вопрос: а если в связном графе нет вершин с нечетным индексом либо таких вершин ровно две, то обязательно ли граф уникурсален? Можно строго доказать, что да! Таким образом, уникурсальность однозначно связана с числом вершин с нечетным индексом.

Упражнение: постройте на схеме кенигсбергских мостов еще один мост – там, где захотите – чтобы полученные мосты можно было бы обойти, побывав на каждом ровно по разу; реально проделайте такой путь.

Теперь еще один интересный факт: оказывается, любую систему местностей, соединенных мостами, можно обойти, если необходимо побывать на каждом мосту ровно два раза! Попробуйте это доказать самостоятельно.

Рис. 6. Граф кенигсбергских мостов с удвоенным количеством мостов уникурсален

Ответ

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

Рисунок с кенигсбергскими мостами, у каждого из которых появляется рядом мост-близнец; рисуется также эквивалентный граф, у всех вершин пишется их новый индекс, выделенная точка зримо обходит этой граф и – синхронно – схему плана Кёнигсберга, при этом получаемый путь постепенно закрашивается; когда вернулась в исходную точку, обходит все снова, при этом весь путь постепенно перекрашивается в новый цвет, и так далее.

к библиотеке   к оглавлению   Базовые понятия теории графов  
Знаете ли Вы, в чем фокус эксперимента Майкельсона?

Эксперимент А. Майкельсона, Майкельсона - Морли - действительно является цирковым фокусом, загипнотизировавшим физиков на 120 лет.

Дело в том, что в его постановке и выводах произведена подмена, аналогичная подмене в школьной шуточной задачке на сообразительность, в которой спрашивается:
- Cколько яблок на березе, если на одной ветке их 5, на другой ветке - 10 и так далее
При этом внимание учеников намеренно отвлекается от того основополагающего факта, что на березе яблоки не растут, в принципе.

В эксперименте Майкельсона ставится вопрос о движении эфира относительно покоящегося в лабораторной системе интерферометра. Однако, если мы ищем эфир, как базовую материю, из которой состоит всё вещество интерферометра, лаборатории, да и Земли в целом, то, естественно, эфир тоже будет неподвижен, так как земное вещество есть всего навсего определенным образом структурированный эфир, и никак не может двигаться относительно самого себя.

Удивительно, что этот цирковой трюк овладел на 120 лет умами физиков на полном серьезе, хотя его прототипы есть в сказках-небылицах всех народов всех времен, включая барона Мюнхаузена, вытащившего себя за волосы из болота, и призванных показать детям возможные жульничества и тем защитить их во взрослой жизни. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 26.04.2017 - 22:30: СОВЕСТЬ - Conscience -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
26.04.2017 - 21:28: СОВЕСТЬ - Conscience -> Просвещение от Михаила Делягина - Карим_Хайдаров.
26.04.2017 - 19:10: СОВЕСТЬ - Conscience -> Просвещение от Константина Сёмина - Карим_Хайдаров.
26.04.2017 - 16:44: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
25.04.2017 - 19:16: Беседка - Chatter -> ФУТУРОЛОГИЯ - прогнозы на будущее - Карим_Хайдаров.
25.04.2017 - 03:11: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
25.04.2017 - 00:47: АСТРОФИЗИКА - Astrophysics -> Происхождение тектитов и кимберлитов. Кометные молнии. - Евгений_Дмитриев.
25.04.2017 - 00:32: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
25.04.2017 - 00:29: СОВЕСТЬ - Conscience -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
23.04.2017 - 05:25: СОВЕСТЬ - Conscience -> Просвещение от Марата Мусина - Карим_Хайдаров.
22.04.2017 - 05:49: СОВЕСТЬ - Conscience -> Проблема народного образования - Карим_Хайдаров.
20.04.2017 - 19:38: СОВЕСТЬ - Conscience -> Декларация Академической Свободы - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution

Источник: sc.uriit.ru/dlrstore