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 ${\displaystyle n}$ vertici sono tutti isomorfi. Il grafo completo astratto di ${\displaystyle n}$ vertici si denota con ${\displaystyle \,K_{n}}$. In questo grafo (in ciascuno dei grafi della classe di isomorfismo ${\displaystyle \,K_{n}}$) vi sono ${\displaystyle \,n(n-1)/2}$ spigoli: in effetti gli spigoli sono in corrispondenza biunivoca con i sottoinsiemi di due elementi dell'insieme degli ${\displaystyle \,n}$ vertici e quindi il loro numero è dato dal coefficiente binomiale ${\displaystyle {n \choose 2}}$.

Il grafo completo ${\displaystyle \,K_{n}}$ è un grafo regolare di grado ${\displaystyle \,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 ${\displaystyle \,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é ${\displaystyle \,K_{5}}$ né il grafo bipartito completo ${\displaystyle \,K_{3,3}}$.

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

Esempi

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

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.
• Mehdi Hassani, Cycles in graphs and derangements (PDF), in Math. Gaz., vol. 88, n. 511, 2004, pp. 123–126.