Min definition siger
A clique er en graf, der har en kant, der forbinder hvert par af hjørner
men som jeg forstår, forbinder en kant kun to hjørner. Ligesom $ A-B $ .
Hvis vi vil forbinde tre hjørner, har vi brug for mindst to kanter. For eksempel $ ABC $ .
Jeg forstår ikke, hvordan en kant kan forbinde hvert par af hjørner.
Kommentarer
- Det ' er ikke en kant $ e $, der forbinder alle parene. For hvert par $ u, v \ i V $ er der en kant $ e_ {uv} $, der forbinder de to knudepunkter. Det vil sige, en klik er en (under-) graf, der indeholder alle mulige kanter.
Svar
Husker, at en klik er et undersæt $ C $ af hjørner af en ikke-rettet graf, således at undergrafen fremkaldt af $ C $ er fuldt forbundet. Det vil sige hver to forskellige hjørner i $ C $ er forbundet med en tydelig kant i grafen. Dette betyder forskellige kanter, ikke de samme.
Så på en klik $ C $ indeholdende $ k $ vertices $ v_1, v_2, .., v_k $ , der er $ \ frac {k (k-1) } 2 $ kanter, der forbinder dem, det vil sige antallet af mulige ikke-ordnede par på $ k $ -elementer.
Eksempel
Som du kan se i det foregående billede, dette er en klik på fire hjørner $ \ {{1,2,3,4} \} $ , så der er en anden kant, der forbinder hver kant (dvs. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Du kan tælle dem og se, at der er nøjagtigt $ 6 = \ frac {4 \ gange 3} {2} $ kanter.
Kommentarer
- Hvordan ved du, at der er k (k-1) / 2 kanter?
- For hver 2 hjørner er der en kant. Hvor mange par af hjørner har du fra $ n $? $ \ binom {n} {2} $