Un eodermdrome galego

Foi o artigo do blogue Xogos de lingua, Non apto para sesquipedalofóbicos, o que prendeu a chispa para que elaborase esta entrada. Xogos de lingua, tal como indica o seu nome, é un blogue adicado á ludolingüística. Como tal, ten algunha entrada na que fai referencia ao gran divulgador das matemáticas, Martin Gardner, coñecido por utilizar os xogos como punto de partida de moitos dos seus artigos. Velaquí o punto de encontro entre a lingua e as matemáticas: o xogo. No libro Rosquillas anudadas (Labor, 1987), Martin Gardner fai referencia a un famoso reto de Henry Dudeney, aparecido no libro Amusements in Mathematics: auga, gas e electricidade consistente en unir co lapis as casas A, B e C cos subministros de auga (W), gas (G) e electricidade (E) de forma que as liñas de subministro non se corten. Tal e como o propio Dudeney adianta, é imposible realizar o que se pide no reto:

Figura 1:Amusements in Mathematics

Este problema entra dentro do campo da teoría de grafos. Os matemáticos chámanlle grafo a unha colección de vértices con arestas entre os mesmos. Cada aresta conecta dous vértices. Velaquí un par de exemplos.

Figura 2. Dous grafos simples

Nota: aquí debuxei as arestas mediante segmentos rectos, pero non hai porque facelo así. O importante dunha aresta consiste nos vértices que conecta.

Figura 3:Grafo K₅

Cómpre avisar que os únicos vértices do grafo son os marcados en cor. Neste grafo denominado K₅  hai 5 vértices e 10 arestas.  O grafo completo de grao n, denotado K_n é o un grafo de n vértices na que todo vértice está conectado con todos os demais vértices. Aquí presentamos o grafo completo de 5 vértices. Algunhas das arestas deste grafo crúzanse, o mesmo lle sucede ao grafo que representa o problema de Dudeney (cada unha das arestas superiores representa unha compañía subministradora e as inferiores representan as casas)

Figura 4: grafo K_3,3

Na Figura 1 podemos ver como este grafo podería representarse con só un cruce, pero sería imposible facelo sen cruce ningún, niso consiste a imposibilidade da resolución do problema das tres casas. Os grafos que poden representarse sen cruces, como os da figura 2, chámanse grafos planares. Hai que ter en conta que nun grafo só nos interesa a forma en que están conectados os vértices, non esta ou aqueloutra representación particular. Para un grafo dado, sempre poderemos buscar a representación que teña o menor número posible de cruces. Na seguinte figura vemos como o grafo que está representado (á esquerda) con cruces, pode representarse (á dereita) sen cruces. Trátase, polo tanto, dun grafo planar.

Figura 5: Grafo planar

Hai unha forma de saber se un grafo é planar ou non grazas ao teorema de Kuratowski: se o grafo non contén ningún subgrafo K₅ nin K_3,3 será planar. Grafos de palabras Podemos combinar os grafos coas palabras conectando cada letra con aquelas ás que é adxacente. Se unha letra aparece repetida e consecutiva, non debuxamos aresta ningunha xa que consideramos a letra conectada consigo mesma. Por exemplo, as palabras touporroutou e nacionalismo terían os seguintes grafos asociados:

Figura 6

Figura 7

A pouco que un remexa nos grafos de palabras, decatarase de que prácticamente todos son planares. As palabras que dan lugar a grafos non planares chámanse eodermdromes. Por suposto, propia palabra eodermdrome é un eodermdrome (ver a figura 7). A. Ross Eckler elaborou no ano 1980 un dicionario de eodermdromes para a lingua inglesa. Martin Gardner cualificaba esta publicación como unha aplicación extravagante do estudo do número de cruces dun grafo fronte á indubidablemente interesante aplicación ao deseño de microcircuítos. Temos unha lista de eodermdromes en inglés pero, haberá algún en galego? As candidatas deben ter unha cantidade considerable de letras, canto máis longas, máis arestas terá o seu grafo e máis posibilidades haberá de que teña un cruce inevitable. Por iso, cando na  entrada de Xogos de lingua vin que se referenciaban as palabras máis longas do noso vocabulario, púxenme a comprobar se entre elas había algún eodermdrome.  O grafo correspondente á palabra máis longa, esternocleidomastoideo, é o seguinte:

Figura 8

Como podemos observar, esternocleidomastoideo é planar. Tamén o son preterintencionalidade, contrarrevolucionario, electroencefalografía ou incluso hipopotomonstrosesquipedaliofobia. Pero a outra palabra, extraterritorialidade contén un subrafo K_3,3,, o que establece todas as arestas entre os dous conxuntos de vértices {t,r,d} e {i,a,e}. Por fin, aquí temos un eodermdrome da nosa lingua:

Figura 9

Haberá outros? Existirá algún que conteña un subrafo K₅? As arestas destes grafos representan un par de letras adxacentes. Cales serán as arestas máis frecuentes en galego?, e noutras linguas? Poderán determinarse a lingua en que vén redactado un texto estudando o tipo de arestas máis frecuentes do mesmo? Todo un extravagante campo de traballo  para a lingüística informática.