Grafico completo | |
| |
Valutazione | |
---|---|
Numero di vertici | |
Numero di bordi | |
Distribuzione dei diplomi | (n-1) - regolare |
Diametro | 1 |
Maglia | ∞ se n = 1 o 2 3 se n > 2 |
Numero cromatico | |
Proprietà | Hamiltoniana , simmetrica , regolare |
Nella teoria dei grafi , un grafo completo è un grafo semplice di cui tutti i vertici sono adiacenti a due a due, vale a dire che qualsiasi coppia di vertici disgiunti è collegata da un bordo. Se il grafo è orientato , diciamo che è completo se ogni coppia di vertici è collegata esattamente da due archi (uno in ogni direzione).
Un grafo completo è un grafo i cui vertici sono tutti adiacenti.
Fino all'isomorfismo , c'è un solo grafo non orientato completo di ordine n , che indichiamo .
In un grafo G , chiamato clicca un sottoinsieme di vertici che inducono un sottografo completo di G . Trovare una cricca della dimensione massima in un grafico è un problema classico nella teoria dei grafi . È NP-completo .
Esiste anche la nozione di un grafo bipartito completo . Ma un grafo bipartito completo non è un grafo completo.
Il numero di bordi di è:
.Il primo termine si ottiene notando che la cancellazione di un primo vertice di comporta la cancellazione di spigoli, la cancellazione di un secondo vertice, la cancellazione di spigoli, e quella di un i-esimo vertice spigoli. Il secondo termine si ottiene con la stessa operazione segnando i bordi invece di rimuoverli, ogni bordo viene poi segnato due volte e si fanno segni per vertice (questa è la formula generale per la mezza somma dei gradi).
Possiamo anche ottenere questa formula vedendo il numero di archi come il numero di coppie distinte che possiamo formare con i nodi, vale a dire archi, il che vale la pena .
Il grafo completo è simmetrico : è transitivo di vertice, transitivo di bordo e transitivo di arco. Ciò significa che il suo gruppo di automorfismi agisce transitivamente su tutti i suoi vertici, bordi e archi. Questo gruppo di automorfismi è del cardinale n! ed è isomorfo al gruppo simmetrico .
Il polinomio caratteristico del grafo completo è: . Questo polinomio caratteristico ammette solo radici intere. Il grafico completo è quindi un grafico integrale , un grafico il cui spettro è composto da numeri interi.
Il grafico è il più piccolo grafico non planare. È utilizzato nelle caratterizzazioni dei grafici planari di Kazimierz Kuratowski e Klaus Wagner .
Indichiamo il numero di incroci del grafico , il numero minimo di incroci tra i possibili grafici di . A. Hill e J. Ernest hanno ipotizzato un valore per il numero di croci del grafico completo , che Richard K. Guy ha pubblicato nel 1960. Sappiamo che c'è sempre un grafico con
croci (suite A000241 del OEIS ). Si ipotizza che la disuguaglianza sia in realtà l'uguaglianza. Una formulazione indipendente della stessa congettura è stata fatta da Thomas L. Saaty nel 1964.
Saaty ha inoltre verificato che questa formula fornisce il numero ottimale di incroci per n ≤ 10 e Pan e Richter hanno dimostrato che è ottimale anche per n = 11, 12 .
Per ciascuno dei grafici completi da 1 a 12 vertici, viene indicato il numero dei suoi bordi.
: 1 bordo
: 3 bordi del
grafico a triangolo
: 6 bordi del
grafico tetraedrico
: 10 bordi
pentacolo
: 15 bordi
: 21 bordi
: 28 bordi
: 36 bordi
: 45 bordi
: 55 bordi
: 66 bordi