"toespuus" - 1 õppematerjal

Graafid ja matemaatiline loogika eksamimaterjal

tippu o Et on sidus, siis igal sammul leidub serv, mis ühendab alamgraafi -1 mõne veel ühendamata tipuga o Algoritmi rakendamise tulemus -1 on puu, sest pole tsükleid ja ta on sidus. -1 sisaldab graafi kõiki tippu, järelikult on toespuu o Tõestame, et toespuu = -1 kaal on minimaalne o Invariant: igal sammul k saadud graaf sisaldub mingis minimaalse kaaluga toespuus. Kui see kehtib ka -1 kohta, siis on -1 ise minimaalse kaaluga toespuu o Baas: Ühetipuline graaf 0 sisaldub graafi igas toespuus o Samm: Sisaldugu puu mingis graafi G minimaalse kaaluga toespuus . Siis ka +1 sisaldub mingis minimaalse kaaluga toespuus o Lisame puule serva +1. Saadud graaf sisaldab tsüklit ja see tsükkel sisaldab serva +1. See tsükkel sisaldab ka servi, mis ei kuulu graafi +1, sest +1 on puu