Grafo completo

Nella teoria dei grafi un grafo completo è un grafo semplice nel quale ogni vertice è collegato a tutti i vertici rimanenti. I grafi completi con $n$ vertici sono tutti isomorfi. Il grafo completo astratto di $n$ vertici si denota con $\,K_n\,$. In questo grafo (in ciascuno dei grafi della classe di isomorfismo $\,K_n\,$) vi sono $\,n(n-1)/2\,$ spigoli: in effetti gli spigoli sono in corrispondenza biunivoca con i sottoinsiemi di due elementi dell'insieme degli $\,n\,$ vertici e quindi il loro numero è dato dal coefficiente binomiale ${n \choose 2}$.

Il grafo completo $\,K_n\,$ è un grafo regolare di grado $\,n-1\,$. Ogni grafo completo è cricca di sé stesso. I grafi completi sono i grafi massimamente connessi, in quanto l'unico taglio di vertici che li sconnette è l'insieme di tutti i suoi vertici.

Il gruppo degli automorfismi di $\,K_n\,$ è il gruppo di tutte le permutazioni dei suoi vertici, cioè in astratto il gruppo simmetrico di n oggetti.

Il teorema di Kuratowski afferma che i grafi planari sono i grafi che non contengono come minore né $\,K_5\,$ né il grafo bipartito completo $\,K_{3,3}\,$.

Seguono raffigurazioni che presentano con simmetria rotazionale dei grafi completi su $\,n\,$ vertici per $\,n= 1, 2, ... , 8 \,$.

Esempi

Sotto vengono mostrati i grafi completi di n vertici, con 1 ≤ n ≤ 12, insieme al rispettivo numero di lati.

$K_1: 0$	$K_2: 1$	$K_3: 3$	$K_4: 6$
$K_5: 10$	$K_6: 15$	$K_7: 21$	$K_8: 28$
$K_9: 36$	$K_{10}: 45$	$K_{11}: 55$	$K_{12}: 66$

Collegamenti esterni

• (EN) Eric W. Weisstein, Grafo completo su MathWorld.
• Hassani, Mehdi (2004). Cycles in graphs and derangements. Math. Gaz. 88 (511): 123–126.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica