it.wikipedia.org

Grafo completo - Wikipedia

Da Wikipedia, l'enciclopedia libera.

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}.

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

{\displaystyle K_{1}:0} {\displaystyle K_{2}:1} {\displaystyle K_{3}:3} {\displaystyle K_{4}:6}
{\displaystyle K_{5}:10} {\displaystyle K_{6}:15} {\displaystyle K_{7}:21} {\displaystyle K_{8}:28}
{\displaystyle K_{9}:36} {\displaystyle K_{10}:45} {\displaystyle K_{11}:55} {\displaystyle K_{12}:66}
Controllo di autoritàLCCN (EN) sh85029361 · GND (DE) 4188588-0 · J9U (EN, HE) 987007545781605171