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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ

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

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

к библиотеке   к оглавлению   Базовые понятия теории графов  
Знаете ли Вы, что такое "Большой Взрыв"?
Согласно рупору релятивистской идеологии Википедии "Большой взрыв (англ. Big Bang) - это космологическая модель, описывающая раннее развитие Вселенной, а именно - начало расширения Вселенной, перед которым Вселенная находилась в сингулярном состоянии. Обычно сейчас автоматически сочетают теорию Большого взрыва и модель горячей Вселенной, но эти концепции независимы и исторически существовало также представление о холодной начальной Вселенной вблизи Большого взрыва. Именно сочетание теории Большого взрыва с теорией горячей Вселенной, подкрепляемое существованием реликтового излучения..."
В этой тираде количество нонсенсов (бессмыслиц) больше, чем количество предложений, иначе просто трудно запутать сознание обывателя до такой степени, чтобы он поверил в эту ахинею.
На самом деле взорваться что-либо может только в уже имеющемся пространстве.
Без этого никакого взрыва в принципе быть не может, так как "взрыв" - понятие, применимое только внутри уже имеющегося пространства. А раз так, то есть, если пространство вселенной уже было до БВ, то БВ не может быть началом Вселенной в принципе. Это во-первых.
Во-вторых, Вселенная - это не обычный конечный объект с границами, это сама бесконечность во времени и пространстве. У нее нет начала и конца, а также пространственных границ уже по ее определению: она есть всё (потому и называется Вселенной).
В третьих, фраза "представление о холодной начальной Вселенной вблизи Большого взрыва" тоже есть сплошной нонсенс.
Что могло быть "вблизи Большого взрыва", если самой Вселенной там еще не было? Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 06.06.2020 - 11:02: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
06.06.2020 - 11:02: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Пламена Паскова - Карим_Хайдаров.
06.06.2020 - 07:27: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
06.06.2020 - 07:26: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вячеслава Осиевского - Карим_Хайдаров.
05.06.2020 - 20:47: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
05.06.2020 - 19:41: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
05.06.2020 - 19:40: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
05.06.2020 - 17:58: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Владимира Николаевича Боглаева - Карим_Хайдаров.
05.06.2020 - 17:24: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
05.06.2020 - 17:23: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> КОМПЬЮТЕРНО-СЕТЕВАЯ БЕЗОПАСНОСТЬ ДЛЯ ВСЕХ - Карим_Хайдаров.
05.06.2020 - 11:12: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
05.06.2020 - 08:38: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Андрея Фурсова - Карим_Хайдаров.
Bourabai Research Institution home page

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

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