zurück zu Grundbegriffe I

6 Grad eines Knotens

Definition: Unter Grad d^[1](x) eines Knotens x ∈V(X) versteht man die Anzahl der Kanten ei ∈E(X), die mit x inzident sind.

Endknoten einer Kanten sind alle drei aber Endknoten des Graphen nur die äußeren zwei.

Es gilt: d(x) = 0……isolierter Knoten

d(x) =1……Endknoten; linear
d(x) >1……kein Endknoten
d(x) = 2……quadratisch
d(x) = 3……kubisch

Ist x eine Ecke eines Graphen, so ist der Grad von x (grad x) die Kardinalzahl der Menge aller Kanten die mit x inzidieren (Schlingen werden doppelt gezählt).

In einem endl., schlingen- und zweiecklosen Graphen gibt grad x auch die Anzahl der Ecken an, die durch Kanten mit x verbunden sind. In derartigen Graphen ist die Kantenzahl n_k = ½∑ grad x.

x∈E

In einem vollstädigen, endl. Graphen mit n_e Ecken ist grad x = n_e 1 für alle Ecken. Die Anzahl der Kanten ist daher n_k = ½ n_e(n_e -1).

Graphen, in denen jede Ecke vom gleichen Grad ist, heißen regulär. Zu ihnen gehören z.B. die vollständigen Graphen und die Graphen, die die Oberfläche der regulären Polyeder,
Def.: In endl., schlingen- und zweiecklosen, regulären Graphen gilt: n_k = ½ ne . grad x.

6.1 Knotengrade – Kanten

; α₀ = |V(x)|; α₁ = |E(x)|

Die Summe der Knotengrade entspricht dem Doppelten der Kanten in dem Graphen. Bei Isomorphie muß die Nachbarschaftsbeziehung gegeben sein. Wenn ein Punkt fixiert wurde, somit ist die Abbildung des Graphen gegeben, da die Reihenfolge auch beibehalten werden muß bei der Abbildung.

4.2 Regulärer Graph vom Grad x

Alle Knoten haben den gleichen Grad.

Def.: Ein Graph X heißt regulär vom Grad r wenn gilt:
∧ d(x) = r)
x∈V(X)

4.3 Vollständiger Graph

Jeder Knoten ist mit jedem Knoten verbunden.

Def.: Ein Graph X heißt vollständiger Graph, wenn er regulär vom Grad |V|-1 ist.

C1

C2

C3

C4

C5

Satz: In hedem Graphen X= (V,E) gilt:
∑d(x) = 2.|E(X)|
x∈V(x)

Folgerung: In jedem Graphen ist die Anzahl der Knoten ungeraden Grades gerade.

die Summe der Grade entspricht immer der doppelten Anzahl der Kanten. Z.B. für Netzwerke bedeutsam; vollständig, wenn alle Knoten des Graphen den selben Knotengrad aufweisen.

1. lineare Graphen…………..regulär vom Grad 1
2. quadratischee Graphen……..regulär vom Grad 2
3. kubische Graphen………….regulär vom Grad 3

ad a) Jeder Knoten im Graphen ist nur durch eine einzige Kante mit einem anderen Knoten verbunden, dadurch gibt es keine adjazenten Kanten untereinander

ad b) Token Ring Netz-Verbindung, dadurch keine große Ausfallsicherheit

ad c) Drahtgitter Modell eines Würfels oder einer dreieckigen Pyramide

|Menge| = Anzahl der Elemente einer Menge

Kubische Graphen können nie eine ungerade Anzahl von Knoten aufweisen. Dies ergibt sich aus der Formel Summe der Knotengrade aller Knoten im Graphen = 2 * der Kantenanzahl im Graphen.

Ein ungerader Knotengrad ergibt nur mit einem geraden Faktor ein gerades Ergebnis, welches ganzzahlig durch 2 teilbar ist. Der gerade Faktor ist die Knotenanzahl.

6.3.1 Erweiterung von kubischen Graphen

1. Erweiterung durch auflösen von 2 nicht zueinander adjazenten Kanten
   1. die Verbindung lösen
   2. 2 neue Knoten einfügen; einen je aufgelöster Kante
   3. jeweils die 2 zweigradigen Knoten mit dem neuen Knoten verbinden
   4. die 2 neuen Knoten miteinander verbinden
2. Erweiterung durch auflösen von 2 zueinander adjazenten Kanten
   1. 2 neue Knoten einfügen
   2. beide mit dem eingradigen Knoten verbinden
   3. die 2 neuen Knoten miteinander verbinden
   4. eine Verbindung jeweils von einem neuen Konten zu einem alten zweigradigen Knoten

Die Erweiterung mittels Auflösen von zwei nicht adjazenten Kanten hat gegenüber der zweiten Variante den Vorteil, daß das Knotennetz globaler bleibt und die Knotenverbindungen untereinander nicht so lokal vernetzt sind.

6.3.2 Beispiel zur Knotenerweiterung von kubischen Graphen

Erweiterung bei adjazenten Kanten

Erweiterung bei ¬ adjazenten Kanten

nach oben