Eulerizar grelhas (redes viárias rectangulares)

 
Existe um procedimento sistemático para encontrar a melhor eulerização, mas não vamos estudar o processo. Trataremos de uma técnica especialmente fácil para eulerizar da melhor maneira redes viárias rectangulares. Vamos observar, por isso, uma rede rectangular em primeiro lugar, antes de tentarmos aproximar-nos de uma abordagem das redes não rectangulares.
Muitas redes viárias são constituídas por uma série de blocos rectangulares que formam um grande rectângulo de m por n blocos. São redes deste tipo que designamos por redes viárias rectangulares. Exemplos de redes viárias rectangulares estão representados na figura abaixo, em que cada grafo da direita (em cada par) representa uma possível melhor eulerização do grafo da rede viária rectangular à esquerda. Aparecem-nos como sendo três procedimentos-padrão de eulerização diferentes, dependentes do facto de da altura do rectângulo (m blocos) e da sua largura (n blocos) no grafo original serem números pares ou ímpares. Na figura (a), ambas as dimensões são ímpares - 3 -; na figura (b), um comprimento é ímpar -3- e o outro é par -4-; na figura (c) ambas as dimensões são pares -4.
 
Embora os procedimentos-padrão pareçam diferentes, uma só técnica está na base da criação de todos eles. Esta técnica pode ser descrita do seguinte modo:
Imagine-se como um peão a percorrer aos passeios exteriores do rectângulo grande em alguma direcção, por exemplo no sentido dos ponteiros do relógio. Parte de um canto, por exemplo, o canto superior esquerdo. À medida que vai andando à volta do rectângulo, vai acrescentando arestas de acordo com certas regras. Quando chega a um vertex de valência ímpar, liga-o ao próximo vertex por uma aresta acrescentada. Este vertex próximo fica de valência par ou ímpar. Se ficar par, salta-o e continua viagem, até encontrar um vertex ímpar. Se esse novo vértice tiver ficado ímpar, o peão liga-o ao vertex seguinte por uma aresta acrescentada e vai verificar se o seguinte fica par ou ímpar e assim sucessivamente. Cada uma das três partes da figura acima foi eulerizado por este método.
 
Numa rede viária que não seja rectangular, o processo de eulerização começa pela localização de todos os vértices com valência ímpar, para, de seguida os emparelhar e procurar o comprimento do caminho menor (com o menor número de arestas) entre cada par. Procuramos os caminhos mais curtos, dado que cada aresta desses caminhos de ligação vai ter de ser duplicada. A ideia é fazer emparelhamentos da forma mais inteligente possível, de tal modo que a soma dos comprimentos destes caminhos seja o menor possível. Com alguma prática, a maioria das pessoas espera encontrar a melhor eulerização (ou perto disso) usando esta ideia simples, tentativa e erro e muita ingenuidade. Os mais interessados continuarão uma discussão mais aprofundada para encontrar as melhores eulerizações.
 
Mostramos a seguir várias eulerizações possíveis para um mesmo grafo. Estude-as. E escolha a melhor.

 
Tarefas:
Primeira.
Na figura abaixo, todos os blocos são de 100 por 100, excepto a coluna do meio em que os blocos são de 100 por 400.
Poder-se-á conseguir uma eulerização em que o comprimento da totalidade das arestas repetidas seja exactamente 800?
 
Segunda.
Pode fazer-se uma eulerização com adição de 7 arestas numa rede rectangular de 2 por 5 blocos? Pode fazer melhor que 7?
Pode fazer-se uma eulerização com adição de 6 arestas numa rede rectangular de 3 por 5 blocos? Pode fazer melhor do que com 6?
Pode fazer-se uma eulerização com adição de 9 arestas numa rede rectangular de 3 por 6? Melhor que isso?
Pode fazer uma eulerização com adiçãod e 10 arestas numa rede rectangular de 4 por 6? E melhor que isso?


voltar ao sumário