Що таке теорія графів і як визначається граф як такий?

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

Цитата (APA)

Олександр Барраза | лип. 2022
Диплом фізика

Зі свого боку, ми визначаємо граф як упорядковану пару (ЙДЕ) де v позначає (непорожній) набір усіх вершин або вузлів графа, тоді як А позначає набір (може бути порожнім) усіх ребер або ліній, які з’єднують вершини графа. Елементи набору А можна позначити як невпорядковану пару {v, w}, де v і w є елементами (вузлами або вершинами) v, таким чином тоді кажуть, що 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]. Тоді варто запитати: чи не принаймні цікаво, що проблема майже банальний чи стане одним із найцікавіших і найяскравіших результатів математики? Можливо, для цього був необхідний внесок одного з найвидатніших умів людства.