Euleri tee (ehk Euleri ahel) graafis on tee, mis kulgeb graafi kõiki servi pidi, läbides igat serva üks kord (võrdle Hamiltoni graafiga). Pildil oleva Königsbergi sildade probleemi lahendamine Leonhard Euleri poolt 1736. aastal pani aluse graafiteooria tekkele. Euleri tsükkel — Euleri tee, mis suletult moodustab tsükli.Loengu kava. 1 Graafi definitsioon ja lihtsamad omadused. 2 Teed, tsüklid ja sidusus. 3 Euleri graafid. 4 Hamlitoni graafid. Jaan Penjam, email: jaan@cs.ioc.ee. Diskreetne Matemaatika II: Graafiteooria.G = (V, E) - graaf. V - lõplik tippude hulk. E C V x V (tipupaaride hulga alamhulk). Kui E elemente vaadeldakse kaheelemendiliste hulkadena (tippude järjekord paaris ei ole oluline), siis nimetatakse graafi orienteerimata graafiks ning hulka E graafi servade hulgaks. Kui E elemente vaadeldakse järjestatud tipupaaridena, siis .Tee (ingl walk) graafis on järjend (v0,e1,v1,.,el,vl), kus v0,.,vl on tipud ning e1,.,el kaared/servad, nii et iga i = 1,.,l korral ei on kaar, mis läheb tipust vi−1 tippu vi. Tippu v0 nimetatakse selle tee algustipuks (ingl initial vertex) ja tippu vl lõpptipuks (ingl terminal vertex). Ahel (ingl path) on tee, milles kaared/servad ei kordu.Eelpool defineeritud graaf on lihtgraaf ehk harilik graaf. Graaf, mille tipupaaride vahel võib esineda mitu serva, on multigraaf. Graaf, mille servad on suunatud, on suunatud graaf ehk orienteeritud graaf. Suunatud serva nimetatakse kaareks või nooleks. Täielikult hargnev graaf on puu. Graaf, mille seostele on omistatud .
You may look: