Teorię uścisku dłoni możemy również nazwać twierdzeniem o sumie stopni lub lematem o uścisku dłoni. Teoria uzgadniania głosi, że suma stopnia wszystkich wierzchołków grafu będzie dwukrotnie większa od liczby krawędzi zawartych w tym grafie. Symboliczne przedstawienie teorii uścisku dłoni opisano w następujący sposób:

Tutaj,

„d” służy do wskazania stopnia wierzchołka.

„v” służy do wskazania wierzchołka.

„e” służy do wskazania krawędzi.

Twierdzenie o uścisku dłoni:

Z twierdzenia o uścisku dłoni należy wyciągnąć pewne wnioski, które opisano w następujący sposób:

Na dowolnym wykresie:

• Suma stopnia wszystkich wierzchołków musi być parzysta.
• Jeśli wszystkie wierzchołki mają stopnie nieparzyste, to suma stopni tych wierzchołków musi zawsze pozostać parzysta.
• Jeśli istnieją wierzchołki o stopniu nieparzystym, liczba tych wierzchołków będzie parzysta.

Przykłady teorii uścisku dłoni

Istnieje wiele przykładów teorii uścisku dłoni, a niektóre z nich opisano w następujący sposób:

Przykład 1: Tutaj mamy graf, którego stopień każdego wierzchołka wynosi 4 i 24 krawędzie. Teraz dowiemy się, ile wierzchołków jest w tym grafie.

Rozwiązanie: Za pomocą powyższego wykresu otrzymaliśmy następujące szczegóły:

Stopień każdego wierzchołka = 24

Liczba krawędzi = 24

Załóżmy teraz, że liczba wierzchołków = n

Korzystając z twierdzenia o uścisku dłoni, mamy następujące rzeczy:

Suma stopnia wszystkich wierzchołków = 2 * Liczba krawędzi

Teraz wstawimy podane wartości do powyższego wzoru uzgadniania:

kolejka i kolejka priorytetowa w Javie

n*4 = 2*24

n = 2*6

n = 12

Zatem w grafie G liczba wierzchołków = 12.

Przykład 2: Mamy tutaj graf, który ma 21 krawędzi, 3 wierzchołki stopnia 4 i wszystkie pozostałe wierzchołki stopnia 2. Teraz policzymy całkowitą liczbę wierzchołków na tym grafie.

Rozwiązanie: Za pomocą powyższego wykresu otrzymaliśmy następujące szczegóły:

Liczba wierzchołków stopnia 4 = 3

Liczba krawędzi = 21

Wszystkie pozostałe wierzchołki mają stopień 2

Załóżmy teraz, że liczba wierzchołków = n

Korzystając z twierdzenia o uścisku dłoni, mamy następujące rzeczy:

Suma stopnia wszystkich wierzchołków = 2 * Liczba krawędzi

Teraz wstawimy podane wartości do powyższego wzoru uzgadniania:

3*4 + (n-3) * 2 = 2*21

12+2n-6 = 42

2n = 42 - 6

2n=36

n = 18

Zatem w grafie G całkowita liczba wierzchołków = 18.

Przykład 3: Mamy tutaj graf, który ma 35 krawędzi, 4 wierzchołki stopnia 5, 5 wierzchołków stopnia 4 i 4 wierzchołki stopnia 3. Teraz obliczymy liczbę wierzchołków stopnia 2 na tym grafie.

Rozwiązanie: Za pomocą powyższego wykresu otrzymaliśmy następujące szczegóły:

Liczba krawędzi = 35

Liczba wierzchołków stopnia 5 = 4

Liczba wierzchołków stopnia 4 = 5

Liczba wierzchołków stopnia 3 = 4

Załóżmy teraz, że liczba wierzchołków stopnia 2 = n

Korzystając z twierdzenia o uścisku dłoni, mamy następujące rzeczy:

Suma stopnia wszystkich wierzchołków = 2 * Liczba krawędzi

Teraz wstawimy podane wartości do powyższego wzoru uzgadniania:

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

Zatem w grafie G liczba wierzchołków stopnia 2 = 9.

Przykład 4: Tutaj mamy graf, który ma 24 krawędzie, a stopień każdego wierzchołka wynosi k. Teraz na podstawie podanych opcji ustalimy możliwą liczbę wierzchołków.

1. piętnaście
2. 20
3. 8
4. 10

Rozwiązanie: Za pomocą powyższego wykresu otrzymaliśmy następujące szczegóły:

Liczba krawędzi = 24

Stopień każdego wierzchołka = k

Załóżmy teraz, że liczba wierzchołków = n

Korzystając z twierdzenia o uścisku dłoni, mamy następujące rzeczy:

Suma stopnia wszystkich wierzchołków = 2 * Liczba krawędzi

Teraz wstawimy podane wartości do powyższego wzoru uzgadniania:

co to jest stos Java

N*k = 2*24

K = 48/ok

Obowiązkowe jest, aby liczba całkowita była zawarta w stopniu dowolnego wierzchołka.

Zatem w powyższym równaniu możemy użyć tylko tych typów wartości n, które dają nam całkowitą wartość k.

Teraz sprawdzimy podane powyżej opcje, umieszczając je kolejno w miejscu n w następujący sposób:

• Dla n = 15 otrzymamy k = 3,2, co nie jest liczbą całkowitą.
• Dla n = 20 otrzymamy k = 2,4, co nie jest liczbą całkowitą.
• Dla n = 8 otrzymamy k = 6, które jest liczbą całkowitą i jest to dozwolone.
• Dla n = 10 otrzymamy k = 4,8, co nie jest liczbą całkowitą.

Zatem właściwą opcją jest opcja C.