Graafi klikk ja vöö: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
P kaka > kaks |
|||
16. rida:
== Klikiprobleem ==
Efektiivse [[algoritm]]i koostamist suurima kliki tuvastamiseks nimetatakse (analoogiliselt [[isomorfismiprobleem]]iga) ''klikiprobleemiks'' <ref> 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 </ref> <ref> A. Dharwadker, ''The Clique Algorithm'', Proc. Institute of Mathematics, Amazon Books, ISBN 1466391219 </ref>. Niisuguse algoritmi [[algoritmiline keerukus|ajalist keerukust]] peetakse ''mittepolünomiaalseks'' '''NP'''. Klikiprobleem on populaarne, nende tuvastusalgoritme on koostatud palju, milledest suurele hulgale on paraku leitud kontranäiteid. Nö vööprobleemi
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 [[Struktuurisemiootika|semiootilise mudeli]] abil on võimalik tuvastada vöö- ja klikkregulaarse graafi lõikuvad (või sidusad) ''n''-vööd ja ''n''-klikid.
| |||