Effizienzanalyse

Die verschiedenen Repräsentationen der Graphen haben Vor- und Nachteile. Man kann z.B. den benötigten Speicherplatz und die Laufzeit für Zugriffsoperationen auf den Graphen bewerten.

Dabei muss man Anwendungen unterscheiden, bei denen relativ dünne Graphen auftreten, und Anwendungen, bei denen der Graph (nahezu) vollständig ist.

Repräsentiert der Graph z.B. eine Karte mit Straßen und Kreuzungen, gehen von jedem Knoten (=Kreuzung) nur wenige Kanten (=Straßen) ab. Mehr als 4-5 Straßen gehen üblicherweise nicht von einer Kreuzung aus. Diese Zahl ändert sich auch nicht, wenn die Anzahl der Knoten steigt. Der Graph ist also sehr dünn. Betrachtet man hingegen das Traveling Salesman Problem, dann kann man von jeder Stadt in jede andere reisen. Der Graph ist also vollständig. Bei einer Erhöhung der der Knotenzahl steigt damit auch die Zahl der Kanten pro Knoten.