A definícióm szerint
A A klikk egy olyan gráf, amelynek éle összeköti az összes csúcspárt
de ahogy megértem, egy él csak két csúcsot köt össze. Mint a $ A-B $ .
Ha három csúcsot akarunk összekapcsolni, akkor legalább két élre van szükségünk. Például: $ ABC $ .
Nem értem, hogy egy él hogyan tudja összekapcsolni minden csúcspárot.
Megjegyzések
- Ez ' nem egy $ e $ éle, amely összeköti az összes párot. Minden egyes $ u, v \ pár esetében a V $ -ban van egy $ e_ {uv} $ él, amely összeköti a két csomópontot. Vagyis egy klikk egy (al-) gráf, amely tartalmazza az összes lehetséges élt.
Válasz
Emlékeztetve arra, hogy a klikk egy irányítatlan gráf csúcsainak $ C $ részhalmaza, amely a $ C $ által kiváltott algráf teljesen összekapcsolva van. Vagyis a $ C $ minden két különböző csúcsa a gráf külön széle köti össze. Ez különböző éleket jelent, nem ugyanazokat.
Tehát egy $ C $ klikken, amely $ k $ csúcsok $ v_1, v_2, .., v_k $ , vannak $ \ frac {k (k-1) } 2 $ él összeköti őket, vagyis a $ k $ elemeken a lehetséges rendezetlen párok száma.
Példa
Amint az előzőben láthatja kép, ez egy klikk négy csúcson $ \ {{1,2,3,4} \} $ , tehát minden élt egy másik él köt össze (azaz $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Megszámolhatja őket, és láthatja, hogy pontosan vannak $ 6 = \ frac {4 \ szor 3} {2} $ él.
Megjegyzések
- Honnan tudhatja, hogy van k (k-1) / 2 él?
- Minden 2 csúcshoz tartozik egy él. Hány csúcspárod van $ n $ -tól? $ \ binom {n} {2} $