grafo completo

Also known as complete digraph, complete graphs, complete digraphs, 2K1-free graph

tipo di grafo

Key facts

Vertices: n
Edges: n ( n − 1 ) 2 {\displaystyle \textstyle {\frac {n(n-1)}{2}}}
Radius: { 0 n ≤ 1 1 otherwise {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}
Diameter: { 0 n ≤ 1 1 otherwise {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}
Girth: { ∞ n ≤ 2 3 otherwise {\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}
Automorphisms: n ! ( S n )
Chromatic number: n
Chromatic index: n if n is odd n − 1 if n is even
Spectrum: { ∅ n = 0 { 0 1 } n = 1 { ( n − 1 ) 1 , − 1 n − 1 } otherwise {\displaystyle \left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{otherwise}}\end{array}}\right.}
Properties: ( n − 1) -regular Symmetric graph Vertex-transitive Edge-transitive Strongly regular Integral
Notation: K n

via Wikipedia infobox

Article · Italiano

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 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 , in quanto l'unico 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 né né il grafo bipartito completo . Seguono raffigurazioni che presentano con dei grafi completi su vertici per .

Abstract from DBpedia / Wikipedia · CC BY-SA