Grafo completo

Nella teoria dei grafi un grafo completo è un grafo semplice nel quale ogni vertice è collegato direttamente 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 $(\genfrac{}{}{0ex}{}{n}{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$
		Errore nella creazione della miniatura:	File:3-simplex graph.svg
$K_5:10$	$K_6:15$	$K_7:21$	$K_8:28$
File:4-simplex graph.svg	File:5-simplex graph.svg
$K_9:36$	$K_{10}:45$	$K_{11}:55$	$K_{12}:66$
File:8-simplex graph.svg	File:9-simplex graph.svg

Collegamenti esterni

• Template:Collegamenti esterni
• Template:Cita pubblicazione