Graaf

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

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

## Määratlusi
* Eespool 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*.
* Sidus ja tsükliteta graaf on ***puu***.
* 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***.
* Graafi „vastandgraaf” ehk ***[[graafi täiend]]*** on see, mis omab servi seal, kus originaal neid ei oma. Näiteks tühigraafi täiend on täisgraaf ja vastupidi.
* Graaf, mille tipud jagunevad kahte hulka, kus servad esinevad ainult erinevatesse hulkadesse kuuluvate tippude vahel, on ***[[kahealuseline graaf]]***.
* Graaf, mille tippudeks on originaali servad ja servadeks originaali tipud, on ***[[servagraaf]]***.

Peale nende esineb veel eriliste omadustega nimelisi graafe nagu Euleri graaf, Hamiltoni graaf, Peterseni graaf, Heawoodi graaf, Folkmani graaf jt.

## 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 teidpidi ühendatud, siis on graaf *[[sidus graaf|sidus]]*. Graafi mittesidusaid 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 servipidi täielikult seostatud (naabertippudeks olevate) tippude alamhulk on ''klikk'' (joonisel 1, 2, 5).

Omavahel mittenaabertippudeks olevate tippude alamhulgad, niisugused, mis on servipidi seotud teiste samasugustega, moodustavad *aluseid*. (Esineb kahe- ja mitmealuselisi graafe.)

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

## Graafi regulaarsusi
Graaf, mille kõikidel tippudel on võrdne arv *k* naabertippe, on *[[regulaarne graaf|regulaarne]]*, täpsemini *k-valents- ehk astakregulaarne*.

*k*-valentsregulaarne graaf, mille iga naabertippude paar omab *a* ühist naabertippu ja iga mittenaabertippude paar *b* ühist naabertippu on *[[regulaarne graaf|tugevregulaarne]]*.

Graaf, mille iga tipu kõik mittenaabertipud asuvad kaugusel *d*, on *[[regulaarne graaf|d-distantsregulaarne]]*.

Graaf, mille kõik tipud asuvad ringis (vöös) ümbermõõduga *d*, on *[[regulaarne graaf|d-vööregulaarne]]*.

Graaf, mille kõik tipud asuvad klikis võimsusega *n*, on *[[regulaarne graaf|n-klikkregulaarne]]*. 

## Sümmeetriast graafis
Harilikku ehk lihtgraafi nimetatakse oma suunamatute servade pärast vahel 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 *sümmeetriaklassidesse*, mida eri käsitlustes on nimetatud ka *[[graafi orbiit|orbiitideks]]*, *ekvivalentsus- või transitiivsusklassideks*.

Tippudest transitiivset graafi, mille kõik tipud kuuluvad ühte orbiiti nimetatakse *tippudest sümmeetriliseks*.

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

Graafi, mille kõik servad kuuluvad ühte ja kõik „mitteservad” 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“ all mõeldakse selle teatud algebralisi omadusi. 

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

## Vaata ka
*Regulaarne graaf
*Tasandiline graaf
*Juhuslik graaf
*Sidus graaf
*Täisgraaf
*Isetäienduv graaf
*Servagraaf
*Orbiitgraaf
*Graafi invariant
*Graafi kanooniline esitus
*Graafi paljuaspektilisus
*Graafi struktuur
*Graafi orbiit
*Graafide süsteem
*Graafiteooria
*Struktuurisemiootika
*Graafi semioos
*Graafi värvimine
*Graafide identifitseerimine
*Graafi seosmaatriks

## Kirjandus
* A. Buldas, P. Laud, J. Villemson. 2003 *Graafid*. Tartu, ISBN 9789949118182.
* F. Harary. 1972. *Graph Theory*. Addisson-Wesley, ISBN 0201027879.
* A. Dharwadker, B. Pirzada. 2011. *Graph Theory*. Amazon Books, ISBN 9781466254992.
* J.-T. Tevet. 2010. *Graafide varjatud külgi*. Tallinn: S.E.R.R. ISBN 9789949213108