Что такое теория графов и как определяется граф?

В 1736 году на основе работы швейцарского физика-математика Леонарда Эйлера (1707-1783) было замечено, что последовательность вершин определяет путь, однако, если указанный путь состоит из разных вершин без повторяющихся ребер, он называется путем или путем эйлерова; если дополнительно мы приходим в исходную точку, обходя каждое ребро только один раз, то мы имеем эйлеров цикл (контур).

Цитата (АПА)

Александр Барраза | июл. 2022
Степень по физике

Со своей стороны, мы определяем граф как упорядоченную пару (ИДЕТ) куда в обозначает (непустой) набор всех вершин или узлов графа, а А обозначает множество (может быть пустым) всех ребер или линий, соединяющих вершины графа. Элементы набора А можно обозначить как неупорядоченную пару {v, w}, где v и w — элементы (узлы или вершины) в, тогда говорят, что v и w — смежные вершины (они соединены ребром).

Теория графов возникла из ответа, данного Эйлером на народную изобретательность, которая заключалась в том, как пересечь семь мостов, которые соединил два острова сообщества Кенигсберг (в то время часть Германии, а в настоящее время Калининград, в России), между ними и с материком без использования двух раз тот же мост и прибытие в исходную точку (находящуюся на материке), какой бы она ни была, определяя, что в данном случае, в конечном счете, нет мог.

Проблема семи мостов Кенигсберга

Эйлер смоделировал Кенигсберг как граф, в котором каждая точка (вершина или узел) представляет собой мост, а каждая линия (ребро) — путь на суше:

Каково решение этой проблемы?

нет ни одного решение что удовлетворяет наложенным условиям, так как, как показал Эйлер, вершины не четной степени, то есть четное число прямых не влияет на каждую точку _[3]. Однако не похоже, что мы можем многое сделать со структурой, определенной так просто, как это часто бывает в математика, Иногда вещи не то, чем кажутся. Таким образом, одна из самых плодовитых, сквозных и междисциплинарных областей _[4] человеческого знания, теория графов.

Эйлеровы графы или с эйлеровой траекторией?

Все следующие графы имеют эйлеровы пути _[5]. Все ли они имеют эйлеровы циклы?

Возьмем третий график:

Пронумеруем вершины:

Мы видим, что путь, определяемый последовательностью {3,4,6,2,1,3,7,6,5,4,2}, является эйлеровым путем, поскольку он проходит через весь граф без повторяющихся ребер, но это не эйлеров цикл, так как он не достигает начальной точки. Что было бы, если бы мы пронумеровали вершины по-другому? Немного, за исключением того, что теперь путь будет определяться другой последовательностью. Что произошло бы, если бы мы пошли по пути, отличному от предложенного в нашем первоначальном решении? На этот вопрос немного сложнее ответить, и он включает в себя алгоритмы, которыми обычно восхищаются разработчики программного обеспечения. программирование.

Для более строгого доказательства изложенного здесь мы должны сослаться на следующий результат:

"Быть грамм связный граф _[6]. Тогда да грамм есть схема Эйлера степень каждой вершины четная, а если грамм имеет эйлеров путь, G имеет ровно две вершины нечетной степени _[7] (именно вершины, где путь начинается и заканчивается)".

Тогда мы можем убедиться, что на самом деле в взятом нами графе только вершины 3 и 6 имеют нечетную степень (это произошло бы, даже если бы нумерация вершин была другой), поэтому указанный граф имеет путь эйлеров _[8]. Для остальных графов мы можем действовать аналогичным образом и проверить, действительно ли они имеют пути и Эйлеровы циклы, или, другими словами, можем ли мы нарисовать такие графики, не беря карандаш и не повторяя линии? Ответ на этот вопрос можно вывести из того, что уже было объяснено до сих пор, однако это представляет собой упражнение. интересно с точки зрения мелкой моторики, сообразительности и терпения, предлагаю читателю найти и нарисовать графики из 6 и более вершины с траектория Эйлера.

Существуют ли другие типы графиков? Есть ли у теории графов приложения в «реальном» мире?

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

Изображение графических моделей и сетей в Psycho. Руис, Ана Мария.

Эти загадки, если мы хотим их так назвать, имеют огромную применимость в современном мире, в таких разнообразных ситуациях, как: биология молекулярный _[11], вычисления_[12], телекоммуникации _[13] и сетевой анализ _[14]. Стоит спросить тогда: не любопытно ли, что проблема почти банальный окажется в конечном итоге одним из самых интересных и заметных результатов математики? Возможно, для этого был необходим вклад одного из самых прославленных умов человечества.