"sidususkomponendiga" - 1 õppematerjal

Diskreetne matemaatika II - viies kodutöö

Tähistan selle tipu t-ga ja olgu selle tipu aste a. Eemaldan graafist selle tipu t ja selle tipuga seotud servad(a serva). Tulemuseks saan graafi, millel on (n-1) tippu ja (m-a) serva. Eeldan, et väide kehtib saadud graafi korral, st et graafil (n-1) tipu ja (m-a) servaga on (n-1-m+a) 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