Изменить язык

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Войдите в Mathigon

или

Новый аккаунт     Сброс пароля     

Графики и Сети
Введение
Мосты Кенигсберга
Рукопожатия и знакомства
Планарные Графики
Раскраска карты
Проблема коммивояжера
Проблемы с расписанием
Графики в повседневной жизни

Поделиться

Сбросить прогресс

Это приведет к удалению вашего прогресса и данных чата для всех глав этого курса, и их нельзя будет отменить!

Глоссарий

Выберите одно из ключевых слов слева ...

Графики и СетиМосты Кенигсберга

Время чтения: ~20 min

Одним из первых математиков, который подумал о графах и сетях, был Леонард Эйлер . Эйлер был заинтригован старой проблемой города Кенигсберга у Балтийского моря.

Река Прегель делит Кенигсберг на четыре отдельные части, которые соединены семью мостами. Можно ли прогуляться по городу, пересекая все мосты ровно один раз, но не более одного раза? (Вы можете начать и закончить где угодно, не обязательно в том же месте.)

Попробуйте найти правильный маршрут, нарисовав на этих картах:

Map 1

Map 2

Map 3

Map 4

В случае Кенигсберга, кажется, невозможно найти правильный маршрут, но некоторые другие города работают. Эйлеру удалось найти простое правило, которое можно применить к любому городу, не прибегая к множеству возможностей - используя теорию графов.

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

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

На бумаге придумайте несколько разных графиков, а затем попытайтесь определить, какие из них можно нарисовать одним непрерывным штрихом.

Как и в случае с картами городов, мы находим, что некоторые графики возможны, а другие нет. Чтобы помочь нам понять почему, давайте пометим каждую вершину ее степенью . Затем мы можем по-разному раскрасить вершины и попытаться выявить закономерность:

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

Сравнивая эти числа для графов, которые возможны, и тех, которые невозможны, кажется, что граф можно нарисовать, если он . Это условие можно объяснить, если мы посмотрим только на одну вершину в графе:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

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

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

Archie