Mijn definitie zegt
A clique is een graaf met een rand die elk paar hoekpunten verbindt.
maar zoals ik begrijp, verbindt een rand slechts twee hoekpunten. Zoals $ A-B $ .
Als we drie hoekpunten willen verbinden, hebben we minimaal twee randen nodig. Bijvoorbeeld $ ABC $ .
Ik begrijp niet hoe een rand elk paar hoekpunten kan verbinden.
Opmerkingen
- Het ' is niet één rand $ e $ die alle paren verbindt. Voor elk paar $ u, v \ in V $ is er een rand $ e_ {uv} $ die de twee knooppunten met elkaar verbindt. Dat wil zeggen, een kliek is een (sub-) graaf die alle mogelijke randen bevat.
Answer
Herinnerend dat een kliek een subset is $ C $ hoekpunten van een niet-gerichte graaf, zodat de subgraaf die wordt geïnduceerd door $ C $ is volledig verbonden. Dat wil zeggen, elke twee verschillende hoekpunten in $ C $ zijn verbonden door een aparte rand van de grafiek. Dit betekent verschillende randen, niet hetzelfde.
Dus op een kliek $ C $ met $ k $ hoekpunten $ v_1, v_2, .., v_k $ , er zijn $ \ frac {k (k-1) } 2 $ randen die ze verbinden, dat is het aantal mogelijke ongeordende paren op $ k $ elementen.
Voorbeeld
Zoals je kunt zien in de vorige picture, dit is een kliekje op vier hoekpunten $ \ {{1,2,3,4} \} $ , dus er is een andere rand die elke rand verbindt (bijv. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
U kunt ze tellen en zien dat er precies $ 6 = \ frac {4 \ times 3} {2} $ randen.
Reacties
- Hoe weet je dat er k (k-1) / 2 randen zijn?
- Voor elke 2 hoekpunten is er een rand. Hoeveel paar hoekpunten heb je vanaf $ n $? $ \ binom {n} {2} $