Definiția mea spune
A clica este un grafic care are o margine care leagă fiecare pereche de vârfuri
dar, după cum am înțeles, o margine conectează doar două vârfuri. Ca $ A-B $ .
Dacă vrem să conectăm trei vârfuri, avem nevoie de cel puțin două margini. De exemplu, $ ABC $ .
Nu înțeleg cum o margine poate conecta fiecare pereche de vârfuri.
Comentarii
- Nu ' nu este o margine $ e $ care conectează toate perechile. Pentru fiecare pereche $ u, v \ în V $ există o margine $ e_ {uv} $ care conectează cele două noduri. Adică o clică este un (sub) grafic care conține toate marginile posibile.
Răspuns
Amintind că o clică este un subset $ C $ de vârfuri ale unui grafic nedirectat astfel încât subgraful indus de $ C $ este complet conectat. Adică, la fiecare două vârfuri distincte din $ C $ sunt conectate printr-o margine distinctă a graficului. Aceasta înseamnă margini diferite, nu la fel.
Deci, pe o clică $ C $ care conține $ k $ vârfuri $ v_1, v_2, .., v_k $ , există $ \ frac {k (k-1) } 2 $ margini care le conectează, adică numărul de perechi neordonate posibile pe $ k $ elemente.
Exemplu
După cum puteți vedea în versiunea anterioară imagine, aceasta este o clică pe patru vârfuri $ \ {{1,2,3,4} \} $ , deci există o margine diferită care leagă fiecare margine (adică $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Puteți să le numărați și să vedeți că există exact $ 6 = \ frac {4 \ times 3} {2} $ margini.
Comentarii
- De unde știi că există k (k-1) / 2 margini?
- Pentru fiecare 2 vârfuri există o margine. Câte perechi de vârfuri aveți de la $ n $? $ \ binom {n} {2} $