"tipupaaridele" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

f: A M ­ tippude märgendus g: R L ­ servade märgendus Ühesõnaga pannakse igale tipule ja igale servale vastavusse mingid arvud / tähed / funktsiooni väärtused. Märgendatud graafid G1 ja G2, mille märgenduste ((f1, g1) ja (f2, g2)) vahel leidub bijektiivne kujutus h: A1 A2, mis · graafid on võrdsed kui märgendamata graafid (aR1b h(a)R2h(b)) · f1(a) = f2(h(a)) samadele tippudele on samad märgendused · g1((a,b)) = g1((h(a), h(b))) ­ samadele tipupaaridele e kaartele on samad märgendused on võrdsed. Tippude jada (a1, ..., an) nimetatakse teeks pikkusega n (n >= 1)., kui igast tipust ai leidub kaar tippu ai+1. Tsükkel on tee, mille korral a1 = an. Graaf on tugevalt sidus, kui iga kahe tipu vahel eksisteerib tee. Tipu astak sisendite ja väljundite suhtes on vastavalt tipust sisenevate või tippu väljuvate kaarte arv . Puud + tsüklivabad orienteeritud graafid: graafi baas ­ tippude hulk, mille astak sisendi suhtes 0.