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.