Teorii podání ruky můžeme také nazvat jako větu o součtu stupně nebo lemma pro podání ruky. Teorie handshakingu říká, že součet stupňů všech vrcholů grafu bude dvojnásobkem počtu hran obsažených v tomto grafu. Symbolická reprezentace teorie handshakingu je popsána následovně:
Tady,
'd' se používá k označení stupně vrcholu.
'v' se používá k označení vrcholu.
'e' se používá k označení hran.
Věta o podání ruky:
Ve větě o podání ruky jsou některé závěry, které je třeba vyvodit a které jsou popsány následovně:
V libovolném grafu:
xor v Javě
- Pro součet stupňů všech vrcholů musí existovat sudá čísla.
- Pokud jsou pro všechny vrcholy liché stupně, pak součet stupňů těchto vrcholů musí vždy zůstat sudý.
- Pokud existují některé vrcholy, které mají lichý stupeň, pak bude počet těchto vrcholů sudý.
Příklady teorie handshakingu
Existují různé příklady teorie handshakingu a některé příklady jsou popsány takto:
Příklad 1: Zde máme graf, který má stupeň každého vrcholu jako 4 a 24 hran. Nyní zjistíme počet vrcholů v tomto grafu.
Řešení: S pomocí výše uvedeného grafu jsme získali následující podrobnosti:
Stupeň každého vrcholu = 24
Počet hran = 24
Nyní budeme předpokládat počet vrcholů = n
S pomocí teorému Handshaking máme následující věci:
Součet stupně všech vrcholů = 2 * Počet hran
Nyní vložíme dané hodnoty do výše uvedeného vzorce pro handshaking:
n*4 = 2*24
n = 2*6
n = 12
V grafu G je tedy počet vrcholů = 12.
Příklad 2: Zde máme graf, který má 21 hran, 3 vrcholy stupně 4 a všechny ostatní vrcholy stupně 2. Nyní zjistíme celkový počet vrcholů v tomto grafu.
Řešení: S pomocí výše uvedeného grafu jsme získali následující podrobnosti:
Počet vrcholů stupně 4 = 3
Počet hran = 21
Všechny ostatní vrcholy mají stupeň 2
Nyní budeme předpokládat počet vrcholů = n
S pomocí teorému Handshaking máme následující věci:
Součet stupňů všech vrcholů = 2 * Počet hran
Nyní vložíme dané hodnoty do výše uvedeného vzorce pro handshaking:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
V grafu G je tedy celkový počet vrcholů = 18.
Příklad 3: Zde máme graf, který má 35 hran, 4 vrcholy stupně 5, 5 vrcholů stupně 4 a 4 vrcholy stupně 3. Nyní zjistíme počet vrcholů se stupněm 2 v tomto grafu.
Řešení: S pomocí výše uvedeného grafu jsme získali následující podrobnosti:
Počet hran = 35
Počet vrcholů stupně 5 = 4
Počet vrcholů stupně 4 = 5
Počet vrcholů stupně 3 = 4
Nyní budeme předpokládat počet vrcholů stupně 2 = n
S pomocí teorému Handshaking máme následující věci:
Součet stupňů všech vrcholů = 2 * Počet hran
Nyní vložíme dané hodnoty do výše uvedeného vzorce pro handshaking:
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
V grafu G je tedy počet vrcholů stupně 2 = 9.
Příklad 4: Zde máme graf, který má 24 hran a stupeň každého vrcholu je k. Nyní z daných možností zjistíme možný počet vrcholů.
- patnáct
- dvacet
- 8
- 10
Řešení: S pomocí výše uvedeného grafu jsme získali následující podrobnosti:
Počet hran = 24
Stupeň každého vrcholu = k
Nyní budeme předpokládat počet vrcholů = n
S pomocí teorému Handshaking máme následující věci:
Součet stupňů všech vrcholů = 2 * Počet hran
Nyní vložíme dané hodnoty do výše uvedeného vzorce pro handshaking:
N*k = 2*24
K = 48/cca
Je povinné, aby celé číslo obsahovalo stupeň libovolného vrcholu.
Můžeme tedy použít pouze ty typy hodnot n ve výše uvedené rovnici, které nám poskytují celou hodnotu k.
Nyní zkontrolujeme výše uvedené možnosti tak, že je vložíme jednu po druhé na místo n takto:
- Pro n = 15 dostaneme k = 3,2, což není celé číslo.
- Pro n = 20 dostaneme k = 2,4, což není celé číslo.
- Pro n = 8 dostaneme k = 6, což je celé číslo a je to povoleno.
- Pro n = 10 dostaneme k = 4,8, což není celé číslo.
Správnou možností je tedy možnost C.