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.

Määratlusi

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.

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

Graaf, mille kõik tipud on omavahel naabertipud, on täisgraaf. Ilma seosteta graaf on tühigraaf.

Täielikult hargnev graafi on puu.

Graaf, mille tippudeks on originaali servad ja servadeks originaali tipud on servagraaf.

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.

Peale nende esineb veel eriliste omadustega nimelisi graafi nagu Euleri graaf, Hamiltoni graaf, Peterseni graaf, Heawood'i graaf jt.

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

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) kusjuures lühim on vöö (joonisel 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 lihtgraafi nimetatakse vahest ka sümmeetriliseks graafiks. See ei ole korrektne, sest sümmeetrial on siin hoopis teine tähendus.

Graafi sümmeetria on graafi tippude ja tipupaaride omadus jaguneda nö sümmeetriaklassideks, mida erinevates käsitlustes ka ekvivalentsus- või transitiivsusklassideks või orbiitideks nimetatud on.

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.

Graafi sümmeetriaomadused omavad olulist tähendust graafi struktuuri määratlemisel.

Graafi struktuur

Graafi struktuur on graafi tippude ja tipupaaride omadus olla organiseeritud, omavahel seostatud mingil kindlal viisil ehk kindlas vormis. Graafi struktuur on isomorfsete graafide täielik invariant.

Graafi struktuurist räägitakse tavaliselt kui selle mingitest omadustest. Näiteks, graafi „algebralise struktuuri“ mõeldakse selle teatud algebralisi omadusi.

Graafi struktuur on määratletav tema sümmeetriaomaduste, klikkide, vööde ja teiste atribuutide põhjal.

Kirjandus

Buldas, Ahto; Laud, Peeter; Willemson, Jan 2003. Graafid. Tartu: TÜ Kirjastus.
Harary, Frank 1969. Graph Theory. New York: Addison-Wesley.
Puusemp, Peeter 2000. Graafiteooria elemente. Tallinn: TTÜ Kirjastus.
Tevet, John-Tagore, 2009. Graafide varjatud külgi. Tallinn: S.E.R.R.

Vaata ka