From Wikipedia, the free encyclopedia
Graaf 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.
Peale nende esineb veel eriliste omadustega nimelisi graafe nagu Euleri graaf, Hamiltoni graaf, Peterseni graaf, Heawoodi graaf, Folkmani graaf jt.
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. 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.)
Graaf, mille kõikidel tippudel on võrdne arv k naabertippe, on 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 tugevregulaarne.
Graaf, mille iga tipu kõik mittenaabertipud asuvad kaugusel d, on d-distantsregulaarne.
Graaf, mille kõik tipud asuvad ringis (vöös) ümbermõõduga d, on d-vööregulaarne.
Graaf, mille kõik tipud asuvad klikis võimsusega n, on n-klikkregulaarne.
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 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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.