Graphentheorie

Definition

Basiswissen

Die Graphentheorie als Teilgebiet der Mathematik und Informatik^[1] beschäftigt sich mit sogenannten Knoten und Kanten. Knoten sind anschaulich gesehen Punkte, Kanten die geraden Verbindungen zwischen zwei Punkten^[3]. Ein typisches Beispiel für einen Graphen wäre eine Karte von verschiedenen Städten (die Knoten) sowie gerade Verbindungslinien zwischen je zwei Städen (die Kanten). Eine typische Frage wäre dann etwa, wie man den kürzesten Weg findet, auf dem jede Stadt genau einmal vorkommt^[4]. Siehe dazu auch Travelling Salesman ↗

Fußnoten

[1] Die Graphentheorie nach Wikipedia: "Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander." In: Der Artikel "Graphentheorie". Wikipedia. Abgerufen am 8. März 2024. Online: https://de.wikipedia.org/wiki/Graphentheorie

[2] Das Spektrum Lexikon der Mathematik betont zunächst die historischen Wurzeln der Graphentheorie: "James Joseph Sylvester benutzte 1878 in seiner Arbeit Chemistry and Algebra erstmalig das Wort „Graph“ als Abkürzung für graphische Darstellungen, wie sie in der Chemie benutzt werden. Eine erste Monographie über die Anfänge der Theorie der endlichen und unendlichen Graphen hat der ungarische Mathematiker Dénes König (1884-1944) Mitte der dreißiger Jahre des zwanzigsten Jahrhunderts geschrieben" In: Guido Walz: Spektrum Lexikon der Mathematik. Band 2: Eig bis Inn; 2001; ISBN: 3-8274-0437-7. Dort die Seiten 323 bis 327. Online: https://www.spektrum.de/lexikon/mathematik/graphentheorie/3591

[3] Zur Definition von einem Graphen: "Ein Graph G ist ein Paar (V, E), wobei V die Menge der Knoten (engl. vertices) des Graphen ist und E ⊆ [V]2, eine Teilmenge der zweielementigen Teilmengen von E, die Menge der Kanten (engl. edges) von G ist." In: Guido Walz: Spektrum Lexikon der Mathematik. Band 2: Eig bis Inn; 2001; ISBN: 3-8274-0437-7. Dort die Seiten 323 bis 327. Siehe auch Graph ↗

[4] Das ist das klassische Beispiel der Graphentheorie, im Deutschen bekannt als Problem des Handlungsreisenden, im Englischen der Travelling Salesman ↗