c. Kui suunatud ahelas või suunatud tsüklis ükski tipp ega serv ei kordu, siis on tegemist suunatud lihtahela või suunatud lihttsükliga. d. Suunatud graafe G = (V, E) ja G' = (V', E') nimetatakse isomorfseteks, kui leidub selline bijektiivne funktsioon f: V V', et graafis G on olemas kaar uv parajasti siis, kui graafis G' on olemas kaar f(u)f(v). e. Graafide isomorfismi näitamiseks tuleb konstrueerida vastav bijektsioon. f. Mitteisomorfismi näitamiseks saab kasutada invariante, mis säilivad isomorfismi korral: tippude sisend- ja väljundastmed, tsüklid jms. 49) a. Suunatud graafi nimetatakse tugevalt sidusaks, kui iga kahe tipu u ja v korral leidub suunatud ahel tipust u tippu v. Piltlikult öeldes tähendab tugev sidusus seda, et graafi igast tipust on võimalik liikuda mööda nooli igasse teise tippu. b. Suunatud graafi nimetatakse nõrgalt sidusaks, kui tema alusgraaf on sidus.
sidus komponent Teoreem suundade määramisest: kui sidusas (suunamata) graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud suunatud graaf on tugevalt sidus Suunatud graafe =(,) ja '=(',') nimetatakse isomorfseteks, kui leidub selline bijektiivne funktsioon : ', et graafis on olemas kaar parajasti siis, kui graafis ' on olemas kaar ()() o Isomorfismi näitamiseks tuleb konstrueerida vastav bijektsioon o Mitteisomorfismi näitamiseks saab kasutada invariante: tippude ja servade arvud, tippude sisend- ja väljundastmed, mingi pikkusega tsüklite olemasolu, sidususe näitajad Lühima tee leidmine laiuti otsimise teel: o Olgu kaalutud suunatud graaf, mille tipud on nummerdatud naturaalarvudega 1, 2, ... , , kaalud on kaarte pikkused o Moodustame kaks × -maatriksit ja o Maatriksi elemendid näitavad seni leitud lühima tee pikkust
41 Teoreem sisendastme ja väljundastme summast o Teoreem. Igas suunatud graafis on tippude sisendastmete summa võrdne tippude väljundastmete summaga. o Kui suunatud graafi alusgraaf ei ole sidus, siis kehtib teoreem ka alusgraafi iga sidusa komponendi kohta eraldi. 50. Suunatud ahel, suunatud tsükkel, lihtahel ja lihttsükkel. Suunatud graafide isomorfism. Isomorfismi ja mitteisomorfismi näitamine. [2] Suunatud ahel o DEF: Suunatud ahel on tippude järjend v0v1…vk, kus iga kaks järjestikust tippu vi ja vi+1 on ühendatud kaarega vivi+1. Suunatud tsükkel o DEF: Suunatud tsükkel on suunatud ahel, mis algab ja lõpeb samas tipus. 51. Tugev ja nõrk sidusus. Näited. Tugeva sidususe komponendid. [2] Tugev sidusus o Suunatud graafi nimetatakse tugevalt sidusaks, kui iga kahe tipu u ja v korral leidub suunatud ahel tipust u tippu v.
annaabi.ee 
