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.

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

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 $\omega (G)$ , är storleken på den största klicken i G. Detta kan även uttryckas som att $\omega (G)$ är det största heltalet r så att den kompletta grafen $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

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

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

[1]