Graaf

Graaf $G=(V,E)$ on järjestatud paar mittetühjast hulgast V ja selle hulga elemendipaaride hulgast E.

Hulga V elemente nimetatakse graafi tippudeks ja hulga E elemente graafi servadeks või seosteks. Seostatud tipupaari nimetatakse naabertippudeks.

Teisisõnu, graaf koosneb tippudest, milledest osa (pildil), või kõik (täisgraaf), või mitte ükski (tühigraaf) on naabertipud.

Määratlusi

Graafi „vastandgraaf” ehk täiend on see, mis omab servi seal, kus originaal neid ei oma. Näiteks, tühigraafi täiend on täisgraaf, ja vastupidi.

Pildil esitatud graaf on harilik graaf.

Täielikult hargnevat graafi nimetatakse puuks.

Graaf, mille tipupaaride vahel võib esineda mitu serva, on multigraaf.

Graaf, mille servad kujutavad nooli on suunatud graaf ehk orienteeritud graaf.

Graaf, mille seostele on omistatud mingid väärtused on kaalutud graaf.

Graafe uurib graafiteooria. Graafi kirjelduse ja graafiteooria vahel ei ole kindlat piiri.

Graaf

Graafi olulisemaid osiseid

Servade ehk naabertippude jada kahe tipu vahel on tee (joonisel 1-5-4-6 ja 1-2-3-4-6). Lühimat teed kahe tipu vahel nimetatakse kauguseks.

Kui kõik tipud on omavahel teid pidi ühendatud, siis on graaf sidus. Graafi mitte sidusaid osi nimetatakse komponentideks.

Tee, mis algab ja lõpeb ühe ja sama tipuga (suletud tee) on ring ehk tsükkel (joonisel 1-2-3-4-5-1 ja 2-3-4-5-2).

Omavahel servi pidi täielikult seostatud (naabertippudeks olevate) tippude alamhulk on klikk (joonisel 1, 2, 5).

Omavahel mitte-naabertippudeks olevate tippude alamhulgad, niisugused, mis on servi pidi seotud teiste samasugustega, moodustavad aluseid. (Esineb kahe- ja mitmealuselisi graafe.)

Tippude (alam)hulka, millede omavaheline ümbervahetamine või –nummerdamine säilitab graafi struktuuri kujutab endast automorfismide transitiivsuspiirkonda, mida orbiidiks nimetatakse. See käib ka servade kohta. (Orbiidist suvalise tipu või serva eemaldamised saadud jääkgraafid on isomorfsed.)

Graafi regulaarsusi

Graaf, mille kõik tipud omavad võrdse arvu k naabertippe on regulaarne, täpsemini k-valents- ehk astakregulaarne.

k-valentsregulaarne graaf, mille iga naabertippude paar omab a ühist naabertippu ja iga mitte-naabertippude paar b ühist naabertippu on tugevregulaarne.

Graaf, mille iga tipu kõik mitte-naabertipud asuvad kaugusel d on d-distantsregulaarne.

Graaf, mille kõik tipud asuvad ringis pikkusega d on d-ringregulaarne.

Graaf, mille kõik tipud asuvad klikis võimsusega n on n-klikkregulaarne.

Sümmeetriast graafis

Harilikku ehk mitte-orienteeritud graafi nimetatakse vahest ka sümmeetriliseks graafiks.

Tippudest transitiivset graafi, mille kõik tipud kuuluvad ühte orbiiti nimetatakse tippudest sümmeetriliseks. Graafi orbiit on sisuliselt ekvivalentsusklass.

Tippudest sümmeetrilist graafi, mille kõik servad kuuluvad ühte orbiiti nimetatakse sümmeetriliseks graafiks.

Graafi, mille kõik servad kuuluvad ühte ja kõik „mitte-servad” kuuluvad teise orbiiti nimetatakse bisümmeetriliseks graafiks.

Kirjandus

• Harary, Frank 1969. Graph Theory. New York: Addison-Wesley.
• Puusemp, Peeter 2000. Graafiteooria elemente. Tallinn: TTÜ Kirjastus.
• Buldas, Ahto; Laud, Peeter; Willemson, Jan 2003. Graafid. Tartu: TÜ Kirjastus.
• Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. Tallinn: S.E.R.R.

Vaata ka

• Graafiteooria