Graphentheorie
Die Graphentheorie untersucht Graphen – Strukturen von Knoten, die durch Kanten verbunden sind – als mathematische Modelle paarweiser Beziehungen und Netzwerke.
Definition
Das mathematische Studium von Graphen, die Mengen von Knoten zusammen mit einer Menge von Kanten sind, wobei jede Kante ein Paar von Knoten verbindet, und der Eigenschaften, die unter der Struktur dieser Verbindungen invariant sind.
Scope
Der Bereich umfasst die Struktur, Eigenschaften und Parameter von Graphen: Konnektivität, Wege und Zyklen, Bäume, Planarität, Färbungen, Matchings und Flüsse, sowie extremale und probabilistische Fragen darüber, wie Grapheneigenschaften einander einschränken. Sie ist zentral für die diskrete Mathematik und liefert die Sprache für Netzwerke in der Informatik, der Operations Research sowie den Natur- und Sozialwissenschaften.
Sub-topics
Core questions
- Welche strukturellen Eigenschaften ergeben sich aus der Konnektivität, der Gradfolge oder der Zyklenstruktur eines Graphen?
- Wann kann ein Graph in der Ebene kreuzungsfrei gezeichnet oder mit wenigen Farben gefärbt werden?
- Wie groß oder dicht kann ein Graph sein, während eine gegebene Teilstruktur vermieden wird?
- Wie ermöglichen Wege, Matchings und Flüsse eine Optimierung über ein Netzwerk?
Key concepts
- Knoten, Kanten und Grad
- Konnektivität und Komponenten
- Wege, Zyklen und Bäume
- Planarität
- Graphenfärbung
- Matchings und Flüsse
Clinical relevance
Graphen modellieren Kommunikations- und Transportnetzwerke, soziale und biologische Interaktionsnetzwerke, Schaltkreis- und Abhängigkeitsstrukturen sowie Planungsprobleme, was die Graphentheorie zu einem grundlegenden Werkzeug in der Informatik und Operations Research macht.
History
Die Graphentheorie geht auf Eulers Lösung des Königsberger Brückenproblems im Jahr 1736 zurück und reifte im 20. Jahrhundert durch Arbeiten zu Färbung, Konnektivität sowie die probabilistischen und strukturellen Methoden von Erdos, Tutte und anderen.
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- Was ist der Unterschied zwischen einem Graphen und einem Netzwerk?
- Ein Graph ist das abstrakte mathematische Objekt von Knoten und Kanten; ein Netzwerk bezieht sich in der Regel auf einen Graphen, der mit zusätzlichen Daten wie Gewichten, Kapazitäten oder Richtungen ausgestattet ist, die ein reales System modellieren.
- Warum war das Königsberger Brückenproblem wichtig?
- Eulers Beweis, dass kein Weg jede der sieben Brücken genau einmal überqueren konnte, abstrahierte das Problem auf Knoten und Kanten und begründete damit die Graphentheorie und Topologie.