Um den In-Grad und Out-Grad eines Scheitelpunkts zu verstehen, müssen wir zunächst etwas über das Konzept des Grades eines Scheitelpunkts lernen. Danach können wir den In-Grad und Out-Grad eines Scheitelpunkts leicht verstehen. Wir sollten wissen, dass der Ein- und Aus-Grad nur im gerichteten Graphen bestimmt werden kann. Mit Hilfe eines ungerichteten Graphen können wir den Grad eines Scheitelpunkts berechnen. Im ungerichteten Graphen können wir den In-Grad und Out-Grad eines Scheitelpunkts nicht berechnen.
Grad eines Scheitelpunkts
Wenn wir den Grad jedes Scheitelpunkts in einem Diagramm ermitteln möchten, müssen wir in diesem Fall die Anzahl der Beziehungen zählen, die ein bestimmter Scheitelpunkt mit dem anderen Scheitelpunkt herstellt. Mit anderen Worten: Wir können den Grad eines Scheitelpunkts bestimmen, indem wir die Anzahl der Kanten berechnen, die mit diesem Scheitelpunkt verbunden sind. Der Grad eines Scheitelpunkts wird mit Hilfe von deg(v) angegeben. Wenn es einen einfachen Graphen gibt, der n Scheitelpunkte enthält, ist in diesem Fall der Grad jedes Scheitelpunkts:
Deg(v) = n-1 ∀ v ∈ G
Ein Scheitelpunkt hat die Fähigkeit, mit allen anderen Scheitelpunkten in einem Diagramm außer mit sich selbst eine Kante zu bilden. In einem einfachen Diagramm ergibt sich der Grad eines Scheitelpunkts also aus der Anzahl der Scheitelpunkte in einem Diagramm minus 1. Hier wird 1 für den Selbstscheitelpunkt verwendet, da er selbst keine Schleife bildet. Wenn der Graph die Eckpunkte enthält, die die Selbstschleife haben, dann ist dieser Graphtyp kein einfacher Graph.
Beispiel:
In diesem Beispiel haben wir einen Graphen mit 6 Eckpunkten, d. h. a, b, c, d, e und f. Der Scheitelpunkt „a“ hat den Grad 5 und alle anderen Scheitelpunkte haben den Grad 1. Wenn ein Scheitelpunkt den Grad 1 hat, wird dieser Scheitelpunkttyp als „Endscheitelpunkt“ bezeichnet.
Es gibt zwei Fälle von Graphen, in denen wir den Grad eines Scheitelpunkts berücksichtigen können, die wie folgt beschrieben werden:
- Ungerichteter Graph
- Gerichteter Graph
Jetzt lernen wir den Grad eines Scheitelpunkts in einem gerichteten Graphen und den Grad eines Scheitelpunkts in einem ungerichteten Graphen im Detail.
Grad eines Scheitelpunkts in einem ungerichteten Diagramm
Wenn es einen ungerichteten Graphen gibt, gibt es in diesem Diagrammtyp keine gerichtete Kante. Die Beispiele zur Bestimmung des Grades eines Scheitelpunkts in einem ungerichteten Graphen werden wie folgt beschrieben:
Beispiel 1: In diesem Beispiel betrachten wir einen ungerichteten Graphen. Jetzt werden wir den Grad jedes Scheitelpunkts in diesem Diagramm herausfinden.
Lösung: Im obigen ungerichteten Diagramm gibt es insgesamt 5 Scheitelpunkte, d. h. a, b, c, d und e. Der Grad jedes Scheitelpunkts wird wie folgt beschrieben:
- Der obige Graph enthält zwei Kanten, die sich am Scheitelpunkt „a“ treffen. Daher ist Grad(a) = 2
- Dieser Graph enthält 3 Kanten, die sich am Scheitelpunkt „b“ treffen. Daher ist Grad(b) = 3
- Der obige Graph enthält 1 Kante, die sich am Scheitelpunkt „c“ trifft. Daher ist Grad(c) = 1. Der Scheitelpunkt c wird auch als hängender Scheitelpunkt bezeichnet.
- Der obige Graph enthält zwei Kanten, die sich am Scheitelpunkt „d“ treffen. Daher ist Grad(d) = 2.
- Der obige Graph enthält 0 Kanten, die sich am Scheitelpunkt „e“ treffen. Daher ist Grad(a) = 0. Der Scheitelpunkt e kann auch als isolierter Scheitelpunkt bezeichnet werden.
Beispiel 2: In diesem Beispiel betrachten wir einen ungerichteten Graphen. Jetzt werden wir den Grad jedes Scheitelpunkts in diesem Diagramm herausfinden.
Lösung: Im obigen ungerichteten Diagramm gibt es insgesamt 5 Scheitelpunkte, d. h. a, b, c, d und e. Der Grad jedes Scheitelpunkts wird wie folgt beschrieben:
Grad des Scheitelpunkts a = deg(a) = 2
Grad des Scheitelpunkts b = deg(b) = 2
Grad des Scheitelpunkts c = deg(c) = 2
Grad des Scheitelpunkts d = deg(d) = 2
Scheitelgrad e = deg(e) = 0
In diesem Diagramm gibt es keinen hängenden Scheitelpunkt und der Scheitelpunkt „e“ ist ein isolierter Scheitelpunkt.
Grad des Scheitelpunkts im gerichteten Diagramm
Wenn es sich bei dem Graphen um einen gerichteten Graphen handelt, muss in diesem Graphen jeder Scheitelpunkt einen In-Grad und einen Out-Grad haben. Angenommen, es gibt einen gerichteten Graphen. In diesem Diagramm können wir die folgenden Schritte verwenden, um den In-Grad, den Out-Grad und den Grad eines Scheitelpunkts zu ermitteln.
Im Grad eines Scheitelpunkts
Der In-Grad eines Scheitelpunkts kann als Anzahl von Kanten mit v beschrieben werden, wobei v zur Angabe des Endscheitelpunkts verwendet wird. Mit anderen Worten, wir können es als eine Reihe von Kanten beschreiben, die zum Scheitelpunkt kommen. Mit Hilfe der Syntax deg-(v) können wir den In-Grad eines Scheitelpunkts schreiben. Wenn wir den In-Grad eines Scheitelpunkts bestimmen wollen, müssen wir dazu die Anzahl der Kanten zählen, die am Scheitelpunkt enden.
Out-Grad eines Scheitelpunkts
Der äußere Grad eines Scheitelpunkts kann als Anzahl von Kanten mit v beschrieben werden, wobei v zur Angabe des anfänglichen Scheitelpunkts verwendet wird. Mit anderen Worten, wir können es als eine Reihe von Kanten beschreiben, die vom Scheitelpunkt ausgehen. Mit Hilfe der Syntax deg+(v) können wir den Out-Grad eines Scheitelpunkts schreiben. Wenn wir den Out-Grad eines Scheitelpunkts bestimmen wollen, müssen wir dazu die Anzahl der Kanten zählen, die vom Scheitelpunkt ausgehen.
Grad eines Scheitelpunkts
Java versuche es zu fangen
Der Grad eines Scheitelpunkts wird mit Hilfe von deg(v) angegeben, was der Addition von Ein-Grad eines Scheitelpunkts und Aus-Grad eines Scheitelpunkts entspricht. Die symbolische Darstellung des Grades eines Scheitelpunkts wird wie folgt beschrieben:
Deg(v) = deg-(v) + deg+(v)
Beispiel 1: In diesem Beispiel haben wir einen Graphen und müssen den Grad jedes Scheitelpunkts bestimmen.
Lösung: Dazu ermitteln wir zunächst den Grad eines Scheitelpunkts, den Ein-Grad eines Scheitelpunkts und dann den Aus-Grad eines Scheitelpunkts.
Wie wir sehen können, enthält das obige Diagramm die gesamten 6 Scheitelpunkte, d. h. v1, v2, v3, v4, v5 und v6.
Abschluss:
In-Grad eines Scheitelpunkts v1 = deg(v1) = 1
In-Grad eines Scheitelpunkts v2 = deg(v2) = 1
In-Grad eines Scheitelpunkts v3 = deg(v3) = 1
Im Grad eines Scheitelpunkts v4 = deg(v4) = 5
In-Grad eines Scheitelpunkts v5 = deg(v5) = 1
Im Grad eines Scheitelpunkts v6 = deg(v6) = 0
Out-Abschluss:
Außengrad eines Scheitelpunkts v1 = deg(v1) = 2
Außengrad eines Scheitelpunkts v2 = deg(v2) = 3
Außengrad eines Scheitelpunkts v3 = deg(v3) = 2
Außengrad eines Scheitelpunkts v4 = deg(v4) = 0
Außengrad eines Scheitelpunkts v5 = deg(v5) = 2
Außengrad eines Scheitelpunkts v6 = deg(v6) = 0
Grad eines Scheitelpunkts
Mithilfe der oben beschriebenen Definition wissen wir, dass der Grad eines Scheitelpunkts Grad(v) = Grad ist-(v) + du+(v). Jetzt berechnen wir es mit Hilfe dieser Formel wie folgt:
Grad eines Scheitelpunkts v1 = deg(v1) = 1+2 = 3
Grad eines Scheitelpunkts v2 = deg(v2) = 1+3 = 4
Grad eines Scheitelpunkts v3 = deg(v3) = 1+2 = 3
Grad eines Scheitelpunkts v4 = deg(v4) = 5+0 = 5
Grad eines Scheitelpunkts v5 = deg(v5) = 1+2 = 3
Grad eines Scheitelpunkts v6 = deg(v6) = 0+0 = 0
Beispiel 2:
In diesem Beispiel haben wir einen gerichteten Graphen mit 7 Eckpunkten. Der Scheitelpunkt „a“ enthält zwei Kanten, nämlich „ad“ und „ab“, die nach außen verlaufen. Daher enthält der Scheitelpunkt „a“ den Ausgangsgrad, der 2 ist. Ebenso hat der Scheitelpunkt „a“ auch eine Kante „ga“, die auf diesen Scheitelpunkt „a“ zuläuft. Daher enthält der Scheitelpunkt 'a' den In-Grad, der 1 ist.
Lösung: Der Ein- und Aus-Grad aller oben genannten Eckpunkte wird wie folgt beschrieben:
Abschluss:
Im Grad eines Scheitelpunkts a = deg(a) = 1
In-Grad eines Scheitelpunkts b = deg(b) = 2
Im Grad eines Scheitelpunkts c = deg(c) = 2
In-Grad eines Scheitelpunkts d = deg(d) = 1
Im Grad eines Scheitelpunkts e = deg(e) = 1
In-Grad eines Scheitelpunkts f = deg(f) = 1
In-Grad eines Scheitelpunkts g = deg(g) = 0
Out-Abschluss:
Außengrad eines Scheitelpunkts a = deg(a) = 2
Außengrad eines Scheitelpunkts b = deg(b) = 0
Außengrad eines Scheitelpunkts c = deg(c) = 1
Außengrad eines Scheitelpunkts d = deg(d) = 1
Außengrad eines Scheitelpunkts e = deg(e) = 1
Außengrad eines Scheitelpunkts f = deg(f) = 1
Außengrad eines Scheitelpunkts g = deg(g) = 2
Grad jedes Scheitelpunkts:
Wir wussten, dass der Grad eines Scheitelpunkts Grad(v) = Grad ist-(v) + du+(v). Jetzt berechnen wir es mit Hilfe dieser Formel wie folgt:
Grad eines Scheitelpunkts a = deg(a) = 1+2 = 3
Grad eines Scheitelpunkts b = deg(b) = 2+0 = 2
Grad eines Scheitelpunkts c = deg(c) = 2+1 = 3
Grad eines Scheitelpunkts d = deg(d) = 1+1 = 2
Grad eines Scheitelpunkts e = deg(e) = 1+1 = 2
Grad eines Scheitelpunkts f = deg(f) = 1+1 = 2
Grad eines Scheitelpunkts g = deg(g) = 0+2 = 2
Beispiel 3: In diesem Beispiel haben wir einen gerichteten Graphen mit 5 Eckpunkten. Der Scheitelpunkt „a“ enthält 1 Kante, d. h. „ae“, die nach außen verläuft. Daher enthält der Scheitelpunkt „a“ einen Ausgangsgrad, der 1 ist. Ebenso hat der Scheitelpunkt „a“ auch eine Kante „ba“, die auf diesen Scheitelpunkt „a“ zuläuft. Daher enthält der Scheitelpunkt 'a' den In-Grad, der 1 ist.
Lösung: Der Ein- und Aus-Grad aller oben genannten Eckpunkte wird wie folgt beschrieben:
In-Grad
Im Grad eines Scheitelpunkts a = deg(a) = 1
scan.next Java
In-Grad eines Scheitelpunkts b = deg(b) = 0
Im Grad eines Scheitelpunkts c = deg(c) = 2
In-Grad eines Scheitelpunkts d = deg(d) = 1
Im Grad eines Scheitelpunkts e = deg(e) = 1
Out-Abschluss:
Außengrad eines Scheitelpunkts a = deg(a) = 1
Außengrad eines Scheitelpunkts b = deg(b) = 2
Außengrad eines Scheitelpunkts c = deg(c) = 0
Außengrad eines Scheitelpunkts d = deg(d) = 1
Außengrad eines Scheitelpunkts e = deg(e) = 1
Grad jedes Scheitelpunkts:
Wir wussten, dass der Grad eines Scheitelpunkts Grad(v) = Grad ist-(v) + du+(v). Jetzt berechnen wir es mit Hilfe dieser Formel wie folgt:
Grad eines Scheitelpunkts a = deg(a) = 1+1 = 2
Grad eines Scheitelpunkts b = deg(b) = 0+2 = 2
Grad eines Scheitelpunkts c = deg(c) = 2+0 = 2
Grad eines Scheitelpunkts d = deg(d) = 1+1 = 2
Grad eines Scheitelpunkts e = deg(e) = 1+1 = 2
Beispiel 4: In diesem Beispiel haben wir einen Graphen und müssen den Grad, den In-Grad und den Out-Grad jedes Scheitelpunkts bestimmen.
Lösung: Dazu ermitteln wir zunächst den In-Grad eines Scheitelpunkts und dann den Out-Grad eines Scheitelpunkts.
Wie wir sehen können, enthält das obige Diagramm die gesamten 8 Scheitelpunkte, d. h. 0, 1, 2, 3, 4, 5 und 6.
Abschluss:
In-Grad eines Scheitelpunkts 0 = Grad(0) = 1
In-Grad eines Scheitelpunkts 1 = Grad(1) = 2
In-Grad eines Scheitelpunkts 2 = Grad(2) = 2
In-Grad eines Scheitelpunkts 3 = Grad(3) = 2
In-Grad eines Scheitelpunkts 4 = Grad(4) = 2
Im Grad eines Scheitelpunkts 5 = Grad(5) = 2
In-Grad eines Scheitelpunkts 6 = Grad(6) = 2
Out-Abschluss:
Außengrad eines Scheitelpunkts 0 = Grad(0) = 2
Außengrad eines Scheitelpunkts 1 = Grad(1) = 1
Außengrad eines Scheitelpunkts 2 = Grad(2) = 3
Außengrad eines Scheitelpunkts 3 = Grad(3) = 2
Außengrad eines Scheitelpunkts 4 = Grad(4) = 2
Außengrad eines Scheitelpunkts 5 = Grad(5) = 2
Außengrad eines Scheitelpunkts 6 = Grad(6) = 1
Grad jedes Scheitelpunkts:
Wir wussten, dass der Grad eines Scheitelpunkts Grad(v) = Grad ist-(v) + du+(v). Jetzt berechnen wir es mit Hilfe dieser Formel wie folgt:
Grad eines Scheitelpunkts 0 = Grad(0) = 1+2 = 3
Grad eines Scheitelpunkts 1 = deg(1) = 2+1 = 3
Grad eines Scheitelpunkts 2 = deg(2) = 2+3 = 5
Grad eines Scheitelpunkts 3 = deg(3) = 2+2 = 4
Grad eines Scheitelpunkts 4 = deg(4) = 2+2 = 4
Grad eines Scheitelpunkts 5 = deg(5) = 2+2 = 4
Grad eines Scheitelpunkts 6 = Grad(5) = 2+1 = 3
Gradfolge eines Graphen
Um die Gradfolge eines Graphen zu bestimmen, müssen wir zunächst den Grad jedes Scheitelpunkts in einem Graphen bestimmen. Danach werden wir diese Abschlüsse in aufsteigender Reihenfolge aufschreiben. Diese Reihenfolge/Folge kann als Gradfolge eines Graphen bezeichnet werden.
Zum Beispiel: In diesem Beispiel haben wir drei Graphen mit 3, 4 und 5 Eckpunkten, und die Gradfolge aller Graphen ist 3.
In der obigen Grafik gibt es drei Eckpunkte. Der Grad einer Folge dieses Graphen wird wie folgt beschrieben:
In der obigen Grafik gibt es 4 Eckpunkte. Die Gradfolge dieses Graphen wird wie folgt beschrieben:
In der obigen Grafik gibt es 5 Eckpunkte. Die Gradfolge dieses Graphen wird wie folgt beschrieben: