Лучше всего представить GT, пожалуй, так, как это сделала моя лектор г-жа Радика - с помощью проблемы Конисбергского моста.
Семь мостов Кенигсберга
Семь мостов Кенигсберга - исторически известная математическая проблема. Это так.
Город Кенигсберг в Пруссии (ныне Калининград, Россия) располагался по обе стороны реки Прегель. В него входили два крупных острова - Кнайпхоф и Ломсе. Эти массивы суши были связаны друг с другом или с двумя материковыми частями города семью мостами, как показано на реальной карте выше.
Постановка проблемы: спланируйте маршрут через город, который будет пересекать каждый из этих семи мостов только один раз.
Условия:
Это не разрешено
- Добраться до острова или материкового берега, кроме как через один из мостов
- Доступ к любому мосту без перехода на другой его конец
Решение. Оно находится в конце блога. Дайте ему несколько минут подумать, амиго.
При чем здесь теория графов?
Что ж, Эйлер заметил, что ...
1. Выбор сухопутного маршрута в пределах каждого массива суши не имеет значения.
Это означало, что проблему не нужно рассматривать фотографически или на карте, ее можно выразить в абстрактной форме.
Это своего рода означает, что вы можете отбросить карту, нарисовать каждый участок суши в виде точки или узла, а мосты - в виде линий или кривых. Это также означает, что вы можете согнуть этот рисунок любым способом (не разрывая линий / кривых и не удаляя ничего), и проблема и решение останутся прежними!
Это преобразует нашу проблему, как показано ниже
2. Если войти по мосту, нужно выйти по мосту.
Эйлер заметил, что, за исключением конечных точек прогулки, когда кто-то входит в вершину по мосту, он должен выходить из вершины по мосту. То есть количество раз, когда человек входит в нетерминальную вершину, равно количеству раз, когда он выходит из нее. Теперь, если по каждому мосту можно пройти только один раз, то для каждой вершины (нетерминальных) количество мостов, соприкасающихся с этим массивом суши, должно быть четным, то есть степень каждого узла должна быть даже (половина из них навстречу, половина от земли)
Он пришел к выводу, что необходимым условием для обхода желаемой формы является то, чтобы граф был связным и имел ровно ноль или два массива суши нечетной степени. Остальные должны быть четной степени. (Степень относится к количеству соединенных с ней мостов)
Но в нашей задаче степени a, b, c и d равны 3. Все узлы имеют нечетные степени, что означает, что решение невозможно.
Нет решения! Немного разочаровывает, да, но эта проблема заложила основу широко известной теории графов. Однако математикам понадобилось более 150 лет, чтобы представить себе график.
Так что же такое граф?
Некоторые определения:
Граф - это упорядоченная тройка G = (V (G), E (G), ψ (G)), состоящая из непустого множества V (G) вершин , множество E (G) ребер и функция инцидентности ψ (G), которая сопоставляет каждому ребру G неупорядоченную пару вершин.
Определение означает, что у вас может быть граф без ребер и только с узлами, но обратное не будет графом.
Чтобы связать с проблемой, участки суши, которые мы видели в пункте 1, являются вершинами, мосты - ребрами, функция отображения обоих будет вашим ψ (G), а вся фигура - вашим графиком.
Простым графом будет граф, в котором нет ни петель (ребро начинается и заканчивается в одном узле), ни параллельных ребер (ребра, которые имеют общие те же узлы).
Граф был бы тривиальным, если бы в нем был только один изолированный узел.
Две вершины называются смежными, если они являются конечными вершинами одного и того же ребра.
Когда вершина v является конечной вершиной некоторого ребра e, они говорят, что они инцидентны друг другу.
Вот и все, ребята. Так была впервые задумана теория графов. Это простое введение в GT. Увидимся в следующем блоге, чтобы узнать больше об этой прекрасной теме!
