Teóriu podávania rúk môžeme nazvať aj teorémom súčtu stupňov alebo lemmou podávania rúk. Teória podávania rúk hovorí, že súčet stupňov všetkých vrcholov grafu bude dvojnásobkom počtu hrán obsiahnutých v tomto grafe. Symbolické znázornenie teórie podávania rúk je opísané takto:
Tu,
„d“ sa používa na označenie stupňa vrcholu.
„v“ sa používa na označenie vrcholu.
„e“ sa používa na označenie hrán.
Veta o podávaní rúk:
Vo vete o podávaní rúk sú niektoré závery, ktoré je potrebné vyvodiť a ktoré sú opísané nasledovne:
V ľubovoľnom grafe:
- Pre súčet stupňov všetkých vrcholov musia byť párne čísla.
- Ak existujú nepárne stupne pre všetky vrcholy, potom súčet stupňov týchto vrcholov musí vždy zostať párny.
- Ak existujú vrcholy, ktoré majú nepárny stupeň, potom bude počet týchto vrcholov párny.
Príklady teórie podávania rúk
Existujú rôzne príklady teórie podávania rúk a niektoré z príkladov sú opísané takto:
Príklad 1: Tu máme graf, ktorý má stupeň každého vrcholu ako 4 a 24 hrán. Teraz zistíme počet vrcholov v tomto grafe.
Riešenie: Pomocou vyššie uvedeného grafu sme získali nasledujúce podrobnosti:
Stupeň každého vrcholu = 24
Počet hrán = 24
Teraz budeme predpokladať počet vrcholov = n
S pomocou teorému Handshaking máme nasledujúce veci:
Súčet stupňa všetkých vrcholov = 2 * Počet hrán
Teraz vložíme dané hodnoty do vyššie uvedeného vzorca na podanie ruky:
n*4 = 2*24
n = 2 x 6
n = 12
V grafe G je teda počet vrcholov = 12.
Príklad 2: Tu máme graf, ktorý má 21 hrán, 3 vrcholy stupňa 4 a všetky ostatné vrcholy stupňa 2. Teraz zistíme celkový počet vrcholov v tomto grafe.
Riešenie: Pomocou vyššie uvedeného grafu sme získali nasledujúce podrobnosti:
Počet vrcholov Stupňa 4 = 3
Počet hrán = 21
Všetky ostatné vrcholy majú stupeň 2
Teraz budeme predpokladať počet vrcholov = n
S pomocou teorému Handshaking máme nasledujúce veci:
Súčet stupňov všetkých vrcholov = 2 * Počet hrán
ako získať prístup k icloud fotografiám
Teraz vložíme dané hodnoty do vyššie uvedeného vzorca na podanie ruky:
3*4 + (n-3)*2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
V grafe G je teda celkový počet vrcholov = 18.
Príklad 3: Tu máme graf, ktorý má 35 hrán, 4 vrcholy stupňa 5, 5 vrcholov stupňa 4 a 4 vrcholy stupňa 3. Teraz zistíme počet vrcholov so stupňom 2 v tomto grafe.
Riešenie: Pomocou vyššie uvedeného grafu sme získali nasledujúce podrobnosti:
Počet hrán = 35
Počet vrcholov Stupňa 5 = 4
Počet vrcholov 4. stupňa = 5
Počet vrcholov 3. stupňa = 4
Teraz budeme predpokladať počet vrcholov 2. stupňa = n
S pomocou teorému Handshaking máme nasledujúce veci:
Súčet stupňov všetkých vrcholov = 2 * Počet hrán
Teraz vložíme dané hodnoty do vyššie uvedeného vzorca na podanie ruky:
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 grafe G je teda počet vrcholov 2. stupňa = 9.
Príklad 4: Tu máme graf, ktorý má 24 hrán a stupeň každého vrcholu je k. Teraz z daných možností zistíme možný počet vrcholov.
arraylist java sort
- pätnásť
- dvadsať
- 8
- 10
Riešenie: Pomocou vyššie uvedeného grafu sme získali nasledujúce podrobnosti:
Počet hrán = 24
Stupeň každého vrcholu = k
Teraz budeme predpokladať počet vrcholov = n
S pomocou teorému Handshaking máme nasledujúce veci:
Súčet stupňov všetkých vrcholov = 2 * Počet hrán
Teraz vložíme dané hodnoty do vyššie uvedeného vzorca na podanie ruky:
N*k = 2*24
K = 48/pribl
Je povinné, aby celé číslo obsahovalo stupeň ktoréhokoľvek vrcholu.
Takže vo vyššie uvedenej rovnici môžeme použiť iba tie typy hodnôt n, ktoré nám poskytujú celú hodnotu k.
Teraz skontrolujeme vyššie uvedené možnosti tak, že ich postupne umiestnime na miesto n takto:
- Pre n = 15 dostaneme k = 3,2, čo nie je celé číslo.
- Pre n = 20 dostaneme k = 2,4, čo nie je celé číslo.
- Pre n = 8 dostaneme k = 6, čo je celé číslo a je to povolené.
- Pre n = 10 dostaneme k = 4,8, čo nie je celé číslo.
Správnou možnosťou je teda možnosť C.