300000
Паутина©
Общее количество побед: 147660
| (6 – 20): | Цикл Путь Случайный Вызов |
Определения + Как это все еще "математическая" игра?
Диаграммы в этой игре основаны на области математики, известной как теория графов!
Что такое график?
Граф: Граф состоит из узлов и ребер.
Node: «объекты», которые соединяет граф, называются узлами. В Spider Web узлы — это круги.
Ребро: Ребро — это соединение в графе между двумя узлами. В Spider Web края представляют собой линии.
Удлинение контура
Путь: Контур представляет собой последовательность соединенных ребер с начальным и конечным узлами.
Путь Эйлера: Это путь, который использует каждое ребро в графе ровно один раз.
Цель в этой игре - найти Эйлеров Путь.
Что такое эйлеровы пути в повседневной жизни?
Снегоуборочная машина, грузовик для уборки улиц и почтальон являются примерами автомобилей и людей, которым нужно пройти по каждой улице, но которые не хотят проходить по улице дважды.
Звучит ли вам знакомо имя «Эйлер»?
Теория графов зародилась, когда математик Леонард Эйлер работал над такого рода путями.
Эйлер написал статью о семи мостах Кёнигсберга, доказав, что невозможно пройти через город, пересекая каждый мост ровно один раз.
Нажмите на карту проблемы ниже, чтобы узнать о ней больше.
Цикл: Цикл — это путь, который заканчивается на узле, на котором начался.
Эйлеров цикл: Это Эйлеров путь, который также является циклом. Выберите "Цикл" в нашей игре выше, и решением всегда будет цикл Эйлера!
Инструкции по настройкам игры
В текстовом поле рядом с Узлы вы можете ввести любое число от 6 до 20. Это число будет количеством узлов, отображаемых на графике. Чем больше число, тем сложнее становится решение!
Далее выберите тип диаграммы
Цикл: Выигрышные пути всегда будут заканчиваться на узле, на котором они начались.
Путь: Выигрышные пути не будут заканчиваться на узле, на котором они начались.
Random: Графики, которые могут допускать цикл Эйлера или траекторию Эйлера. Выигрышные пути могут заканчиваться, а могут и не заканчиваться на том узле, на котором они начались.
Задача: Созданные вручную графики, на которых пересекаются ребра и, следовательно, мосты не очевидны.
Наконец, нажмите «Создать новую сеть», чтобы увидеть изменения в настройках графика!
Какой узел следует выбрать в первую очередь?
Степень: степень является свойством узла. Это количество ребер, соединенных с ним. Мы будем различать нечетные и четные узлы в зависимости от их степени.
Connected Graph: Граф, в котором каждая пара узлов может быть соединена с помощью пути.
Мост: Ребро является мостом, если два конца ребра не могут быть соединены иным образом. Таким образом, перейдя мост, вы не вернетесь на прежнюю сторону. При удалении моста граф разбивается на два несвязанных компонента.
Неориентированный граф : Граф, к которому ребра не имеют направления. В этой игре мы рассматриваем только тех, кто участвует.
Направленный граф : Граф, в котором каждое ребро имеет направление, прикрепленное, как улица с односторонним движением.
Неориентированный граф содержит эйлеров цикл, когда все узлы имеют четную степень (степень 0, 2, 4, 6...). Для них вы можете выбрать любой узел в качестве начального и все равно выиграть. Только имейте в виду, что вам придется финишировать на том узле, с которого вы начали.
Граф содержит путь Эйлера, но не цикл Эйлера, когда ровно два узла имеют нечетную степень (степень 1, 3, 5, 7...) и все остальные узлы имеют четную степень. В этом случае вы должны выбрать узел с нечетным градусом в качестве начального узла иначе вы не сможете завершить путь Эйлера.
Почему именно два узла?
Думайте о каждом шаге как о «извне» узла, из которого вы пришли, и «внутри» к узлу, к которому вы перемещаетесь. Большинство узлов будут следовать этой схеме спаривания, поэтому они будут иметь четную степень.
Когда вы начинаете игру, первое ребро, которое вы отмечаете, является ходом «наружу» начального узла. Он остается несопряженным во время игры.
Чтобы создать цикл Эйлера, последнее ребро, которое вы отмечаете, является ходом «внутрь» к начальному узлу. Таким образом, создается пара с первым ходом, то есть начальный узел имеет четный градус.
Если путь Эйлера графа не является циклом, то последнее ребро, которое вы отмечаете, является непарным перемещением «внутрь» к узлу, который не является начальным узлом. начальный узел остается с нечетной степенью, а конечный узел также будет иметь нечетную степень.
Не переживайте ни о каких других случаях. Если бы количество узлов с нечетной степенью не было точно 0 или 2, не было бы ни эйлеровых путей, ни эйлеровых циклов, то есть не было бы возможности выиграть. Такие графики не должны появляться в этой игре.
Предварительные вопросы
Может ли быть нечетное количество узлов с нечетной степенью?
Нет.
Почему?
Доказательство:
Подсчет всех концов всех ребер дает то же число, что и сложение всех степеней всех узлов, согласен?
Поскольку каждое ребро имеет 2 конца, общее количество концов всех ребер должно быть четным. (Сложение четных чисел дает четное число.)
Чтобы сложить градусы всех узлов, нужно сложить четные градусы, что дает четное число, и сложить нечетные градусы.
Если бы существовало нечетное число узлов с нечетными степенями, то эта сумма была бы нечетной, а затем четная + нечетная = нечетная, так что общее число степеней было бы нечетным. Но она равна общему числу всех концов всех ребер, и то есть четно. Следовательно, количество нечетных узлов не может быть нечетным, оно должно быть четным.
Например, 1 является нечетным числом, поэтому не существует графа, содержащего только 1 узел нечетной степени.
Когда существует Эйлеров путь или цикл?
Если узел имеет четную степень, т.е. 2, 4, 6,... Ребра прикрепляются к узлу, затем, когда они достигают этого узла, остается нечетное количество неиспользуемых ребер, которое больше нуля, поэтому можно будет покинуть этот узел и продолжить путь. Если степень нечетная, т.е. 1, 3, 5,.. Если вы прикрепляете ребра, то либо путь должен начинаться в этом узле, либо путь заканчивается в этом узле. Поскольку путь имеет только 2 конца, может быть только 2 узла с нечетной степенью. Следовательно:
Чтобы иметь цикл Эйлера, граф должен иметь только четные вершины, а чтобы иметь путь Эйлера, он должен иметь 2 нечетных вершины, один из которых будет началом, а другой — концом пути.
Как найти Эйлеров Путь или Цикл?
Как показано выше, если нет узлов нечетной степени, то можно начать с любого узла и закончить в том же узле. Если существует ровно 2 узла с нечетными степенями, то один из них должен начинаться с любого из этих 2 узлов и автоматически заканчивается на другом.
Может ли что-то пойти не так при продлении пути?
Да, что-то может пойти не так. Пример:
2 4 / \ / \ 1---3---5
Степень всех узлов равна 2, за исключением узла 3, который имеет степень 4. Так что все степени одинаковы, и мы можем начать с чего угодно. Давайте начнем с узла 1 и перейдем к узлу 3 и отбросим все ребра, которые были пройдены.
2 4 / \ / \ 1 3---5
Ребро 3-2 становится мостом. При пересечении и удалении этого ребра 3-2 получается разрозненный граф
2 4 / / \ 1 3---5
которые уже нельзя полностью пройти. Следовательно, следует продолжать с 3 на 4 или на 5, чтобы завершить эйлеров цикл.
Как предотвратить переход по мосту?
Чтобы проверить, является ли ребро мостом, нужно начать с одного конца ребра и посетить все его соседние узлы, всех их соседей и так далее. Если один не попадает на другую сторону края, то край – это мост. Такой полный обыск всех соседей стоит не очень дорого. Но если нужно сделать это до того, как пересечь каждый край, то общее усилие будет большим. Полный алгоритм называется алгоритмом Флери, восходящим к 1883 году.
Есть ли более эффективный алгоритм?
Более эффективным алгоритмом является алгоритм Гирхольцера (1873).
Если граф имеет 2 узла с нечетными степенями, то можно найти путь, иначе цикл, в обоих случаях очень быстро без проверки мостов.
1) После удаления всех используемых ребер степень оставшихся неиспользуемых ребер равномерна по всем узлам.
Почему?
Если градус узла был четным, то к нему одинаково часто приближались, как его оставили, так он и остается ровным. Если степень была нечетной, то это либо начальный узел, либо конечный узел первого пути, а затем он был оставлен + приближен в сумме нечетное количество раз, поэтому оставшаяся степень нечетная − нечетная = четная.
2) Должен быть хотя бы один узел с используемыми и неиспользуемыми смежными ребрами.
Почему?
Потому что исходный граф был связан.
Из-за 1) можно найти цикл неиспользуемых ребер, начинающийся и заканчивающийся на этом узле. Потому что 2) этот цикл может быть включен в первый путь/цикл, когда он достигнет этого узла. Это вложение циклов до сих пор неиспользуемых ребер повторяется до тех пор, пока не будут использованы все ребра, и таким образом мы получим эйлеров путь или эйлеров цикл, в котором используются все ребра.
Сколько стоит эта более быстрая версия?
Нужно помнить предыдущий путь/цикл, чтобы включить в него дополнительный цикл.
Пример:
2 4 / \ / \ 1---3---5
Пусть первый цикл будет 1-3-2-1. Узел 3 возникает в этом цикле и в неиспользуемом цикле 3-4-5-3. Вставляем его в первый цикл и получаем цикл 1-3-4-5-3-2-1. Неиспользуемых ребер больше нет, поэтому на этом алгоритм заканчивается, мы нашли цикл Эйлера.
Как вставить цикл с помощью нашего интерфейса?
Можно нажимать кнопку «Отменить» до тех пор, пока не дойдете до самого последнего узла, в котором есть использованные и неиспользованные ребра, как в узле 3 выше, а затем пройти через цикл 3-4-5-3 и продолжить работу с неиспользованными ребрами.
Если существует узел с нечетной степенью, нужно ли находить их оба, чтобы нарисовать первый путь от одного к другому?
Нет. Если найден только один, то можно начать путь с этого узла, и он автоматически окажется на другом узле нечетной степени, независимо от того, используются ли все ребра или нет.
Почему?
Потому что, когда кто-то доходит до узла четной степени, тогда используется нечетное количество присоединенных ребер.
Почему?
Каждый раз, когда кто-то приходил к узлу, он также покидал узел, поэтому используется четное количество ребер. Теперь мы приходим и используем одно ребро на четном узле. Таким образом, используется в общей сложности нечетное количество ребер на четном узле степени.
Чет − нечет = нечет, таким образом, остается нечетное количество неиспользуемых ребер. Нечетное число всегда не равно нулю, поэтому существует по крайней мере одно неиспользуемое ребро, которое можно использовать для выхода из этого узла. Следовательно, единица автоматически закончится на узле нечетной степени, независимо от того, были ли использованы все ребра или нет.
У вас есть предложение, как можно найти один узел с нечетными степенями?
Конечно, можно проверять степень каждого узла до тех пор, пока не будет найден узел с нечетной степенью. Вот способ без счета.
Можно выбрать любой узел. Если его степень нечетная, то он найден. Если нет, то с этого узла начинают рисовать цикл. Он будет заканчиваться либо на узле с нечетной степенью, затем будет найден узел с нечетной степенью, либо на начальном узле. Если это так, то мы игнорируем все используемые ребра и делаем это снова, т.е. выбираем узел и рисуем путь или цикл. Это продолжается до тех пор, пока не будет найден узел с нечетными степенями или пока не останется неиспользуемых ребер. Тогда все узлы имеют четную степень.
Что, если график похож на город с улицами с односторонним движением?
Граф с рёбрами, которые могут быть пройдены только в одном направлении, называется направленным графом. Следуя приведенной выше аргументации, следующие 2 утверждения являются правдоподобными.
Ориентированный граф допускает цикл Эйлера тогда и только тогда, когда для каждого узла число исходящих ребер равно числу входящих ребер.
Ориентированный граф допускает путь Эйлера тогда и только тогда, когда
• у одного узла на одно исходящее ребро больше, чем у входящих,
• один узел имеет на одно входящее ребро больше, чем исходящее ребро, и
• Все остальные ребра имеют одинаковое количество исходящих и входящих ребер.
Следите за обновлениями или подписывайтесь на них: