Min definisjon sier
A clique er en graf som har en kant som forbinder hvert par av hjørner
men som jeg forstår, forbinder en kant bare to hjørner. Som $ A-B $ .
Hvis vi ønsker å koble til tre hjørner, trenger vi minst to kanter. For eksempel $ ABC $ .
Jeg forstår ikke hvordan en kant kan koble hvert par av hjørnene.
Kommentarer
- Det ' er ikke en kant $ e $ som forbinder alle parene. For hvert par $ u, v \ i V $ er det en kant $ e_ {uv} $ som forbinder de to nodene. Det vil si at en klikk er en (under-) graf som inneholder alle mulige kanter.
Svar
Husker at en klikk er en delmengde $ C $ av hjørner av en ikke-rettet graf slik at undergrafen indusert av $ C $ er fullt tilkoblet. Det vil si hver annen distinkt toppunkt i $ C $ er koblet sammen med en distinkt kant av grafen. Dette betyr forskjellige kanter, ikke de samme.
Så på en klikk $ C $ som inneholder $ k $ vertices $ v_1, v_2, .., v_k $ , det er $ \ frac {k (k-1) } 2 $ kanter som forbinder dem, det er antallet mulige uordnede par på $ k $ -elementer.
Eksempel
Som du kan se i forrige bilde, dette er en klikk på fire hjørner $ \ {{1,2,3,4} \} $ , så det er en annen kant som forbinder hver kant (dvs. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Du kan telle dem og se at det er nøyaktig $ 6 = \ frac {4 \ ganger 3} {2} $ kanter.
Kommentarer
- Hvordan vet du at det er k (k-1) / 2 kanter?
- For hver 2 hjørner er det en kant. Hvor mange par av hjørnene har du fra $ n $? $ \ binom {n} {2} $