Quando as linhas centrais das ruas de uma cidade podem ser pintadas sem percorrer uma rua mais de uma vez? (Suponha que todas as ruas sejam de mão dupla.)

Passo 1

O enunciado pede para pintar a linha central de cada rua de uma cidade sem percorrer nenhuma rua mais de uma vez. Isso equivale a encontrar, num grafo onde vértices são cruzamentos e arestas são ruas de mão dupla, um percurso que use cada aresta exatamente uma vez. O conteúdo envolvido é Teoria dos Grafos, mais precisamente trilhas e circuitos eulerianos.

Passo 2

Para modelar o problema, associamos cada cruzamento a um vértice e cada rua de mão dupla a uma aresta não-direcionada. Assim, pintar todas as ruas sem repeti-las significa passar por cada aresta exatamente uma vez, isto é, encontrar uma trilha que percorra todas as arestas do grafo.

Passo 3

Um grafo é conexo se, para quaisquer dois vértices, existe um caminho que os une. Se o grafo não for conexo, não há como pintar todas as ruas numa única caminhada, pois faltarão componentes isolados.

Passo 4

O Teorema de Euler afirma que, num grafo conexo, existe trilha que percorre cada aresta exatamente uma vez (trilha euleriana) se e somente se o número de vértices de grau ímpar for igual a 0 ou a 2.
\begin{cases} \text{0 vértices de grau ímpar} &\Rightarrow \text{existe circuito euleriano (volta ao ponto inicial)},\\\ \text{2 vértices de grau ímpar} &\Rightarrow \text{existe trilha euleriana aberta (inicia num ímpar e termina no outro)}. \end{cases}éíéíí

Passo 5

Portanto, para pintar as ruas sem repetir nenhuma delas é necessário e suficiente que o grafo das ruas seja conexo e tenha exatamente 0 ou 2 vértices de grau ímpar. No caso de 0 vértices ímpares, podemos começar e terminar no mesmo cruzamento; no caso de 2, começamos num cruzamento de grau ímpar e terminamos no outro.

Resposta

As linhas centrais podem ser pintadas sem repetir ruas se, e somente se, o grafo associado às ruas for conexo e tiver exatamente 0 ou 2 vértices de grau ímpar.

Exercícios de Livros Relacionados