Man kann darüber streiten, ob man Graphen lieber intuitiv oder mathematisch sauber definiert. Deswegen geben wir hier drei Definitionen mit wachsendem mathematischen Härtegrad. Graphen informell")?> Ein Graph G=(V,E) besteht aus Knoten V und Kanten E. Dabei verbindet eine Kante üblicherweise zwei Knoten und diese Relationen zwischen den Knoten sind das, was den Graphen ausmacht. Also z.B. folgender Graph hat zehn Knoten und 15 Kanten und ist normalerweise ein Gegenbeispiel, der Petersen Graph.

einfache Graphen")?> Ein Graph besteht aus einer endlichen Menge von Knoten V und einer Teilmenge E der zweielementigen Teilmengen von V, den Kanten. Um für alle Eventualitäten gerüstet zu sein, die bei Graphen auftreten können, kommt man, glaube ich, nicht an folgender Definition vorbei: Graphen formal")?> Ein Graph besteht aus endlichen Mengen V, den Knoten, und E, den Kanten, sowie einer Inzidenzrelation f: E -> V + W, wobei V +W die Menge aller Teilmengen von Knoten mit mindestens einem und höchstens zwei Elementen sei. Kontakt:")?> Tel.: 0221/470-6030
Fax: 0221/470-5160
contact@zpr.uni-koeln.de