Attributierung

  Für viele Anwendungen von Graphen ist es nötig, neben der reinen Graphenstruktur noch zusätzliche Daten an Knoten oder Kanten zu verwalten. Sollen Knoten oder Kanten mit Daten versehen werden, spricht man von einer  Attributierung des Graphen. Man kann zwei Arten der Attributierung unterscheiden:

• Häufig reicht zur Abbildung eines Realitätsausschnitts auf einen Graphen die Unterscheidung von Knoten- oder Kantenarten mittels der Typisierung nicht aus. Vielmehr ist für einige (oder alle) Knoten und Kanten zusätzliche Information zu speichern. Die Art der Information hängt dabei in der Regel vom Typ des Knotens oder der Kante ab. Im Beispiel aus dem vorangehenden Abschnitt (siehe Abb.) könnte es notwendig sein, für die Parkeinrichtungen die Namen der Einrichtung, für Parkgebäude darüberhinaus die Öffnungszeiten zu speichern.
• Für viele Algorithmen der Graphentheorie ist es notwendig, kurzfristig Steuerinformationen an Knoten oder Kanten zu schreiben, die nach Ablauf des Verfahrens wieder gelöscht werden können. Z.B. ist es für ein Suchverfahren wichtig zu wissen, welche Knoten bereits behandelt wurden und welche nicht. Attributierung dieser Art wird im folgenden als  temporäre Attributierung bezeichnet.