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