Min definition säger
A klick är ett diagram som har en kant som förbinder varje par av hörn
men som jag förstår ansluter en kant bara två hörn. Som $ A-B $ .
Om vi vill ansluta tre hörn behöver vi minst två kanter. Till exempel $ ABC $ .
Jag förstår inte hur en kant kan ansluta varje par av hörn.
Kommentarer
- Det ' är inte en kant $ e $ som förbinder alla par. För varje par $ u, v \ i V $ finns en kant $ e_ {uv} $ som förbinder de två noderna. Det vill säga en klick är ett (under-) diagram som innehåller alla möjliga kanter.
Svar
Påminner om att en klick är en delmängd $ C $ av hörn i en oriktad graf så att subgrafen som induceras av $ C $ är helt ansluten. Det vill säga varannan distinkt hörn i $ C $ är anslutna med en distinkt kant i diagrammet. Detta betyder olika kanter, inte samma.
Så på en klick $ C $ som innehåller $ k $ vertices $ v_1, v_2, .., v_k $ , det finns $ \ frac {k (k-1) } 2 $ kanter som förbinder dem, det vill säga antalet möjliga oordnade par på $ k $ element.
Exempel
Som du kan se i föregående bild, detta är en klick på fyra hörn $ \ {{1,2,3,4} \} $ , så det finns en annan kant som förbinder varje kant (dvs. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Du kan räkna dem och se att det finns exakt $ 6 = \ frac {4 \ gånger 3} {2} $ kanter.
Kommentarer
- Hur vet du att det finns k (k-1) / 2 kanter?
- För varje 2 hörn finns det en kant. Hur många par av hörn har du från $ n $? $ \ binom {n} {2} $