Calibro (teoria dei grafi)

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo.[1] Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito.[2] Ad esempio, un ciclo di ordine 4 (quadrato) 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.

Gabbie[modifica | modifica wikitesto]

Un grafo cubico (tutti i vertici hanno grado 3) di calibro g – cioè più piccolo possibile – è noto come una gabbia g o come una gabbia (3,g). Il grafo di Petersen è l'unica gabbia 5 (è il più piccolo grafo cubico di calibro 5), il grafo di Heawood è l'unica gabbia 6, il grafo di McGee è l'unica gabbia 7 e il grafo di Tutte-Coxeter è l'unica gabbia 8.[3] 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.

Calibro e colorazione dei grafi[modifica | modifica wikitesto]

Per un qualsiasi intero positivo g e \chi, esiste un grafo con un calibro almeno di g e un numero cromatico almeno di \chi; ad esempio, il grafo di Grötzsch è senza triangoli e ha numero cromatico 4, e ripetendo la costruzione di Mycielskian 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.[4] Più precisamente, dimostrò che un grafo aleatorio su n vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità n^{(1-g)/g}, ha, con probabilità che tende a 1 quando n va a infinito, al massimo n/2 cicli di lunghezza g o minore, ma non ha alcun insieme indipendente di dimensione n/2k. Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di g, in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno k colori in una qualsiasi colorazione.

Concetti correlati[modifica | modifica wikitesto]

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

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

Note[modifica | modifica wikitesto]

  1. ^ R. Diestel, Graph Theory, p. 8. 3ª edizione, Springer-Verlag, 2005
  2. ^ Girth -- Wolfram MathWorld.
  3. ^ Andries E. Brouwer, Cages. Supplemento elettronico al libro Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
  4. ^ Paul Erdős, Graph theory and probability in Canadian Journal of Mathematics, vol. 11, 1959, pp. 34-38, DOI:10.4153/CJM-1959-003-9..

Collegamenti esterni[modifica | modifica wikitesto]