Lehekülje Graaf lähteteksti vaatamine

'''Graaf''' <math>G=(V, E)</math> on [[järjestatud paar]] [[mittetühi hulk|mittetühjast hulgast]] ''V'' ja selle hulga elementide paaride [[hulk|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 [[hulk]]a, 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]], [[Heawood'i graaf|Heawoodi graaf]], [[Folkmani graaf]] jt.

==Graafi olulisemaid osiseid==
[[Pilt:6n-graf.svg‎|thumb|Graaf]]
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 [[Graafi klikk ja vöö|''vöö'']] (joonisel 2-3-4-5-2).

Omavahel servipidi täielikult seostatud (naabertippudeks olevate) tippude alamhulk on [[Graafi klikk ja vöö|''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 [[struktuur]]i, kujutab endast [[automorfism]]ide transitiivsuspiirkonda, mida nimetatakse [[graafi orbiit|orbiidiks]]. See käib ka servade kohta. (Orbiidist suvalise tipu või serva eemaldamisel saadud jääkgraafid on [[isomorfism|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''.

[[Transitiivne graaf|Tippudest transitiivset graafi]], mille kõik tipud kuuluvad ühte [[graafi orbiit|orbiiti]] nimetatakse ''tippudest sümmeetriliseks''.

Tippudest sümmeetrilist graafi, mille kõik servad kuuluvad ühte [[graafi orbiit|orbiiti]] nimetatakse ''servadest sümmeetriliseks graafiks''.

Graafi, mille kõik servad kuuluvad ühte ja kõik „mitteservad” kuuluvad teise [[graafi orbiit|orbiit]]i nimetatakse ''bisümmeetriliseks'' graafiks.

Graafi sümmeetriaomadused omavad olulist tähendust [[graafi struktuur]]i 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 [[isomorfism|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 [[graafi sümmeetria|sümmeetriaomaduste]], [[graafi klikk ja vöö|klikkide, vööde]] ja teiste [[struktuurisemiootika|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

[[Kategooria:Graafiteooria]]