La mia definizione dice
R clique è un grafo che ha un bordo che collega ogni coppia di vertici
ma da quanto ho capito, un bordo collega solo due vertici. Come $ A-B $ .
Se vogliamo connettere tre vertici, abbiamo bisogno di almeno due bordi. Ad esempio, $ ABC $ .
Non capisco come un bordo possa connettere ogni coppia di vertici.
Commenti
- ' non è un lato $ e $ che collega tutte le coppie. Per ciascuna coppia $ u, v \ in V $ cè un bordo $ e_ {uv} $ che collega i due nodi. Cioè, una cricca è un (sotto) grafo che contiene tutti i possibili archi.
Risposta
Ricordando che una cricca è un sottoinsieme $ C $ di vertici di un grafo non orientato tale che il sottografo indotto da $ C $ è completamente connesso. Cioè, ogni due vertici distinti in $ C $ sono collegati da un bordo distinto del grafico. Ciò significa bordi diversi, non uguali.
Quindi, su una cricca $ C $ contenente $ k $ vertices $ v_1, v_2, .., v_k $ , ci sono $ \ frac {k (k-1) } 2 $ bordi che li collegano, ovvero il numero di possibili coppie non ordinate sugli elementi $ k $ .
Esempio
Come puoi vedere nella precedente immagine, questa è una cricca su quattro vertici $ \ {{1,2,3,4} \} $ , quindi cè un bordo diverso che collega ogni bordo (cioè $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Puoi contarli e vedere che ci sono esattamente $ 6 = \ frac {4 \ times 3} {2} $ bordi.
Commenti
- Come fai a sapere che ci sono k (k-1) / 2 archi?
- Per ogni 2 vertici cè un bordo. Quante coppie di vertici hai da $ n $? $ \ binom {n} {2} $