Voimme kutsua kättelyteoriaa myös asteen summalauseeksi tai kättelylemmaksi. Kättelyteoria väittää, että graafin kaikkien kärkien asteiden summa on kaksinkertainen graafin sisältämien reunojen lukumäärään verrattuna. Kättelyteorian symbolinen esitys kuvataan seuraavasti:
Tässä,
'd' käytetään osoittamaan kärjen astetta.
'v':tä käytetään osoittamaan kärki.
e:tä käytetään osoittamaan reunat.
Kättelylause:
Kättelylauseessa on joitain johtopäätöksiä, jotka on tehtävä ja jotka kuvataan seuraavasti:
Missä tahansa kaaviossa:
- Kaikkien pisteiden asteiden summalla täytyy olla parilliset luvut.
- Jos kaikilla pisteillä on parittomat asteet, niin näiden pisteiden asteiden summan tulee aina pysyä parillisena.
- Jos on joitain pisteitä, joilla on pariton aste, niin näiden pisteiden määrä on parillinen.
Esimerkkejä kättelyteoriasta
Kättelyteoriasta on useita esimerkkejä, ja joitain esimerkkejä kuvataan seuraavasti:
Esimerkki 1: Tässä meillä on graafi, jossa kunkin kärjen aste on 4 ja 24 reunaa. Nyt saamme selville tämän graafin kärkien lukumäärän.
Ratkaisu: Yllä olevan kaavion avulla olemme saaneet seuraavat tiedot:
binääri bcd:hen
Jokaisen kärjen aste = 24
Reunojen lukumäärä = 24
Nyt oletetaan pisteiden lukumäärä = n
Kädenpuristuslauseen avulla meillä on seuraavat asiat:
Kaikkien pisteiden asteiden summa = 2 * Reunojen lukumäärä
Nyt laitamme annetut arvot yllä olevaan kättelykaavaan:
n*4 = 2*24
n = 2*6
n = 12
Siten graafissa G kärkien lukumäärä = 12.
Esimerkki 2: Tässä meillä on graafi, jossa on 21 reunaa, 3 asteen 4 kärkeä ja kaikki muut asteen 2 kärjet. Nyt selvitetään tämän graafin kärkien kokonaismäärä.
Ratkaisu: Yllä olevan kaavion avulla olemme saaneet seuraavat tiedot:
Asteen 4 kärkien lukumäärä = 3
Reunojen lukumäärä = 21
Kaikilla muilla huippupisteillä on aste 2
Nyt oletetaan pisteiden lukumäärä = n
Kädenpuristuslauseen avulla meillä on seuraavat asiat:
muuntaa merkkijono int javaksi
Kaikkien pisteiden asteiden summa = 2 * Reunojen lukumäärä
Nyt laitamme annetut arvot yllä olevaan kättelykaavaan:
3*4 + (n-3)*2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n = 36
n = 18
Siten graafissa G pisteiden kokonaismäärä = 18.
nimisopimus java
Esimerkki 3: Tässä meillä on graafi, jossa on 35 kulmaa, 4 asteen 5 kärkeä, 5 asteen 4 pistettä ja 4 asteen 3 pistettä. Nyt selvitetään tämän graafin asteen 2 kärkien lukumäärä.
Ratkaisu: Yllä olevan kaavion avulla olemme saaneet seuraavat tiedot:
Reunojen lukumäärä = 35
Asteen 5 kärkien lukumäärä = 4
Asteen 4 kärkien lukumäärä = 5
Asteen 3 kärkien lukumäärä = 4
Nyt oletetaan asteen 2 kärkien lukumäärä = n
Kädenpuristuslauseen avulla meillä on seuraavat asiat:
Kaikkien pisteiden asteiden summa = 2 * Reunojen lukumäärä
Nyt laitamme annetut arvot yllä olevaan kättelykaavaan:
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
Siten graafissa G asteen 2 kärkien lukumäärä = 9.
Esimerkki 4: Tässä meillä on graafi, jossa on 24 reunaa ja kunkin kärjen aste on k. Nyt selvitetään mahdollinen kärkimäärä annetuista vaihtoehdoista.
- viisitoista
- kaksikymmentä
- 8
- 10
Ratkaisu: Yllä olevan kaavion avulla olemme saaneet seuraavat tiedot:
Reunojen lukumäärä = 24
Jokaisen kärjen aste = k
Nyt oletetaan pisteiden lukumäärä = n
Kädenpuristuslauseen avulla meillä on seuraavat asiat:
Kaikkien pisteiden asteiden summa = 2 * Reunojen lukumäärä
Nyt laitamme annetut arvot yllä olevaan kättelykaavaan:
N*k = 2*24
K = 48/n
primitiiviset tietotyypit javassa
On pakollista, että minkä tahansa kärjen aste sisältää kokonaisluvun.
Voimme siis käyttää vain sellaisia n:n arvoja yllä olevassa yhtälössä, joka antaa meille k:n kokonaisarvon.
Nyt tarkistamme yllä olevat vaihtoehdot asettamalla ne n:n tilalle yksitellen näin:
- Kun n = 15, saamme k = 3,2, joka ei ole kokonaisluku.
- Jos n = 20, saamme k = 2,4, joka ei ole kokonaisluku.
- Kun n = 8, saamme k = 6, joka on kokonaisluku, ja se on sallittu.
- Jos n = 10, saamme k = 4,8, joka ei ole kokonaisluku.
Oikea vaihtoehto on siis vaihtoehto C.