"sidususkomponente" - 1 õppematerjal

Diskreetne matemaatika II - viies kodutöö

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. Kuna tegemist on tühja graafiga, siis on tal tõepoolest 0 sidususkomponenti ja väide kehtib n = 0 ja m = 0 korral. Induktsioonisamm. Olgu antud suvaline graaf. Valin selles graafis välja suvalise tipu. Tähistan selle tipu t-ga ja olgu selle tipu aste a.