Visa källa för Klick

{{olika betydelser}}
[[Fil:6n-graf-clique.svg|höger|miniatyr|stående|En graf med den enda klicken av storlek 3 markerad (noderna 1, 2 och 5).]]
[[Fil:Complement graph.svg|höger|miniatyr|stående|En graf och dess komplementgraf. Klicken <math>\{a,b,c\}</math> i grafen till vänster bildar en oberoende mängd i grafen till höger.]]

En '''klick''' är inom [[matematik]], specifikt [[grafteori]], ett antal utvalda noder i en [[graf (grafteori)|graf]] sådan att det i grafen finns en båge mellan varje par av noder. Annorlunda uttryckt är en klick en mängd av noder som inducerar en [[delgraf]] ''H'' i en graf ''G'' sådan att ''H'' är en [[komplett graf]]. Med storleken på en klick avses antalet noder som den innehåller. En klick i en graf bildar en [[oberoende mängd]] i dess [[komplementgraf]].

'''Klickproblemet''' är att, givet en graf, avgöra om det finns en klick av minst en given storlek i grafen. Klickproblemet är [[NP-fullständig]]t.<ref>{{bokref |författare = Richard M. Karp |kapitel =[http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] |titel = Complexity of Computer Computations |utgivare=Plenum |sid= 85–103 |år = 1972}}</ref> Detta hänger samman med NP-fullständigheten att hitta en oberoende mängd av given storlek, eftersom om man hittar en oberoende mängd i komplementgrafen har man hittat en klick i den ursprungliga grafen.

En graf ''G'':s '''klicktal''', ofta betecknat <math>\omega(G)</math>, är storleken på den största klicken i ''G''. Detta kan även uttryckas som att <math>\omega(G)</math> är det största heltalet ''r'' så att den kompletta grafen <math>K_r</math> är en delgraf till ''G''.

==Referenser==
*{{bokref |titel=Algebraic Graph Theory |efternamn=Godsil |förnamn=Chris |medförfattare=Gordon Royle|år=2001 |utgivare=Springer Verlag |isbn=0-387-95241-1 }}
*{{bokref |titel=Graph Theory |efternamn=Diestel |förnamn=Reinhard |år=2005 |utgivare=Springer Verlag |isbn=3-540-26182-6 |sid= }}

===Noter===
<references />

[[Kategori:Grafteori]]