"semigraaf" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

Sidususkomponent- graafi G sidususkomponent on selle graafi G maksimaalne sidus alamgraaf. [32]. Euleri graafid. Hamiltoni tsüklid. Euleri tsükliks graafis G=(V,E) nimetatakse sellist servade järjestust, mis läbib graafi igat serva täpselt 1 kord ning servade järjestus lõppeb oma alguspunktis. Euleri graaf on graaf, mis sisaldab Euleri tsüklit. Euleri ahel on lahtine servade järjestus, kus igat serva läbitakse täpselt 1 kord. Euleri semigraaf on graaf, mis sisaldab Euleri ahelat. Kui mingi graaf on Euleri graaf, siis: a). Graaf on sidus. b). Kõikkide tippude aste peab olema paarisarvuline. c). Servade hulk E esitub paarikaupa lõikumatute tsüklite ühendina. 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.