imported>Mathze: Die letzte Textänderung von ~2025-63539-0 wurde verworfen und die Version 255090757 von Kreuz Elf wiederhergestellt.

2025-09-17T09:27:50Z

Die letzte Textänderung von ~2025-63539-0 wurde verworfen und die Version 255090757 von Kreuz Elf wiederhergestellt.

Neue Seite

[[Datei:6n-graf.svg|mini|Ungerichteter Graph mit sechs Knoten]]
Die '''Graphentheorie''' (seltener auch '''Grafentheorie''') ist ein Teilgebiet der [[Diskrete Mathematik|diskreten Mathematik]] und der [[Theoretische Informatik|theoretischen Informatik]]. [[Graphentheorie#Betrachteter Gegenstand|Betrachtungsgegenstand]] der Graphentheorie sind [[Graph (Graphentheorie)|Graphen]] ([[Menge (Mathematik)|Mengen]] von [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]]), deren [[Eigenschaft]]en und ihre [[Vernetzung|Beziehungen]] zueinander.

Graphen sind mathematische [[Modell]]e für netzartige Strukturen in Natur und Technik (wie [[Soziales Netzwerk (Systemtheorie)|soziale Strukturen]], [[Straßennetz]]e, [[Verwandtschaftsbeziehung]]en, [[Computernetz]]e, [[elektrische Schaltung]]en, [[Versorgungsnetz]]e oder [[Molekül]]e). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Es verbleiben jedoch viele allgemeingültige [[Graphentheorie#Grapheigenschaften|Graphen-Eigenschaften]], die bereits auf dieser Abstraktionsstufe untersucht werden können und sich in allgemeingültigen Aussagen ([[:Kategorie:Satz (Graphentheorie)|Sätze der Graphentheorie]]) wiederfinden.<ref>{{Literatur |Autor=Peter Tittmann |Titel=Graphentheorie. Eine anwendungsorientierte Einführung |Auflage=3., aktualisierte |Ort=München |ISBN=978-3-446-46052-2 |Seiten=1}}</ref> Ein Beispiel hierfür ist das [[Handschlaglemma]], wonach die Summe der [[Grad (Graphentheorie)|Knotengrade]] in einem Graphen stets gerade ist (in der nebenstehenden Abbildung: 14).

Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung [[Graphentheorie#Probleme|graphentheoretischer Probleme]] oft auf [[Algorithmus|Algorithmen]] basiert, ist die Graphentheorie auch in der [[Informatik]], insbesondere der [[Komplexitätstheorie]], von großer Bedeutung. Insbesondere lassen sich viele [[Optimierungsproblem|Aufgaben]] der [[Kombinatorische Optimierung|kombinatorischen Optimierung]] in der Sprache der Graphentheorie formulieren und umgekehrt graphentheoretische Probleme als [[Ganzzahlige lineare Optimierung|lineare ganzzahlige Optimierungsprobleme]] [[Optimierungsmodell|modellieren]].<ref>{{Literatur |Autor=Bernhard Korte, Jens Vygen |Titel=Combinatorial Optimization |Sammelwerk=Algorithms and Combinatorics |Datum=2002 |ISSN=0937-5511 |DOI=10.1007/978-3-662-21711-5 |Online=https://www.mathematik.uni-muenchen.de/~kpanagio/KombOpt/book.pdf |Abruf=2024-01-16}}</ref> Die Untersuchung von Graphen ist auch Inhalt der [[Netzwerkforschung|Netzwerktheorie]]. Graphen werden insbesondere durch die [[Datenstruktur]]en [[Adjazenzmatrix]], [[Inzidenzmatrix]] oder [[Adjazenzliste]] repräsentiert.

== Geschichte ==
[[Datei:Konigsberg bridges.png|mini|Das [[Königsberger Brückenproblem]] im Stadtplan …]]
[[Datei:Königsberg graph.svg|mini|… und abstrakt als Graph (Orte durch Knoten, Brücken durch Kanten repräsentiert)]]

Ein von der Graphentheorie unabhängiger Vorläufer in der [[Antike]] war die Methode [[Dihairesis]], mit deren Hilfe man (nur teilweise grafisch) zoologische, musikwissenschaftliche und andere Begriffe hierarchisierte. Es entstanden so frühe Systematiken innerhalb verschiedener Wissensgebiete.

Die Anfänge der Graphentheorie gehen bis in das Jahr 1736 zurück. Damals publizierte [[Leonhard Euler]] eine Lösung für das [[Königsberger Brückenproblem]]. Die Frage war, ob es einen Rundgang durch die Stadt [[Königsberg (Preußen)]] gibt, der jede der sieben Brücken über den Fluss [[Pregel]] genau einmal benutzt. Euler konnte eine für dieses Problem nicht erfüllbare notwendige Bedingung angeben und so die Existenz eines solchen Rundganges verneinen.

1852 bemerkte der Mathematiker und Botaniker [[Francis Guthrie]], dass vier Farben reichen, um eine Landkarte so zu färben, dass zwei aneinander grenzende Länder stets unterschiedlich gefärbt sind. Viele Mathematiker beschäftigten sich mit diesem [[Graphentheorie#Färbung|Färbungsproblem]]. Es dauerte jedoch bis 1976, bis der [[Vier-Farben-Satz]] mittels Computer bewiesen werden konnte.<ref>{{Literatur |Autor=Peter Tittmann |Titel=Graphentheorie. Eine anwendungsorientierte Einführung |Auflage=3., aktualisierte |Ort=München |ISBN=978-3-446-46052-2 |Seiten=76}}</ref> Erst 1997 stellten [[Neil Robertson (Mathematiker)|Neil Robertson]], Daniel Sanders, [[Paul Seymour (Mathematiker)|Paul Seymour]], [[Robin Thomas (Mathematiker)|Robin Thomas]] einen neuen Beweis vor.<ref>{{Literatur |Autor=Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas |Titel=The Four-Colour Theorem |Hrsg= |Sammelwerk=Journal of Combinatorial Theory, Series B |Band=70 |Nummer=1 |Auflage= |Verlag= |Ort= |Datum=1997 |ISBN= |ISSN=0095-8956 |Seiten=2–44}}</ref>

Der Begriff ''Graph'' wurde in Anlehnung an graphischen Notationen chemischer Strukturen erstmals 1878 von dem Mathematiker [[James Joseph Sylvester]] verwendet.<ref name="Sylvester1878">James Joseph Sylvester: ''Chemistry and Algebra.'' In: ''Nature.'' Band 17, 1878, S. 284.</ref> Als weiterer Begründer der frühen Graphentheorie gilt [[Arthur Cayley]]. Eine der ersten Anwendungen waren chemische [[Konstitutionsformel]]n.<ref>{{Literatur |Autor=Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson |Titel=Graph Theory 1736–1936 |Verlag=Oxford University Press |Jahr=1999 |ISBN=0198539169}}</ref><ref>Arthur Cayley: ''Chemical Graphs''. In: ''Philosophical Magazine''. Band 47, 1874, S. 444–446.</ref> (Siehe auch [[Chemische Graphentheorie]] und [[#Literatur|Literatur]]: Bonchev/Rouvray, 1990). Das erste Lehrbuch zur Graphentheorie erschien 1936 von [[Dénes Kőnig]].<ref>Dénes Kőnig: ''Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe.'' Akademische Verlagsgesellschaft, Leipzig 1936.</ref>

In der zweiten Hälfte des 20. Jahrhunderts hat [[William Thomas Tutte]] maßgeblich an der Weiterentwicklung der Graphentheorie gearbeitet und dieses Teilgebiet der Mathematik stark geprägt.

== Teilgebiete der Graphentheorie ==
Teilgebiete der Graphentheorie sind:

* '''[[Algorithmische Graphentheorie]]''': Dieses Teilgebiet beschäftigt sich mit auf Graphen anwendbaren Algorithmen [[Liste von Algorithmen#Graphentheorie|(Liste der Graphalgorithmen)]].
* '''[[Chemische Graphentheorie]]''': Die chemische Graphentheorie gehörte zu den ersten Anwendungen der Strukturerkenntnisse und wendet diese auf chemische Molekülstrukturen an.
* '''[[Extremale Graphentheorie]]''': Die extremale Graphentheorie untersucht, welche Graphen einer gegebenen Klasse einen bestimmten Graphenparameter maximieren oder minimieren.
* '''[[Geometrische Graphentheorie]] und [[Topologische Graphentheorie]]''': Diese Teilgebiete betten Graphen in Ebenen und anderen geometrischen Objekten ein.
* '''[[Netzwerktheorie (Soziologie)|Netzwerkforschung]]''': In der Netzwerkforschung werden [[Komplexes Netzwerk|komplexe Netzwerke]] empirisch untersucht. Sie findet Anwendungen in Disziplinen wie [[Biologie]], [[Wirtschaftswissenschaft]]en und [[Soziologie]].
* '''Probabilistische Graphentheorie''': Mittels [[Zufallsgraph]] können Eigenschaften für beliebig große Graphen nachgewiesen werden.
* '''[[Spektrale Graphentheorie]]''' (auch algebraische Graphentheorie): Die spektrale Graphentheorie untersucht Graphen anhand ihrer [[Adjazenzmatrix|Adjazenzmatrizen]] und [[Laplace-Matrix|Laplace-Matrizen]] durch die Analyse von [[Eigenwerte]]n, [[Eigenvektoren]] und [[Charakteristisches Polynom|charakteristischen Polynomen]]. Ungerichtete Graphen besitzen symmetrische Adjazenzmatrizen und deshalb reelle [[Eigenwertproblem|Eigenwerte]]. Alle Eigenwerte zusammengenommen werden als [[Spektrum (Operatortheorie)|Spektrum des Graphen]] bezeichnet. Während die Adjazenzmatrix von der Knotensortierung abhängig ist, ist das [[Spektrum (Graphentheorie)|Spektrum]] davon unabhängig.

== Betrachteter Gegenstand ==
{{Hauptartikel|Graph (Graphentheorie)}}[[Datei:GraphentheorieArtikulationUndBrücke.PNG|mini|Graph mit Artikulation und Brücke]]In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken oder Punkte genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine [[Menge (Mathematik)|Menge]] von genau zwei Knoten. Sie gibt an, ob zwei [[Knoten (Graphentheorie)|Knoten]] miteinander in Beziehung stehen, bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind. Zwei Knoten, die durch eine Kante verbunden sind, heißen [[Nachbarschaft (Graphentheorie)|benachbart]] oder adjazent''.'' Wenn die Kanten statt durch Mengen durch [[geordnetes Paar|geordnete Paare]] von Knoten angegeben sind, spricht man von ''gerichteten Graphen''. In diesem Falle unterscheidet man zwischen der Kante (''a'',''b'') – als Kante von Knoten ''a'' zu Knoten ''b'' – und der Kante (''b'',''a'') – als Kante von Knoten ''b'' zu Knoten ''a''. Knoten und Kanten können auch mit Farben (formal mit [[Natürliche Zahl|natürlichen Zahlen]]) oder Gewichten (d. h. [[Rationale Zahl|rationalen]] oder [[Reelle Zahl|reellen Zahlen]]) versehen werden. Man spricht dann von knoten- bzw. kanten[[Färbung (Graphentheorie)|gefärbten]] oder -[[Gewicht (Graphentheorie)|gewichteten]] Graphen.

Komplexere Graphentypen sind:
* ''Multigraphen'', bei denen die Kantenmenge eine [[Multimenge]] ist
* ''Hypergraphen'', bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von ''Hyperkanten'')
* ''[[Petri-Netz]]e'' mit zwei Arten von Knoten

Ist die Menge der Knoten endlich, spricht man von ''endlichen Graphen'', ansonsten von ''[[Unendlicher Graph|unendlichen Graphen]]''.

=== Grapheigenschaften ===
[[Datei:Pseudoforest.svg|alternativtext=|mini|Zusammenhangskomponenten]]
Graphen können verschiedene Eigenschaften haben. So kann ein Graph

* [[Zusammenhang (Graphentheorie)|zusammenhängend]] (im Allgemeinen [[K-Zusammenhang|k-zusammenhängend]]),
* [[Bipartiter Graph|bipartit]] (im Allgemeinen [[K-partiter Graph|k-partit]]),
* [[Planarer Graph|planar]],
* [[Eulerscher Graph|eulersch]] oder [[Hamiltonscher Graph|hamiltonisch]] sein.

Es kann nach der Existenz spezieller [[Teilgraph]]en oder [[Minor (Graphentheorie)|Minoren]] gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel [[Knotenzahl]], [[Kantenzahl]], [[Minimalgrad]], [[Maximalgrad]], [[Taillenweite (Graphentheorie)|Taillenweite]], [[Durchmesser (Graphentheorie)|Durchmesser]], [[Knotenzusammenhangszahl]], [[Kantenzusammenhangszahl]], [[Bogenzusammenhangszahl]], [[chromatische Zahl]], [[Knotenüberdeckungszahl]] ([[Faktor (Graphentheorie)|Faktor]]), [[Unabhängigkeitszahl]] ([[Stabilitätszahl]]) oder [[Cliquenzahl]]. Zwei Graphen können [[Isomorphie von Graphen|isomorph]] (strukturell gleich) oder [[Automorphismus|automorph]] zueinander sein.

Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl, welche wiederum nie größer als der Minimalgrad des betrachteten Graphen ist. In [[Ebener Graph|ebenen Graphen]] ist die Färbungszahl immer kleiner als fünf. Diese Aussage ist auch als der [[Vier-Farben-Satz]] bekannt.[[Datei:Directed graph, cyclic.svg|mini|Gerichteter zyklischer Graph]]Einige der aufgezählten Grapheneigenschaften sind relativ schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von [[Heuristik|heuristischen Verfahren]] zu sinnvollen Näherungslösungen führen.

=== Graphenklassen ===
[[Datei:GraphBipartit.png|mini|Bipartiter Graph]]
Grundsätzlich werden Graphen in [[Gerichteter Graph|gerichtete]] und [[Ungerichteter Graph|ungerichtete]] Graphen unterteilt.

Aufgrund des [[Zusammenhang (Graphentheorie)|Zusammenhangs]] unterscheidet man:

* azyklische Graphen: [[Weg (Graphentheorie)|Weg (oder Pfad)]], [[Wald (Graphentheorie)|Wald]], [[Baum (Graphentheorie)|Baum]], DAG (directed acyclic graph)
* zyklische Graphen, beispielsweise: [[Zyklus (Graphentheorie)|Zyklus]], [[Zyklus (Graphentheorie)|Kreis]], [[Vollständiger Graph|Vollständige Graphen]].

Aufgrund des Vorhandenseins bestimmter Eigenschaften lassen sich weitere Graphenklassen unterscheiden wie

* [[Bipartiter Graph|Bipartite Graphen]],
* [[Graziöse Beschriftung|Graziöse Graphen]],
* [[Planarer Graph|Planare Graphen]],
* [[Regulärer Graph|Reguläre Graphen]],
* [[Chordale Graphen]],
* [[Perfekter Graph|Perfekte Graphen]],
* [[Magischer Graph|Magische Graphen]].

Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer [[Wurzel (Graphentheorie)|Wurzel]] bzw. einem [[Wurzelgraph|gewurzeltem Graphen]]. Besondere Bedeutung haben [[Gewurzelter Baum|gewurzelte Bäume]] unter anderem auch als [[Baum (Datenstruktur)|Baumstruktur]].

== Probleme ==
Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden im Folgenden dargestellt:[[Datei:Garaph and line graph color.png|mini|Graphfärbung]]
=== Färbung ===
{{Hauptartikel|Färbung (Graphentheorie)}}Ein bekanntes Problem fragt, wie viele Farben man braucht, um die Länder einer Landkarte einzufärben, sodass keine zwei benachbarten Länder die gleiche Farbe zugewiesen bekommen. Die Nachbarschaftsbeziehung der Länder kann man als planaren Graph repräsentieren. Das Problem kann nun als Knoten-Färbungsproblem modelliert werden. Nach dem [[Vier-Farben-Satz]] braucht man maximal vier verschiedene Farben. Ob sich im Allgemeinen ein Graph mit weniger Farben einfärben lässt, kann man nach heutigem Wissensstand nicht effizient entscheiden. Das Problem gilt als eines der schwierigsten Probleme in der Klasse der [[NP-Vollständigkeit|''NP''-vollständigen]] Probleme. Unter der Voraussetzung, dass ''P''≠ ''NP'', ist selbst eine bis auf einen konstanten Faktor angenäherte Lösung nicht effizient möglich.

=== Suchprobleme ===
{{Hauptartikel|Suchalgorithmen}}Eine wichtige Anwendung der algorithmischen Graphentheorie ist die Suche nach einer kürzesten Route zwischen zwei Orten in einem Straßennetz. Dieses Problem kann man als Graphenproblem modellieren. Hierzu abstrahiert man das Straßennetz, in dem man alle Orte als Knoten aufnimmt, und eine Kante hinzufügt, wenn es eine Verbindung zwischen diesen Orten gibt. Die Kanten dieses Graphen werden je nach Anwendung [[Kantengewichteter Graph|gewichtet]], zum Beispiel mit der Länge der assoziierten Verbindung. Mit Hilfe eines Algorithmus zum Finden von kürzesten Pfaden (beispielsweise mit dem [[Algorithmus von Dijkstra]]) kann eine kürzeste Verbindung effizient gefunden werden (siehe auch: [[:Kategorie:Graphsuchalgorithmus|Kategorie:Graphsuchalgorithmen]]).[[Datei:TSP Deutschland 3.png|mini|Handlungsreisendenproblem]]

=== Durchlaufbarkeit von Graphen ===
{{Hauptartikel|Durchlaufbarkeit von Graphen}}Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe [[Problem des Handlungsreisenden]]), bei der alle Orte eines Straßennetzes genau einmal besucht werden müssen. Da die Zahl der möglichen Rundreisen faktoriell mit der Zahl der Orte wächst, ist der naive Algorithmus, alle Rundreisen auszuprobieren und die kürzeste auszuwählen, für praktische Anwendungen nur für sehr kleine Netzwerke praktikabel. Es existieren für dieses Problem eine Reihe von [[Approximationsalgorithmus|Approximationsalgorithmen]], die eine gute aber nicht eine optimale Rundreise finden. So liefert die [[Christofides-Heuristik]] eine Rundreise die maximal 1,5-mal so lang ist wie die bestmögliche. Unter der Annahme, dass ''[[P (Komplexitätsklasse)|P]]'' ≠ ''[[NP (Komplexitätsklasse)|NP]]'' (''siehe'' [[P-NP-Problem]]), existiert kein effizienter Algorithmus für die Bestimmung einer optimalen Lösung, da dieses Problem [[NP-schwer|''NP''-schwer]] ist.

Das [[Königsberger Brückenproblem]] fragt nach der Existenz eines [[Eulerkreisproblem|Eulerkreises]]. Während sich das Eulerkreisproblem mittels [[Algorithmus von Hierholzer|Hierholzer-Verfahren]] in linearer Zeit lösen lässt, ist das Finden eines [[Hamiltonkreisproblem|Hamiltonkreises]] (ein geschlossener [[Weg (Graphentheorie)|Pfad]] in einem Graphen, der jeden Knoten genau einmal enthält) NP-schwierig. Beim [[Briefträgerproblem]] wird nach einem kürzesten Zyklus gefragt, der alle Kanten mindestens einmal durchläuft.

=== Zusammenhang ===
{{Hauptartikel|Zusammenhang (Graphentheorie)}}Beim Zusammenhang wird gefragt, ob bzw. über wie viele Wege zwei Knoten untereinander [[Erreichbarkeitsproblem in Graphen|erreichbar]] sind. Dies spielt beispielsweise bei der Beurteilung der Versorgungsnetze hinsichtlich der kritischen (ausfallbedrohten Teile) eine Rolle.
[[Datei:Block graph.svg|mini|Graph mit Cliquen]]

=== Cliquenproblem ===
{{Hauptartikel|Cliquenproblem}}Die Frage nach dem Vorhandensein (ggf. maximaler) [[Clique (Graphentheorie)|Cliquen]] sucht die Teile eines Graphen, die untereinander [[Vollständiger Graph|vollständig]] mit Kanten verbunden sind.

=== Knotenüberdeckung ===
{{Hauptartikel|Knotenüberdeckungsproblem}}Das Knotenüberdeckungsproblem sucht nach einer Teilmenge von Knoten eines Graphen, die von jeder Kante mindestens einen Endknoten enthält.

=== Flüsse und Schnitte in Netzwerken ===
{{Hauptartikel|Flüsse und Schnitte in Netzwerken}}Mit der Frage nach dem maximalen Fluss lassen sich Versorgungsnetze hinsichtlich ihrer Kapazität beurteilen.
[[Datei:HeiratssatzGraphentheorie.PNG|mini|150x150px|Matching im bipartiten Graphen]]

=== Matching ===
{{Hauptartikel|Matching (Graphentheorie)}}Matchingprobleme, die sich auf [[Flussproblem]]e zurückführen lassen, fragen nach der optimalen Auswahl von Kanten, so dass keine zwei Kanten inzident zu einem Knoten sind. Damit lassen sich [[Zuordnungsproblem]]e, beispielsweise der Ressourcennutzung wie Raum- oder Maschinenbelegung lösen.

=== Weitere Graphenprobleme ===
Zu den weiteren Graphenproblemen zählen
* das Finden einer [[stabile Menge|stabilen Menge]],
* das [[Graphzeichnen]] (hierfür existiert Software zur Visualisierung von Graphen: [[yEd]], [[Graphviz]]) und
* die Transformation von Graphen anhand von regelbasierten [[Graphersetzungssystem]]en. Graphersetzungssysteme, die dem Aufzählen aller Graphen einer Graphsprache dienen, werden auch [[Graphgrammatik]] genannt

== Siehe auch ==
{{Portal|Graphentheorie}}

== Literatur ==
* Martin Aigner: ''Graphentheorie: eine Entwicklung aus dem 4-Farben-Problem.'' 1984 (269 Seiten).
* Daniel Bonchev, D. H. Rouvray: ''Chemical Graph Theory: Introduction and Fundamentals.'' Abacus, New York NY 1990/1991, ISBN 0-85626-454-7.
* J. Sedlacek: ''Einführung in die Graphentheorie.'' B. G. Teubner, Leipzig 1968, 1972.
* M. Nitzsche: ''Graphen für Einsteiger (Rund um das Haus vom Nikolaus).'' Vieweg, Wiesbaden 2004, ISBN 3-528-03215-4.
* R. Diestel: ''Graphentheorie.'' 3. Auflage. Springer, Heidelberg 2005, ISBN 3-540-67656-2 ([https://diestel-graph-theory.com/german/index.html online-download]).
* Peter Gritzmann, René Brandenberg: ''Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer''. 2. Auflage. Springer, Berlin/Heidelberg 2003, ISBN 3-540-00045-3.
* Peter Tittmann: ''Graphentheorie. Eine anwendungsorientierte Einführung.'' 3. Auflage. Hanser, München 2019, ISBN 978-3-446-46052-2.

== Weblinks ==

{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)|Graphentheorie im Rahmen einer Vorlesung über Diskrete Mathematik}}
{{Wikibooks|Mathematik-Glossar: Graphentheorie}}
{{Wiktionary}}
* {{dmoz|Science/Math/Combinatorics/Graph_Theory/|Graphentheorie}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4113782-6}}

[[Kategorie:Graphentheorie| ]]
[[Kategorie:Teilgebiet der Mathematik]]
[[Kategorie:Diskrete Mathematik]]

Graphentheorie - Versionsgeschichte

imported>Mathze: Die letzte Textänderung von ~2025-63539-0 wurde verworfen und die Version 255090757 von Kreuz Elf wiederhergestellt.