Nevezhetjük a kézfogás-elméletet fokösszegtételnek vagy kézfogási lemmának is. A kézfogás elmélet azt állítja, hogy a gráf összes csúcsának fokszámának összege kétszerese a gráf éleinek számának. A kézfogás-elmélet szimbolikus ábrázolását a következőképpen írjuk le:
Itt,
A 'd' a csúcs fokának jelzésére szolgál.
A 'v' a csúcsot jelöli.
Az 'e' az élek jelzésére szolgál.
Kézfogás tétel:
A kézfogás tételben van néhány levonandó következtetés, amelyeket az alábbiak szerint írunk le:
Bármely grafikonon:
- Az összes csúcs fokszámának páros számnak kell lennie.
- Ha minden csúcsnak páratlan foka van, akkor ezeknek a csúcsoknak a fokszámának mindig párosnak kell maradnia.
- Ha vannak olyan csúcsok, amelyeknek páratlan foka van, akkor ezeknek a csúcsoknak a száma páros lesz.
Példák a kézfogás elméletére
Különféle példák vannak a kézfogás-elméletre, és néhány példát a következőképpen írunk le:
1. példa: Itt van egy gráfunk, amelyben minden csúcs fokszáma 4 és 24 él. Most megtudjuk a gráf csúcsainak számát.
Megoldás: A fenti grafikon segítségével a következő részleteket kaptuk:
Mindegyik csúcs foka = 24
Élek száma = 24
Most feltételezzük a csúcsok számát = n
A Kézfogás tétel segítségével a következő dolgokat kapjuk:
Az összes csúcs fokának összege = 2 * Élek száma
Most a megadott értékeket a fenti kézfogási képletbe helyezzük:
ankita dave
n*4 = 2*24
n = 2*6
n = 12
Így a G gráfban a csúcsok száma = 12.
2. példa: Itt van egy gráfunk, amelynek 21 éle, 3 4-es fokú csúcsa és minden más 2-es fokú csúcsa van. Most megtudjuk, hogy a gráfban hány csúcs van.
Megoldás: A fenti grafikon segítségével a következő részleteket kaptuk:
A 4. fok csúcsainak száma = 3
Élek száma = 21
Az összes többi csúcs 2-es fokozatú
Most feltételezzük a csúcsok számát = n
A Kézfogás tétel segítségével a következő dolgokat kapjuk:
aki feltalálta az iskolát
Az összes csúcs fokának összege = 2 * Élek száma
Most a megadott értékeket a fenti kézfogási képletbe helyezzük:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42-6
2n = 36
n = 18
Így a G gráfban a csúcsok teljes száma = 18.
3. példa: Itt van egy gráfunk, amelynek 35 éle, 4 5. fokú csúcsa, 5 4. fokú csúcsa és 4 3. fokú csúcsa van. Most megtudjuk, hány csúcs van ebben a gráfban.
Megoldás: A fenti grafikon segítségével a következő részleteket kaptuk:
Élek száma = 35
Az 5. fok csúcsainak száma = 4
A 4. fokozatú csúcsok száma = 5
A 3. fokozatú csúcsok száma = 4
Most feltételezzük a 2-es fokú csúcsok számát = n
A Kézfogás tétel segítségével a következő dolgokat kapjuk:
Az összes csúcs fokának összege = 2 * Élek száma
Most a megadott értékeket a fenti kézfogási képletbe helyezzük:
beillesztési rendezés java-ban
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
Így a G gráfban a 2-es fokú csúcsok száma = 9.
4. példa: Itt van egy gráfunk, amelynek 24 éle van, és mindegyik csúcs foka k. Most megtudjuk a lehetséges csúcsok számát a megadott opciók közül.
- tizenöt
- húsz
- 8
- 10
Megoldás: A fenti grafikon segítségével a következő részleteket kaptuk:
Élek száma = 24
Az egyes csúcsok foka = k
Most feltételezzük a csúcsok számát = n
A Kézfogás tétel segítségével a következő dolgokat kapjuk:
Az összes csúcs fokának összege = 2 * Élek száma
Most a megadott értékeket a fenti kézfogási képletbe helyezzük:
N*k = 2*24
K = 48/kb
Kötelező, hogy egy egész számot tartalmazzon bármely csúcs foka.
Tehát a fenti egyenletben csak azokat az n típusú értékeket használhatjuk, amelyek megadják a k egész értékét.
Most ellenőrizzük a fent megadott lehetőségeket úgy, hogy egyesével az n helyére helyezzük őket, így:
- Ha n = 15, akkor k = 3,2-t kapunk, ami nem egész szám.
- Ha n = 20, akkor k = 2,4-et kapunk, ami nem egész szám.
- Ha n = 8, akkor k = 6-ot kapunk, ami egy egész szám, és ez megengedett.
- Ha n = 10, akkor k = 4,8-at kapunk, ami nem egész szám.
Így a helyes opció a C.