Wir können die Handshaking-Theorie auch als Gradsummensatz oder Handshaking-Lemma bezeichnen. Die Handshaking-Theorie besagt, dass die Summe der Grade aller Eckpunkte eines Graphen doppelt so groß ist wie die Anzahl der in diesem Graphen enthaltenen Kanten. Die symbolische Darstellung der Handshake-Theorie wird wie folgt beschrieben:
Hier,
„d“ wird verwendet, um den Grad des Scheitelpunkts anzugeben.
„v“ wird verwendet, um den Scheitelpunkt anzugeben.
„e“ wird verwendet, um die Kanten anzuzeigen.
Handshake-Theorem:
Aus dem Handshake-Theorem müssen einige Schlussfolgerungen gezogen werden, die wie folgt beschrieben werden:
In jedem Diagramm:
- Für die Gradsumme aller Eckpunkte muss es gerade Zahlen geben.
- Wenn es für alle Eckpunkte ungerade Grade gibt, muss die Summe der Grade dieser Eckpunkte immer gerade bleiben.
- Wenn es einige Eckpunkte gibt, die einen ungeraden Grad haben, dann ist die Anzahl dieser Eckpunkte gerade.
Beispiele der Handshake-Theorie
Es gibt verschiedene Beispiele für die Handshake-Theorie, und einige Beispiele werden wie folgt beschrieben:
Beispiel 1: Hier haben wir einen Graphen, dessen Grad jeder Scheitelpunkt 4 und 24 Kanten beträgt. Jetzt werden wir die Anzahl der Eckpunkte in diesem Diagramm ermitteln.
Lösung: Mit Hilfe der obigen Grafik haben wir die folgenden Details erhalten:
Grad jedes Scheitelpunkts = 24
Anzahl der Kanten = 24
Nun gehen wir davon aus, dass die Anzahl der Eckpunkte = n ist
Mit Hilfe des Handshaking-Theorems haben wir Folgendes:
Summe eines Grades aller Eckpunkte = 2 * Anzahl der Kanten
Jetzt werden wir die angegebenen Werte in die obige Handshake-Formel einfügen:
n*4 = 2*24
Array im String
n = 2*6
n = 12
Somit ist in Graph G die Anzahl der Eckpunkte = 12.
Beispiel 2: Hier haben wir einen Graphen mit 21 Kanten, 3 Eckpunkten vom Grad 4 und allen anderen Eckpunkten vom Grad 2. Jetzt ermitteln wir die Gesamtzahl der Eckpunkte in diesem Graphen.
Lösung: Mit Hilfe der obigen Grafik haben wir die folgenden Details erhalten:
Anzahl der Eckpunkte vom Grad 4 = 3
Anzahl der Kanten = 21
Alle anderen Eckpunkte haben den Grad 2
Nun gehen wir davon aus, dass die Anzahl der Eckpunkte = n ist
Mit Hilfe des Handshaking-Theorems haben wir Folgendes:
Summe der Grade aller Eckpunkte = 2 * Anzahl der Kanten
Jetzt werden wir die angegebenen Werte in die obige Handshake-Formel einfügen:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Somit ist in Diagramm G die Gesamtzahl der Eckpunkte = 18.
Beispiel 3: Hier haben wir einen Graphen mit 35 Kanten, 4 Eckpunkten vom Grad 5, 5 Eckpunkten vom Grad 4 und 4 Eckpunkten vom Grad 3. Jetzt ermitteln wir die Anzahl der Eckpunkte vom Grad 2 in diesem Graphen.
Lösung: Mit Hilfe der obigen Grafik haben wir die folgenden Details erhalten:
Anzahl der Kanten = 35
Anzahl der Eckpunkte vom Grad 5 = 4
Anzahl der Eckpunkte vom Grad 4 = 5
Anzahl der Eckpunkte vom Grad 3 = 4
Nun gehen wir davon aus, dass die Anzahl der Eckpunkte vom Grad 2 = n ist
Java konvertiert String in int
Mit Hilfe des Handshaking-Theorems haben wir Folgendes:
Summe der Grade aller Eckpunkte = 2 * Anzahl der Kanten
Jetzt werden wir die angegebenen Werte in die obige Handshake-Formel einfügen:
Null-Check in Java
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
Somit ist in Diagramm G die Anzahl der Eckpunkte vom Grad 2 = 9.
Beispiel 4: Hier haben wir einen Graphen mit 24 Kanten und der Grad jedes Scheitelpunkts ist k. Nun ermitteln wir die mögliche Anzahl der Scheitelpunkte aus den gegebenen Optionen.
- fünfzehn
- zwanzig
- 8
- 10
Lösung: Mit Hilfe der obigen Grafik haben wir die folgenden Details erhalten:
Anzahl der Kanten = 24
Grad jedes Scheitelpunkts = k
Nun gehen wir davon aus, dass die Anzahl der Eckpunkte = n ist
Mit Hilfe des Handshaking-Theorems haben wir Folgendes:
Summe der Grade aller Eckpunkte = 2 * Anzahl der Kanten
Jetzt werden wir die angegebenen Werte in die obige Handshake-Formel einfügen:
N*k = 2*24
K = 48/ca
Es ist zwingend erforderlich, dass der Grad eines Scheitelpunkts eine ganze Zahl enthält.
Daher können wir in der obigen Gleichung nur die Wertetypen von n verwenden, die uns einen ganzen Wert von k liefern.
Nun überprüfen wir die oben angegebenen Optionen, indem wir sie nacheinander wie folgt an die Stelle von n setzen:
- Für n = 15 erhalten wir k = 3,2, was keine ganze Zahl ist.
- Für n = 20 erhalten wir k = 2,4, was keine ganze Zahl ist.
- Für n = 8 erhalten wir k = 6, was eine ganze Zahl ist und zulässig ist.
- Für n = 10 erhalten wir k = 4,8, was keine ganze Zahl ist.
Daher ist Option C die richtige Option.