|
Snark (teoria dei grafi) 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, è un grafo in cui ogni vertice ha tre vicini, e gli spigoli non possono essere colorati solo con tre colori senza che due spigoli dello stesso colore si incontrino in un punto. (Per il teorema di Vizing, l'indice cromatico di un grafo cubico è 3 o 4.) Per evitare casi banali, gli snark sono spesso limitati ai grafi aventi un calibro almeno di 5. Scrivendo su The Electronic Journal of Combinatorics, Miroslav Chladný afferma che «Nello studio di vari importanti e difficili problemi della teoria dei grafi (come la congettura sulla copertura del doppio ciclo e la congettura sul 5-flusso), si incontra una varietà di grafi interessante ma in un certo modo misteriosa chiamati snark. Malgrado la loro semplice definizione... e un'indagine lunga oltre un secolo, le loro proprietà e la loro struttura sono in gran parte ignote.[1]» StoriaP. G. Tait iniziò lo studio degli snark nel 1880, quando dimostrò che il teorema dei quattro colori è equivalente all'enunciato che nessuno snark è planare.[2] Il primo snark conosciuto fu il grafo di Petersen, scoperto nel 1898. Nel 1946, il matematico croato Danilo Blanuša scoprì altri due snark, entrambi su 18 vertici, ora chiamati snark di Blanuša.[3] Il quarto snark conosciuto fu trovato due anni dopo da Bill Tutte, sotto lo pseudonimo Blanche Descartes, ed era un grafo di ordine 210.[4][5] Nel 1973, George Szekeres trovò il quinto snark conosciuto — lo snark di Szekeres.[6] Nel 1975, Rufus Isaacs generalizzò il metodo di Blanuša per costruire due famiglie infinite di snark: lo snark a fiore e gli snark di Blanuša-Descartes-Szekeres (Blanuša-Descartes-Szekeres snark, BDS), una famiglia che comprende i due snark di Blanuša, lo snark di Descartes e lo snark di Szekeres.[7] Isaacs scoprì anche uno snark con 30 vertici che non appartiene alla famiglia BDS e che non è uno snark a fiore: lo snark a doppia stella. Gli snark furono chiamati così dal matematico americano Martin Gardner nel 1976, dal nome del misterioso ed elusivo oggetto del poema La caccia allo Snark (1874) di Lewis Carroll.[8] ProprietàTutti gli snark sono non hamiltoniani, e molti snark conosciuti sono ipohamiltoniani: l'eliminazione di un singolo vertice qualsiasi lascia un sottografo hamiltoniano. Uno snark ipohamiltoniano deve essere bicritico: l'eliminazione di due vertici qualsiasi lascia un sottografo 3-colorabile sui vertici.[9][10] È stato mostrato che il numero di snark per un dato numero pari di vertici è limitato in basso mediante una funzione esponenziale.[11] (Essendo grafi cubici, tutti gli snark devono un numero pari di vertici.) La sequenza OEIS A130315 contiene il numero di snark non banali di 2n vertici per piccoli valori di n. La congettura sulla copertura del doppio ciclo postula che in ogni grafo privo di ponti si può trovare una collezione di cicli che copre ogni vertice due volte, o in modo equivalente che il grafo può essere incorporato su una superficie in modo tale che tutte le facce dell'incorporazione siano cicli semplici. Gli snark rappresentano il caso difficile per questa congettura: se è vero per gli snark, è vero per tutti i grafi.[12] In questa connessione, Branko Grünbaum congetturò che non era possibile incorporare alcuno snark su una superficie in modo tale che tutte le facce siano cicli semplici e che ogni due facce o sono disgiunte o condividono solo un unico spigolo; tuttavia, un controesempio per la congettura di Grünbaum fu trovato da Martin Kochol.[13][14][15] Teorema degli snarkW. T. Tutte congetturò che ogni snark ha il grafo di Petersen come minore. Cioè, congetturò che il più piccolo snark, il grafo di Petersen, può essere formato da un qualsiasi altro snark contraendo alcuni spigoli e cancellandone altri. Equivalentemente (poiché il grafo di Petersen ha grado massimo tre) ogni snark ha un sottografo che può essere formato dal grafo di Petersen mediante suddividendo alcuni dei suoi spigoli. Questa congettura è una forma rafforzata del teorema dei quattro colori, perché qualsiasi grafo contenente il grafo di Petersen come minore deve essere non planare. Nel 1999, Robertson, Sanders, Seymour e Thomas annunciarono una dimostrazione di questa congettura.[16] Fino al 2012 questa dimostrazione restava in gran parte non pubblicata.[17] Vedi la congettura di Hadwiger per altri problemi e risultati che collegano la colorazione dei grafi ai minori dei grafi. Tutte congetturò anche una generalizzazione del teorema degli snark ai grafi arbitrari: ogni grafo privo di ponti senza minori di Petersen ha un 4-flusso zero in nessun luogo. Ossia, agli spigoli del grafo possono essere assegnati una direzione e un numero dall'insieme {1, 2, 3}, tale che la somma dei numeri entranti meno la somma dei numeri uscenti in ogni vertice è divisibile per quattro. Come mostrò Tutte, per i grafi cubici tale assegnazione esiste se e solo se gli spigoli possono essere colorati da tre colori, così in questo caso la congettura deriva dal teorema degli snark. Tuttavia, quest congettura rimane aperta per i grafi che non devono essere cubici.[18] Lista di snark
Una lista di tutti gli snark fino a 36 vertici, eccetto quelli con 36 vertici e calibro 4, fu creata da Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund e Klas Markström nel 2012.[19] Note
Altri progetti
Collegamenti esterni
|
Portal di Ensiklopedia Dunia
