Топ-100
Indietro

ⓘ Calibro, teoria dei grafi. Nella teoria dei grafi, il calibro di un grafo è la lunghezza del ciclo più corto contenuto nel grafo. Se il grafo non contiene alcun ..




                                     

ⓘ Calibro (teoria dei grafi)

Nella teoria dei grafi, il calibro di un grafo è la lunghezza del ciclo più corto contenuto nel grafo. Se il grafo non contiene alcun ciclo, il suo calibro si definisce infinito. Ad esempio, un ciclo di ordine 4 ha calibro 4. Anche una griglia ha calibro 4, e un maglia triangolare ha calibro 3. Un grafo con calibro pari a 4 o superiore è senza triangoli.

                                     

1. Gabbie

Un grafo cubico tutti i vertici hanno grado 3 di calibro g {\displaystyle g} – cioè più piccolo possibile – è noto come una gabbia g {\displaystyle g} o come una gabbia 3, g {\displaystyle g}. Il grafo di Petersen è lunica gabbia 5 è il più piccolo grafo cubico di calibro 5, il grafo di Heawood è lunica gabbia 6, il grafo di McGee è lunica gabbia 7 e il grafo di Tutte-Coxeter è lunica gabbia 8. Possono esistere gabbie multiple per un dato calibro. Per esempio ci sono tre gabbie 10 non isomorfiche, ognuna con 70 vertici: la gabbia 10 di Balaban, il grafo di Harries e il grafo di Harries-Wong.

                                     

2. Calibro e colorazione dei grafi

Per un qualsiasi intero positivo g {\displaystyle g} e χ {\displaystyle \chi }, esiste un grafo con un calibro almeno di g {\displaystyle g} e un numero cromatico almeno di χ {\displaystyle \chi } ; ad esempio, il grafo di Grötzsch è senza triangoli e ha numero cromatico 4, e ripetendo la costruzione di Jan Mycielski usata per formare il grado di Grötzsch produce grafi senza triangoli con numero cromatico arbitrariamente grande. Paul Erdős fu il primo a provare il risultato generale, usando il metodo probabilistico. Più precisamente, dimostrò che un grafo aleatorio su n {\displaystyle n} vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità n 1 − g / g {\displaystyle n^{1-g/g}}, ha, con probabilità che tende a 1 quando n {\displaystyle n} va a infinito, al massimo n / 2 {\displaystyle n/2} cicli di lunghezza g {\displaystyle g} o minore, ma non ha alcun insieme indipendente di dimensione n / 2 k {\displaystyle n/2k}. Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di g {\displaystyle g}, in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno k {\displaystyle k} colori in una qualsiasi colorazione.

                                     

3. Concetti correlati

Il calibro dispari e il calibro pari di un grafo sono le lunghezze rispettivamente del più breve ciclo dispari e del più breve ciclo pari.

Pensato come la minore lunghezza di un ciclo non banale, il calibro ammette generalizzazioni naturali come sistole 1 o sistoli superiori in geometria sistolica.

                                     
  • Nel campo matematico della teoria dei grafi uno snark è un grafo cubico connesso, privo di ponti, con indice cromatico uguale a 4. In altre parole, è
  • Nella teoria dei grafi la colorazione dei grafi è un caso speciale di etichettamento dei grafi è un assegnazione di etichette, tradizionalmente chiamate
  • Nel campo matematico della teoria dei grafi il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come