Grafo completo
tipo di grafo / Da Wikipedia, l'enciclopedia encyclopedia
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 vertici sono tutti isomorfi. Il grafo completo astratto di
vertici si denota con
. In questo grafo (in ciascuno dei grafi della classe di isomorfismo
) vi sono
spigoli: in effetti gli spigoli sono in corrispondenza biunivoca con i sottoinsiemi di due elementi dell'insieme degli
vertici e quindi il loro numero è dato dal coefficiente binomiale
.
Il grafo completo è un grafo regolare di grado
. 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 è 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é né il grafo bipartito completo
.
Seguono raffigurazioni che presentano con simmetria rotazionale dei grafi completi su vertici per
.