"sidususkomponendist" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

Hammiltoni ahelaks graafis G nimetatakse lahtist servade järjestust, kus igat tippu läbitakse täpselt 1 kord. Hamiltoni semigraaf on graaf, mis sisaldab Hammiltoni ahelat. Algoritm Hamiltoni tsükli leidmiseks graafis G: Hamiltoni tsükli leidmine on NP-keerukas ülesanne, seega puudub konkreetne algoritm. Leidub vaid üksikuid seaduspärasusi, mille järgi saab öelda, et graafis Hamiltoni tsüklit ei leidu- näiteks kui graaf koosneb kahest suuremast sidususkomponendist, mille vaheliseks ,,sillaks" on üksainus tipp, ei ole graafis kindlasti Hamiltoni ahelat. Teooria arendajaks oli William R. Hamilton(19. saj). [33]. Puud. Puude omadused. Puu on defineeritud, kui sidus tsükliteta orienteerimata graaf. Puude omadusi: a). Puu on alati sidus. b). Puus ei sisaldu tsükleid. c). Puus leidub alati n-1 serva, kus n on tippude arv. d). Iga puu koosseisus leiduv serv on sild. e)