Klick

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.

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

En graf med den enda klicken av storlek 3 markerad (noderna 1, 2 och 5).

En graf och dess komplementgraf. Klicken ${\displaystyle \{a,b,c\}}$ i grafen till vänster bildar en oberoende mängd i grafen till höger.

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.

Referenser

• 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

Noter

1. Richard M. Karp (1972). ”Reducibility Among Combinatorial Problems”. Complexity of Computer Computations. Plenum. sid. 85–103