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 $(\binom{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$

$K_{5} : 10$	$K_{6} : 15$	$K_{7} : 21$	$K_{8} : 28$

$K_{9} : 36$	$K_{10} : 45$	$K_{11} : 55$	$K_{12} : 66$

Altri progetti

Wikimedia Commons contiene immagini o altri file su grafo completo

Collegamenti esterni

(EN) complete graph, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

(EN) Eric W. Weisstein, Complete Graph, su MathWorld, Wolfram Research.

(EN) Grafo completo, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
Mehdi Hassani, Cycles in graphs and derangements (PDF), in Math. Gaz., vol. 88, n. 511, 2004, pp. 123–126.

Controllo di autorità	LCCN (EN) sh85029361 · GND (DE) 4188588-0 · J9U (EN, HE) 987007545781605171

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