Czym jest teoria grafów i jak definiuje się graf jako taki?

W 1736 r. na podstawie pracy szwajcarskiego fizyka-matematyka Leonharda Eulera (1707-1783) zaobserwowano, że następstwo wierzchołków definiuje ścieżka jednak, jeśli wspomniana ścieżka składa się z różnych wierzchołków bez powtarzających się krawędzi, nazywana jest ścieżką lub ścieżką euleryjski; jeśli dodatkowo dochodzimy do punktu startowego, przechodząc każdą krawędź tylko raz, to mamy cykl (obwód) Eulera.

Wycena (APA)

Aleksander Barraza | Lip. 2022
Dyplom z fizyki

Ze swej strony graf definiujemy jako parę uporządkowaną (IDZIE) gdzie v wyznacza (niepusty) zbiór wszystkich wierzchołków lub węzłów grafu, podczas gdy A wyznacza zbiór (może być pusty) wszystkich krawędzi lub linii łączących wierzchołki grafu. Elementy zestawu A można wyznaczyć jako nieuporządkowaną parę {v, w} gdzie v i w są elementami (węzłami lub wierzchołkami) v, w ten sposób mówi się, że v i w są sąsiednimi wierzchołkami (połączone są krawędzią).

Teoria grafów wynika z odpowiedzi Eulera na problem popularnej pomysłowości, która zastanawiała się, jak przekroczyć siedem mostów, które połączyła dwie wyspy gminy Königsberg (wówczas część Niemiec, a obecnie Kaliningrad, w Rosji), między nimi oraz z lądem stałym bez użycia dwóch razy ten sam most i dotarcie do punktu początkowego (znajdującego się na stałym lądzie) cokolwiek to może być, ustalając, że w tym przypadku ostatecznie nie mógłby.

Problem siedmiu mostów Królewca

Euler zamodelował Królewiec jako wykres, w którym każdy punkt (wierzchołek lub węzeł) reprezentuje most, a każda linia (krawędź) ścieżkę na lądzie:

Jakie jest rozwiązanie tego problemu?

nie ma jednego rozwiązanie spełnia narzucone warunki, ponieważ, jak pokazał Euler, wierzchołki nie są równe, czyli parzysta liczba linii nie wpływa na każdy punkt _[3]. Nie wydaje się, abyśmy mogli wiele zrobić ze strukturą zdefiniowaną tak prosto, jak to często bywa w matematyka, Czasami rzeczy nie są takie, jakimi się wydają. Tym samym jeden z najbardziej płodnych, przekrojowych i interdyscyplinarnych obszarów _[4] wiedzy ludzkiej, teoria grafów.

Wykresy Eulera czy z trajektorią Eulera?

Wszystkie poniższe wykresy mają ścieżki Eulera _[5]. Czy wszystkie mają cykle Eulera?

Weźmy trzeci wykres:

Ponumerujmy wierzchołki:

Widzimy więc, że ścieżka określona przez sekwencję {3,4,6,2,1,3,7,6,5,4,2} jest ścieżką Eulera, ponieważ przechodzi przez cały wykres bez powtarzających się krawędzi, ale nie jest to cykl Eulera, ponieważ nie osiąga punktu początkowego. Co by się stało, gdybyśmy inaczej ponumerowali wierzchołki? Niewiele, poza tym, że teraz ścieżkę wyznaczałaby inna sukcesja. Co by się stało, gdybyśmy poszli innymi ścieżkami niż ta, którą proponowaliśmy w naszym pierwotnym rozwiązaniu? Odpowiedź na to pytanie jest nieco bardziej skomplikowana i obejmuje algorytmy, którymi zwykle zachwycają się inżynierowie oprogramowania. programowanie.

Aby uzyskać bardziej rygorystyczny dowód tego, co jest tutaj ujawnione, musimy odwołać się do następującego wyniku:

"Być G połączony wykres _[6]. W takim razie tak G mieć okrążenie Euler, stopień każdego wierzchołka jest parzysty, natomiast jeśli G ma ścieżkę Eulera, G ma dokładnie dwa nieparzyste wierzchołki _[7] (dokładnie wierzchołki, w których zaczyna się i kończy ścieżka)".

Możemy wtedy zweryfikować, że w rzeczywistości na wykresie, który bierzemy, tylko wierzchołki 3 i 6 mają nieparzysty stopień (to wystąpiłaby nawet gdyby numeracja wierzchołków była inna), dlatego wspomniany wykres ma ścieżkę euleryjski _[8]. Dla pozostałych grafów możemy postępować w analogiczny sposób i zweryfikować, czy rzeczywiście mają ścieżki i Cykle Eulera, czyli inaczej mówiąc, czy możemy narysować takie wykresy bez podnoszenia ołówka i powtarzania? linie? Odpowiedź na to pytanie można wywnioskować z tego, co już zostało wyjaśnione do tej pory, jest to jednak ćwiczenie ciekawe pod względem sprawności ruchowej, pomysłowości i cierpliwości zapraszam czytelnika do odnalezienia i narysowania wykresów 6 lub więcej wierzchołki z trajektoria Eulera.

Czy istnieją inne rodzaje wykresów? Czy teoria grafów ma zastosowanie w „rzeczywistym” świecie?

Te wykresy, które bardzo pokrótce przejrzeliśmy, są tylko jednym z wielu rodzajów wykresów, które znajdujemy w teorii grafów. Znajdziemy też grafy, takie jak drzewa, bardzo reprezentatywne w zbiorach, w których ich elementy można klasyfikować w hierarchiach oraz w obliczeniach rachunkowych i prawdopodobieństwo_[9], digrafy, grafy Hamiltona _[10]itp.

Obraz modeli graficznych i sieci w Psycho., Ruiz, Ana María.

Te zagadki, jeśli chcemy je tak nazwać, mają ogromne zastosowanie w dzisiejszym świecie, w sytuacjach tak różnych, jak: biologia molekularny _[11], przetwarzanie danych_[12], telekomunikacja _[13] i analiza sieci _[14]. Warto więc zapytać: czy nie jest to przynajmniej ciekawe, że problem prawie banalny stanie się jednym z najciekawszych i najbardziej rzucających się w oczy wyników matematyki? Być może do tego potrzebny był wkład jednego z najznamienitszych umysłów ludzkości.