Klick

Från Wikipedia
Hoppa till: navigering, sök
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 \{a,b,c\} 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 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 \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[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

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