Grafo completo

Da Wikipedia, l'enciclopedia libera.

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\,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[modifica | modifica sorgente]

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
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K_9: 36 K_{10}: 45 K_{11}: 55 K_{12}: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

Collegamenti esterni[modifica | modifica sorgente]

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