Määritelmäni sanoo
A klikkaus on kaavio, jossa on reuna, joka yhdistää jokaisen kärkiparin
mutta ymmärrän, että reuna yhdistää vain kaksi kärkeä. Kuten $ A-B $ .
Jos haluamme yhdistää kolme kärkeä, tarvitsemme vähintään kaksi reunaa. Esimerkiksi $ ABC $ .
En ymmärrä, kuinka reuna voi yhdistää jokaisen kärjen parin.
Kommentit
- Se ' ei ole yhtä reunaa $ e $, joka yhdistää kaikki parit. Kullekin parille $ u, v \ V $: ssa on reuna $ e_ {uv} $, joka yhdistää nämä kaksi solmua. Toisin sanoen klikkaus on (ala) kaavio, joka sisältää kaikki mahdolliset reunat.
Vastaa
Palautetaan mieleen, että klikkaus on suuntaamattoman kaavion pisteiden osajoukko $ C $ , että $ C $ : n aiheuttama aligrafiikka on täysin kytketty. Toisin sanoen joka toinen erillinen piste $ C $ on liitetty kaavion erillisellä reunalla . Tämä tarkoittaa eri reunoja, ei samoja.
Joten klikkauksella $ C $ , joka sisältää $ k $ kärjet $ v_1, v_2, .., v_k $ , on $ \ frac {k (k-1) } 2 $ reunaa, jotka yhdistävät ne, eli mahdollisten järjestämättömien parien määrä $ k $ -elementeissä.
Esimerkki
Kuten voit nähdä edellisestä kuva, tämä on klikkaus neljään kärkeen $ \ {{1,2,3,4} \} $ , joten jokaisen reunan yhdistää erilainen reuna (ts. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Voit laskea ne ja nähdä, että niitä on täsmälleen $ 6 = \ frac {4 \ kertaa 3} {2} $ reunat.
Kommentit
- Mistä tiedät, että reunoja on k (k-1) / 2?
- Jokaista 2 kärkeä kohti on reuna. Kuinka monta kärkiparia sinulla on $ n $? $ \ binom {n} {2} $