Snark (teoria de grafos)

Artícul principal → Teoria de grafos.

El grafo de Petersen és el snark més menut.

En el camp matemàtic de la teoria de grafos, un snark és un grafo no dirigit en exactament tres arestes per vèrtiç les arestes del qual no poden colorearse en només tres colors. Per a evitar casos trivials, els snarks solen tindre requisits adicionals sobre la seua conectivitat i a la llongitut dels seus cicles. Existixen infinits snarks.

Una de les formes equivalents del teorema dels quatre colors és que cada snark és un grafo no pla. L'investigació sobre els snarks té el seu orige en els treballs de Peter G. Tait sobre la teorema dels quatre colors en 1880, pero el seu nom és molt més recent, ya que li'l va donar Martin Gardner en 1976. Més allà de la coloració, els snarks també estan relacionats en atres problemes difícils de la teoria de grafos: en el Electronic Journal of Combinatorics, Miroslav Chladný i Martin Škoviera afirmen que:

En l'estudi de varis problemes importants i difícils de la teoria de grafos (com la conjectura del cicle doble tapa i la conjectura dels 5 fluix en fluix zero en ninguna parte (nowhere-zero flow), un es troba en una interessant pero alguna cosa misteriosa varietat de grafos cridats snarks. A pesar de la seua senzilla definició... i de més d'un sigle d'investigació, les seues propietats i estructura són en gran part desconegudes.

Archiu:Flower snarkv.svg

El snark flor J₅ és una de les sis snarks en 20 vèrtiços.

Ademés dels problemes que mencionen, la conjectura snark de W. T. Tutte es referix a l'existència de grafos de Petersen com grafos menors de snarks; la seua demostració s'ha anunciat fa temps pero seguix sense publicar-se, i resoldria un cas especial de l'existència de 4-fluix en fluix zero en ninguna parte.

Història i eixemples

Els snarks varen ser batejats aixina pel matemàtic nortamericà Martin Gardner en 1976, en honor al misteriós i esmonyidiç objecte del poema La caça del Snark de Lewis Carroll. No obstant, l'estudi d'esta classe de grafos és prou més antic que el seu nom. Peter G. Tait va iniciar l'estudi dels snarks en 1880, quan va demostrar que el teorema dels quatre colors és equivalent a l'afirmació de que cap snark és pla. El primer gràfic conegut com snark va ser el gràfic de Petersen; Julius Petersen va demostrar que era un snark en 1898, encara que Alfred Kempe ya ho havia estudiat en un propòsit diferent en 1886.

Els següents quatre snarks coneguts varen ser:

• els snarks de Blanuša (dos en 18 vèrtiços), descoberts per Danilo Blanuša en 1946,

• el snark Descartes (210 vèrtiços), descobert per Bill Tutte en 1948, i
• el snark Szekeres (50 vèrtiços), descobert per George Szekeres en 1973.

En 1975, Rufus Isaacs va generalisar el método de Blanuša per a construir dos famílies infinites de snarks: els snarks flor i els snarks Blanuša-Descartes-Szekeres, una família que inclou els dos snarks de Blanuša, el snark Descartes i el snark Szekeres. Isaacs també va descobrir un snark de 30 vèrtiços que no pertany a la família Blanuša-Descartes-Szekeres i que no és un snark de flor: el snark de doble estrela. En 1989 es va descobrir el snark de 50 vèrtiços de Watkins.

Un atre notable grafo cúbic no coloreable en tres arestes és el grafo de Tietze, en 12 vèrtiços; com va descobrir Heinrich Franz Friedrich Tietze en 1910, forma el llímit d'una subdivisió de la banda de Möbius que requerix sis colors. No obstant, degut a que conté un triàngul, generalment no es considera un snark. Segons les definicions estrictes de snarks, els snarks més menuts són el grafo de Petersen i els snarks de Blanuša, seguits de sis snarks diferents de 20 vèrtiços.

Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund i Klas Markström varen generar en 2012 una llista de tots els snarks de fins a 36 vèrtiços (segons una definició estricta) i de fins a 34 vèrtiços (segons una definició més dèbil). El número de snarks per a un número par de vèrtiços donat creix a lo manco exponencialment en el número de vèrtiços. Ya que tenen vèrtiços de grau impar, tots els snarks deuen tindre un número par de vèrtiços pel lema de la premuda de mans). La seqüència A130315 de l'OEIS conté el número de snarks no trivials de $2n$ vèrtiços per a valors menuts de $n$.

Definició

La definició precisa de snarks varia segons els autors, pero generalment es referix a grafos cúbics (que tenen exactament tres arestes en cada vèrtiç) les arestes del qual no poden colorearse en només tres colors. Segons el teorema de Vizing, el número de colors necessaris per a les arestes d'un grafo cúbic és tres (grafos de «classe un») o quatre (grafos de «classe dos»), per lo que els snarks són grafos cúbics de classe dos. No obstant, per a evitar casos en els que un snark és de classe dos per raons trivials, o es construïx de forma trivial a partir de grafos més menuts, a sovint s'imponen restriccions adicionals sobre la conectivitat i la llongitut dels cicles. En particular:

• Si un grafo cúbic té un pont, una aresta l'eliminació de la qual ho desconectaria, llavors no pot ser de classe un. Pel lema de la premuda de mans, els subgrafos a abdós costats del pont tenen un número impar de vèrtiços cada u. Qualsevol que siga el color elegit per al pont, el seu número impar de vèrtiços impedix que estos subgrafos estiguen coberts per cicles que alternen entre els atres dos colors, com seria necessari en una coloració de 3 arestes. Per esta raó, generalment es requerix que els snarks no tinguen ponts.
• Un bucle (una aresta que conecta un vèrtiç en si mateixa) no pot colorearse sense que el mateix color aparega dos voltes en eixe vèrtiç, lo que supon una violació dels requisits habituals per a la coloració d'arestes de grafos. Ademés, un cicle format per dos vèrtiços conectats per dos arestes sempre pot substituir-se per una única aresta que conecte a les seues uns atres dos veïns, lo que simplifica el grafo sense canviar el seu coloreabilidad de tres arestes. Per estes raons, els snarks es llimiten generalment a grafos simples, sense bucles ni adyacencias múltiples.
• Si un grafo conté un triàngul, pot simplificar-se de nou sense canviar el seu coloreabilidad en tres arestes, contraent els tres vèrtiços del triàngul en un únic vèrtiç. Per lo tant, moltes definicions de snarks prohibixen els triànguls. No obstant, encara que este requisit també es va establir en el treball de Gardner que va donar el nom de «snark» a estos grafos, Gardner inclou el grafo de Tietze, que conté un triàngul, com un snark.
• Si un grafo conté un cicle de quatre vèrtiços, pot simplificar-se de dos maneres diferents eliminant dos arestes opostes del cicle i substituint els camins resultants de vèrtiços de grau dos per arestes simples. Té una coloració de tres arestes si i només si a lo manco una d'estes simplificació la té. Per lo tant, Isaacs requerix que un grafo cúbic «no trivial» de classe dos evite cicles de quatre vèrtiços, i atres autors han seguit el seu eixemple prohibint estos cicles. El requisit de que un snark evite cicles de llongitut quatre o menys pot resumir-se afirmant que la circumferència d'estos grafos, la llongitut dels seus cicles més curts, és a lo manco cinc.
• En concret, la definició utilisada per Brinkmann et al. (2012) exigix que els snarks estiguen conectats cíclicamente per 4 arestes. Açò significa que no pot haver cap subconjunt de tres o menys arestes l'eliminació de les quals desconectaria el grafo en dos subgrafos, cada u dels quals té a lo manco un cicle. Brinkmann et al. definixen un snark com un grafo cúbic i cíclicamente conectat per 4 arestes de circumferència cinc o més i classe dos; definixen un «snark dèbil» per a permetre circumferència quatre.

Encara que estes definicions només consideren restriccions en la circumferència fins a cinc, existixen snarks en circumferències arbitrariamente grans.