gerichteten Graphen
-
Hallo,
kann mir bitte jemand eine genauere Definition von "dünn besetzten Graphen" geben...
Habe im Internet folgende Information dazu gefunden, aber was genau versteht man unter "dünn besetzten .." ist mir noch nicht 100% klar...Danke im Voraus!!!
"Viele Graphen haben nur eine dünn besetzte Verbindungsmatrix. Die meisten Einträge werden daher nicht
verwendet und die ganze Matrix verschwendet viel Platz. Ein ökonomischerer Umgang mit Speicher haben die
Nachbarschaftslisten oder Verbindungslisten (adjacency lists). Für jeden Knoten unterhält man eine Liste mit
benachbarten Knoten."
-
**....ist es so, dass die Anzahl der Kanten ähnlich hoch wie die Anzahl der Knoten ist ?
**
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x, bzw. C++11) in das Forum Mathematik und Physik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Den Begriff "dünnbesetzter Graph" würd ich ähnlich wie "dünnbesetzte Matrix" definieren. Also ja. Eine exakte Grenze des Verhältnisses von Knoten- zu Kantenzahl wirst du aber nicht finden.
Edit: siehe http://en.wikipedia.org/wiki/Dense_graph
-
ok, Danke