Klick

För andra betydelser, se Klick (olika betydelser).

En klick är inom matematik, specifikt grafteori, ett antal utvalda noder i en 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ändigt.^[1] 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 ${\displaystyle \omega (G)}$, är storleken på den största klicken i G. Detta kan även uttryckas som att ${\displaystyle \omega (G)}$ är det största heltalet r så att den kompletta grafen ${\displaystyle K_{r}}$ är en delgraf till G.

• Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1 
• Diestel, Reinhard (2005). Graph Theory. Springer Verlag. ISBN 3-540-26182-6