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.
- piętnaście
- 20
- 8
- 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.