Graafi klikk ja vöö

**Klikk** on hariliku graafi alamgraaf, mille iga tipp on servade kaudu seotud selle alamgraafi teiste tippudega.

**Vöö** on graafi alamgraaf, mille tipud moodustavad väikseima suletud tee ehk ahela.

## Selgitus
Kui graafi kõik tipud on omavahel seotud, siis on see täisgraaf. Seega, klikk on graafi täis-alamgraaf. Mõiste *klikk* võtsid kasutusele Luce ja Perry (1949), kes rakendasid neid omavahel suhtlevate inimrühmade modelleerimiseks sotsiaalses keskkonnas. Klikkidel on palju rakendusi erinevates teadusharudes.

Kui suletud ahel ei ole väikseim, siis on see *ring* või suunatud graafi puhul *tsükkel*. Vööl ei ole palju rakendusi kuid teatud kaalutlustel on sobiv seda koos klikiga käsitleda.

Kliki definitsiooni kohaselt on väikseim klikk kaheelemendiline – 2-klikk (samas nimetatakse üksikut tippu 1-klikiks). 3-klikki nimetatakse *triangliks* ning see on ühtlasi ka 3-vöö. Näites esitatud graafil on 23 1-klikki (tippu), 42 2-klikk (serva), 11 iseseisvat 3-klikki (helesinised trianglid) ja kaks 4-klikki (tumesinine). Esitatud graafil on kaks 4-vööd ja üks 8-vöö (valge, kuid järgida ka definitsiooni).

Tavaliselt huvitutakse suurima kliki ja suurima vöö *võimsusest*. Antud juhul on graafi *klikinumber* 4 ja *vöönumber* 8.

Kliki vastand ehk täiend on graaf, mis omab servi seal kus need originaalis puuduvad.

## Klikiprobleem
Efektiivse algoritmi koostamist suurima kliki tuvastamiseks nimetatakse (analoogiliselt isomorfismiprobleemiga) *klikiprobleemiks* . Niisuguse algoritmi ajalist keerukust peetakse *mittepolünomiaalseks* **NP**. Klikiprobleem on populaarne, nende tuvastusalgoritme on koostatud palju, millest suurele hulgale on paraku leitud kontranäiteid. N-ö vööprobleemi vastu tuntakse vähem huvi.

Klikialgoritmid piirduvad tavaliselt klikinumbri, paremal juhul ka kliki enda väljatoomisega. *Transitiivses* (tippudest sümmeetrilises) graafis ei eksisteeri üksikut ja ainsat klikki, selles esineb n-ö ***klikkregulaarsus***, st *lõikuvate* või *sidusate* klikkide kontiinuum, mille puhul paljud klikialgoritmid ei toimi. Graafi semiootilise mudeli abil on võimalik tuvastada vöö- ja klikkregulaarse graafi lõikuvad (või sidusad) *n*-vööd ja *n*-klikid.

Pilt:Petersen1 tiny.svg|5-vööregulaarne Peterseni graaf
Pilt:Heawood_Graph.svg|6-vööregulaarne Heawood’i graaf
Pilt:McGee graph.svg|7-vööregulaarne McGee graaf
Pilt:Tutte eight cage.svg|8-vööregulaarne Tutte–Coxeter'i graaf

Kolmevalentseid ***vööregulaarseid*** graafe nimetatakse *kage’ks*. Peterseni graaf on ***5-vöö-regulaarne***, selles on kaksteist 5-vööd. Iga tipp esineb kuues vöös, iga serv esineb neljas vöös. Peterseni graafi ***täiendis*** on viis lõikuvat 4-klikki. See on ***4-klikk-regulaarne***, iga tipp esineb kahes klikis, iga serv ühes klikis. Peterseni graaf ja selle täiend on ***tugevalt regulaarsed***.

Heawoodi graaf on ***kahealuseline*** (kaks sõltumatut tipuhulka), kuid mitte *bi-klikk*. Sellest järeldub, et selle *täiend* koosneb kahest omavahel sidusast 7-klikist ning on ***7-klikkregulaarne***. Klikid vastavad originaali alustele.

Klikid ja vööd on graafi sümmeetria kõrval selle olulised osised, ilma nendeta ei ole graafi struktuur määratletav.

## Matemaatilisi tulemusi
Turáni teoreemis (1941) väidetakse, et iga tihe graaf sisaldab klikki. Ramsey teoreem (1990) väidab, et iga graaf või selle täiend sisaldab klikki võimsusega vähemalt logaritm tippude arvust. Hadwigeri seni tõestamata hüpoteesis väidetakse, et kõige suurema kliki võimsus on seotud graafi kromaatilise arvuga.

## Viited