Was ist Graphentheorie und wie wird ein Graph als solcher definiert?

1736 wurde basierend auf der Arbeit des Schweizer Physiker-Mathematikers Leonhard Euler (1707-1783) beobachtet, dass eine Folge von Scheitelpunkten definiert ein Weg, aber wenn dieser Weg aus verschiedenen Eckpunkten ohne sich wiederholende Kanten besteht, wird er ein Weg oder Weg genannt Euler; wenn wir zusätzlich am Startpunkt ankommen und jede Kante nur einmal durchlaufen, dann haben wir einen Eulerschen Kreis (Kreis).

Zitat (APA)

Alexander Baraza | Juli. 2022
Abschluss in Physik

Wir seinerseits definieren einen Graphen als ein geordnetes Paar (GEHT) wo v bezeichnet die (nicht leere) Menge aller Ecken oder Knoten eines Graphen, während EIN bezeichnet die Menge (kann leer sein) aller Kanten oder Linien, die die Eckpunkte eines Graphen verbinden. Die Elemente des Sets EIN kann als ungeordnetes Paar {v, w} bezeichnet werden, wobei v und w Elemente (Knoten oder Eckpunkte) von sind v, so sagt man dann, dass v und w benachbarte Ecken sind (sie sind durch eine Kante verbunden).

Die Graphentheorie ergibt sich aus der Antwort von Euler auf ein Problem des populären Einfallsreichtums, das sich fragte, wie man die sieben Brücken überquert schloss sich zwei Inseln der Gemeinde Königsberg (damals Teil Deutschlands und derzeit Kaliningrad in Russland) zwischen ihnen und mit dem Festland an, ohne zwei zu verwenden mal die selbe brücke und am startpunkt angekommen (auf dem festland gelegen) was auch immer das sein mag, bestimmt in diesem fall schlussendlich nein könnte.

Das Problem der sieben Brücken von Königsberg

Euler modellierte Königsberg als Graphen, in dem jeder Punkt (Eckpunkt oder Knoten) eine Brücke und jede Linie (Kante) einen Weg an Land darstellt:

Was ist die Lösung für dieses Problem?

es gibt keinen Lösung das die auferlegten Bedingungen erfüllt, da, wie Euler gezeigt hat, die Ecken nicht von geradem Grad sind, dh eine gerade Anzahl von Linien wirkt sich nicht auf jeden Punkt aus _[3]. Es scheint jedoch nicht so, als könnten wir mit einer so einfach definierten Struktur viel anfangen, wie dies häufig der Fall ist in Mathematik, Manchmal sind die Dinge nicht so, wie sie scheinen. Somit einer der produktivsten, transversalsten und interdisziplinärsten Bereiche _[4] des menschlichen Wissens, Graphentheorie.

Eulersche Graphen oder mit Eulerscher Trajektorie?

Die folgenden Graphen haben alle Eulersche Pfade _[5]. Haben sie alle Eulersche Zyklen?

Nehmen wir den dritten Graphen:

Nummerieren wir die Scheitelpunkte:

Wir sehen dann, dass der durch die Folge {3,4,6,2,1,3,7,6,5,4,2} definierte Pfad ein Eulerscher Pfad ist, da er durchläuft den gesamten Graphen ohne Kantenwiederholung, ist aber kein Eulerkreis, da er den Startpunkt nicht erreicht. Was wäre passiert, wenn wir die Scheitelpunkte anders nummeriert hätten? Nicht viel, außer dass jetzt der Weg durch eine andere Sukzession bestimmt würde. Was wäre passiert, wenn wir andere Wege gegangen wären als in unserer ursprünglichen Lösung vorgeschlagen? Diese Frage ist etwas komplexer zu beantworten und beinhaltet Algorithmen, mit denen Softwareingenieure normalerweise zufrieden sind. Programmierung.

Für einen strengeren Beweis dessen, was hier aufgedeckt wird, müssen wir uns auf das folgende Ergebnis beziehen:

"Sei G ein zusammenhängender Graph _[6]. Dann ja G haben eine Schaltkreis Euler, der Grad jeder Ecke ist gerade, während if G einen Euler-Weg hat, hat G genau zwei Ecken ungeraden Grades _[7] (genau die Eckpunkte, an denen der Pfad beginnt und endet)".

Wir können dann überprüfen, dass in dem von uns genommenen Graphen tatsächlich nur die Eckpunkte 3 und 6 einen ungeraden Grad haben (dies auftreten würde, selbst wenn die Numerierung der Scheitelpunkte unterschiedlich gewesen wäre), daher hat der Graph einen Pfad Eulerisch _[8]. Für die restlichen Graphen können wir analog vorgehen und überprüfen, ob sie tatsächlich Pfade und haben Eulersche Zyklen, oder anders ausgedrückt, können wir solche Graphen zeichnen, ohne den Stift in die Hand zu nehmen und zu wiederholen Linien? Die Antwort auf diese Frage lässt sich aus dem bisher Erläuterten ableiten, stellt jedoch eine Übung dar Interessant in Bezug auf Feinmotorik, Einfallsreichtum und Geduld, lade ich den Leser ein, Diagramme von 6 oder mehr zu finden und zu zeichnen Ecken mit Flugbahn Eulersch.

Gibt es andere Arten von Diagrammen? Hat die Graphentheorie Anwendungen in der „realen“ Welt?

Diese Graphen, die wir kurz betrachtet haben, sind nur eine der vielen Arten von Graphen, die wir in der Graphentheorie finden. Wir können auch Diagramme wie Bäume finden, die sehr repräsentativ in Mengen sind, in denen ihre Elemente in Hierarchien und in Zählberechnungen klassifiziert werden können Wahrscheinlichkeit_[9], Digraphen, Hamiltonsche Graphen _[10], etc.

Image of Graphic Models and Networks in Psycho., von Ruiz, Ana María.

Diese Rätsel, wenn wir sie so nennen wollen, haben eine enorme Anwendbarkeit in der heutigen Welt, in so unterschiedlichen Situationen wie: Biologie molekular _[11], rechnen_[12], Telekommunikation _[13] und Netzwerkanalyse _[14]. Es lohnt sich also zu fragen: Ist es nicht zumindest merkwürdig, dass ein Problem eines fast banal wird am Ende eines der interessantesten und auffälligsten Ergebnisse der Mathematik sein? Vielleicht war dazu der Beitrag eines der berühmtesten Köpfe der Menschheit notwendig.