Dimension eines Graphs

Wissenschaft Informatik
#1

Hallo,

in der Physik bezeichnet man häufig mit der „Dimension“ eines Systems den Vernetzungsgrad, weil häufig nur benachbarte Teilchen (oder Subsysteme) miteinander agieren können, und je höher die Dimension ist, desto mehr Nachbarn hat ein Teilchen.

Gibt es eine ähnliche Definition des Dimensionsbegriffs für Graphen in der Informatik? Nach einer ersten Suche scheint es das schon zu geben, aber ich habe keine verständliche Definition gefunden.
Kann mir ja jemand helfen? (Ach ja, falls es relevant ist: es geht um gerichtete Graphen).

Grüße und Danke im Voraus,
Moritz

#2

Moien

Gibt es eine ähnliche Definition des Dimensionsbegriffs für
Graphen in der Informatik?

Es gibt dense oder sparse Graph (sparse ermöglicht eine andere, platzsparende Speicherung) http://en.wikipedia.org/wiki/Sparse_graph . Ist allerdings sehr wage.

Nach einer ersten Suche scheint es
das schon zu geben, aber ich habe keine verständliche
Definition gefunden.

Brauchst du die Definition oder Algorithmen ?

cu

#3

Hallo,

Gibt es eine ähnliche Definition des Dimensionsbegriffs für
Graphen in der Informatik?

Es gibt dense oder sparse Graph (sparse ermöglicht eine
andere, platzsparende Speicherung)
http://en.wikipedia.org/wiki/Sparse_graph . Ist allerdings
sehr wage.

stimmt - eine Zahl als Dimension wäre mir lieber :wink:

Nach einer ersten Suche scheint es
das schon zu geben, aber ich habe keine verständliche
Definition gefunden.

Brauchst du die Definition oder Algorithmen ?

hm, beides. Letztendlich will ich (aus Neugierde) die Dimension berechnen, d.h. ich brauche einen Algorithmus. Aber ich will auch verstehen, was ich da implementiere, daher wäre eine Definition auch ganz nett.

Grüße,
Moritz