Diskreetne matemaatika II - viies kodutöö
astmega 3 on ühendatud kolme tipuga, mille aste on 2.
Seega olen leidnud sellised tipud, mis on vasakpoolses graafis naabrid, kuid parempoolses graafis ei
ole(need on 2 tippu, mille aste on 3). See aga tähendab, et nende kahe graafi tipuhulkade vahel ei leidu
sellist bijektsiooni, et need kaks graafi oleksid isomorfsed. Seega ei ole need graafid isomorfsed.
Vastus: Need graafid ei ole isomorfsed.
ÜLESANNE 4.
Graafi G sidususkomponentideks nimetatakse tema maksimaalseid sidusaid alamgraafe. Vähim võimalik
graafi sidususkomponent on seega üksik tipp, mille aste on 0(ehk selline tipp, mis pole teistega
ühendatud).
Väide kehtib vaid juhul kui n m, sest graafil ei saa olla negatiivne arv sidususkomponente ning juhul n =
m on tal 0 sidususkomponenti ehk tegemist on tühja graafiga, mis on lubatud olukord.
Tõestan väite induktsiooniga.
Baas. Väide kehtib n = 0 ja m = 0 korral, n m = 0 ehk graafil on 0 sidususkomponenti
annaabi.ee 
