ITT0030 Diskreetne matemaatika II - eksamikonspekt
Algoritm Euleri tsükli leidmiseks graafis G: Esmalt eraldatakse G servade hulgast
ükshaaval tsüklid ning seejärel pannakse tsüklitest kokku Euleri ahel.
Teooria arendajaks oli Leonhard Euler(18. saj) Köeningsbergi sildade probleem.
Hamiltoni tsükliks graafis G = (V,E) nimetatakse sellist graafi servade järjestust, mis läbib
graafi igat tippu täpselt 1 kord ning servade järjestus lõppeb oma alguspunktis.
Hamiltoni graaf on graaf, mis sisaldab Hamiltoni tsüklit.
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
annaabi.ee 
