Graafi klikk ja vöö

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

Graafi klikid ja vööd

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

Selgitus muuda

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).

Tavapäraselt 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 muuda

Efektiivse algoritmi koostamist suurima kliki tuvastamiseks nimetatakse (analoogiliselt isomorfismiprobleemiga) klikiprobleemiks [1][2]. 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.

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 muuda

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 muuda

  1. D. Kumlander. A simple and efficient algorithm for the maximum clique finding reusing a heuristicvertex colouring. – IADS International Journal on Comp. Sci. and Information System, vol. 1, no. 2, 2006, 32-49
  2. A. Dharwadker, The Clique Algorithm, Proc. Amazon Books, ISBN 9781466391219