"alamgraafiga" - 1 õppematerjal

Diskreetne matemaatika II - viies kodutöö

sidususkomponenti. Nüüd lisan selle eemaldatud tipu t graafi tagasi selliselt, et tema aste oleks maksimaalselt a. See aga tähendab, et ta on ühendatud maksimaalselt a graafi G sidususkomponendiga. Seega ühendab lisatud tipp t omavahel maksimaalselt a graafi G sidususkomponenti, see tähendab, et maksimaalselt a sidususkomponendi asemel saan ma ühe sidususkomponendi, sest sidususkomponendi puhul on tegemist maksimaalse sidusa alamgraafiga. Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton 104493 IAPB21 Seega, kui enne eeldasin, et graafil (n-1) tipu ja (m-a) servaga on (n-1-m+a) sidususkomponenti, siis tipu