2. Unterteilung der Graphen

(Last Updated On: 24. Mai 2012)

zurück zu Grundbegriffe I

2.1 Unterteilung der einfachen Graphen

2.1.1 Einfache, schlichte Graphen

Das sind Graphen ohne Schlingen (Kante von einem Knoten zu sich selbst) und ohne Mehrfachkanten.

X1 = ({a, b, c, d}, {[a, b], [a, c], [a, d], [b, c], [b, d], [c, d]})
Ist ein ungerichteter Graph, welcher mit unterschiedlichen Darstellungsmöglichkeiten gezeichnet werden kann.

X2 = (V2, E2)
V2 = {A, B, C, D}
E2 = {[A, B], [A, C], [A, D], [B, C], [B, D], [C, D]}
Ist ebenfalls ein ungerichteter Graph, welcher mit denselben Darstellungsmöglichkeiten gezeichnet werden kann, nur die Knotenbezeichnung ist anders. Struktur (Beziehung zwischen den Komponenten) ist gleich. Daher können unterschiedliche Graphen eine gleiche Abblidungen haben.

2.1.2 Ungerichteter Graph

X(V,E); jeder Kante entspricht ein ungeordnetes Paar von Knoten, das in eckige Klammern gesetzt wird; e ∈ E(X) und x,y ∈ V(X); e ⇒ [x,y]; x y

Def: Graph X = (V,E)
V…(endl.) Menge von Knoten
E…(endl.) Menge von Kanten
[x,y]… ungerichtete Kante zwischen x und y

2.1.3 Gerichteter Graph

jeder Kante entspricht ein geordnetes Paar von Knoten, das in spitze Kalammern gesetzt wird:e ∈ ⟨x,y⟩ x ⇒ y; ⟨y,x⟩ x ⇐ y;

2.1.4 Gemischte Graphen

es treten geordnete und ungeordnete Paare auf.

2.1.5 Plättbarer Graph

z.B. einschichtige Platine

plättbare Graphen lassen sich als Strecken darstellen z.B.:

V(x)= {} E(x)= {}

x = ({a,b,c,d},{[a,b],[a,c],[a,d],[b,c],[d,b]}

*********************

adjazent (anliegend) bedeutet: zwei Knoten (Kanten) sind benachbart!

(nur innerhalb desselben Typs, also Kante-Kante oder Knoten-Knoten)

inzident bedeutet: Knoten ist Bestandteil der Kante! (bei unterschiedlichen Typen)

Vergleich: Kohäsion und Adhäsion

Bei gerichteten Graphen spricht man auch von Nachfolger; bei ungerichteten Graphen von Nachbar.

(432)


History

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert