Quase todos os professores de Matemática já se depararam algum dia com o seguinte problema:

É possível ligar água, luz e telefone a três casas, sem que as ligações se cortem (supondo que todas as ligações, fios e canos esteiam situados em um mesmo plano)?

Vamos chegar a uma resposta a esse problema por meio de uma aplicação da Fórmula de Euler.

A fórmula de Euler, V A + F = 2, que relaciona o número de vértices, V, arestas, A, e faces, F, de um poliedro, já foi considerada duas vezes nesta Revista (RPM 3, p.15 e RPM 5, p.23).

Como vários teorema nportantes de Matemática, este resultado de Euler admite várias interpretações, várias "leituras". Nosso objetivo aqui é interpretá-lo como um teorema da Teoria dos Grafos.

Definição: Um grafo consiste em um certo número de pontos do espaço, A, B, C, ..., F,  chamados vértices e em arcos, chamados arestas, de forma que:

1.°) as extremidades de cada aresta são vértices (um ou dois) do grafo;

2.°) duas arestas distintas ou são disjuntas ou possuem em comum somente extremidades, uma ou duas.

Exemplos: São grafos

A Teoria dos Grafos, que até há pouco tempo era considerada mais como um passatempo matemático, passou a ser muito estudada nas três ou quatro últimas décadas, em grande parte devido ao aparecimento dos computadores eletrônicos. Um computador armazena dados em "arquivos". Frequentemente, organizam-se esses arquivos de forma sistemática, segundo algum critério (por exemplo, se o arquivo for uma lista de nomes de pessoas com seus endereços, ele poderá ser ordenado — "indexado", na terminologia de informática — segundo o nome da pessoa, seu endereço, seu CEP, etc). Tais arquivos têm uma "estrutura de árvore", ou seja, uma estrutura que é um certo tipo de gra­fo. Um problema importante é, então, o de determinar qual o "caminho" mais curto para chegar a um dos dados armazenados no arquivo. Os grafos também são importantes em pesquisa operacional, onde uma certa sequência de operações pode ser representada por um grafo. Ainda em pesquisa operacional, um exemplo óbvio de grafo é o da rede de distribuição de energia elétrica de uma região (por exemplo, o Sudeste do Brasil) ou a rede de ruas de uma cidade.

Não podemos, além disso, esquecer que a Teoria dos Grafos, independentemente de suas aplicações importantes e variadas, é fonte de um grande nú­mero de problemas fascinantes, difíceis e de fácil enunciado.

O grafo é, portanto, uma coleção de objetos muito simples e mais, não estamos interessados em considerar propriedades mais complicadas destes objetos como, por exemplo, o comprimento de cada arco, etc. Assim é que, para efeito dessa teoria, vamos considerar a seguinte relação de equivalência entre grafos:

Definição: Dois grafos se dizem equivalentes se for possível estabelecer uma correspondência biunívoca entre vértices de um e vértices do outro e entre arestas de um e do outro, de forma que arestas correspondentes tenham vértices também correspondentes.

Exemplos

Observação sobre a definição dos grafos: O leitor interessado em consultar a bibliografia perceberá que grande parte dos textos de Teoria Combinatória ou de Teoria dos Grafos utiliza a seguinte definição de grafo, que é mais abstraia do que a utilizada neste artigo.

Definição: Um grafo é constituído por duas listas: a primeira é formada por um conjunto finito de elementos chamados vértices do grafo; a segunda é constituída por pares de elementos da primeira; cada par é chamado uma aresta do grafo.

Se tomássemos em conta, ainda, uma orientação nas arestas, um grafo orientado seria um par de conjuntos, A e B, onde A é um conjunto finito, cujos elementos são os vértices do grafo, e  B é um subconjunto de A x A.   Os elementos de  B  são as arestas do grafo orientado.

No desenvolvimento desse artigo, o conceito de grafo plano será importante.

Definição: Um grafo se diz plano se seus vértices e suas arestas estiverem todos em um mesmo plano.

Por exemplo, o grafo formado pelos vértices e lados de um triângulo é um grafo plano, enquanto o grafo formado pelos vértices e arestas de um cubo não é um grafo plano.

Definição: Um grafo se diz planar quando for equivalente a um grafo plano.

Exemplo: No exemplo de grafos equivalentes, verifica-se que o grafo formado pelos vértices e arestas de um tetraedro é um grafo planar.

Para mostrar que um grafo é planar, é suficiente achar um grafo plano que lhe seja equivalente. Por outro lado, para mostrar que um grafo não é planar, é necessário demonstrar que qualquer grafo que lhe seja equivalente não pode ser plano. Isto, por si, já dá uma idéia do valor de uma caracterização de grafos planos. O Teorema de Euler que mostraremos neste artigo caminha nessa direção, mas são ainda necessárias algumas definições para o seu enunciado.

Definição: Dados dois vértices A e B de um grafo, dizemos que existe um caminho unindo (ou ligando) A a B, se existirem vértices V₁ V₂, ^{. . .}, V_n  e arestas A V₁ V₁V₂, ^{. . .} , V_n_₁V_n  e   V_nB.

Ou seja, intuitivamente, é possível ir de A a B percorrendo um caminho formado por arestas do grafo.

No grafo da figura C, é possível unir A a C (AB, BC), mas não é possível unir A  a D, por exemplo.

Definição: Um grafo é conexo se dois quaisquer de seus vértices podem ser unidos por um caminho.

Os exemplos das figuras A e B são de grafos conexos. Já o da figura C não é conexo.

Fig. A                                       Fig. B                                    Fig. C       

Todo grafo conexo divide o plano em um certo número de regiões R_i, como nos exemplos abaixo.

ou

ou

 

ou ainda

Das regiões determinadas no plano pelas arestas de um grafo conexo plano, uma é "ilimitada" e as restantes são "limitadas" pelas arestas do grafo.

Podemos agora enunciar o teorema de Euler:

Teorema (Euler): Em todo grafo plano conexo V A + R = 2, onde V = número de vértices, A = número de arestas e R = número de regiões determinadas no plano pelo grafo.

Observe que o método usual de demonstração do teorema de Euler para poliedros consiste realmente em transformar o problema de verificação desta fórmula para os poliedros em um problema sobre a relação entre o número de vértices, arestas e regiões do plano determinadas por um grafo conexo plano, obtido a partir do poliedro pela retirada de uma de suas faces e deformação do restante sobre o plano.

Apresentamos, a seguir, esboços dos cinco sólidos regulares e dos grafos planos que obtemos tratando-os da maneira descrita acima. Estas figuras ilustram também que os grafos constituídos dos vértices e arestas de cada um destes sólidos são grafos planares.

Demonstraremos agora o teorema de Euler para qualquer grato conexo plano.

Demonstração:

Observe, em primeiro lugar, que qualquer grafo plano conexo pode ser obtido a partir do grafo mais simples, o que consiste somente em um vértice e nenhuma aresta, por meio das seguintes operações:

Operação 1: Adicionar uma aresta e um vértice a um vértice já existente

Observe que, no caso do grafo mais simples, o que tem somente um vértice e zero arestas, verificamos que  V = 1, A = 0  e  R = 1. Donde, no caso citado,   V A + R = 1 0 + 1 = 2.

Examinemos, agora, como cada um dos tipos de operações descritas acima altera a quantidade V A + R. Para cada uma das operações descritas, sejam V, A, R e (V A + R) as alterações causadas, respectivamente, no número de vértices, arestas, regiões e em   V A + R.

É fácil, então, verificar que a seguinte tabela descreve os efeitos de cada uma das operações.

Assim, a expressão V A + R permanece invariante sob as três operações consideradas e o grafo permanece conexo. Como qualquer grafo plano conexo pode ser obtido a partir do grafo mais simples por uma sequência finita de tais operações, vemos que, para qualquer grafo conexo plano,

V A + R = 2.

Observação: O leitor pode verificar que para construir um grafo não conexo seria preciso introduzir uma outra operação, a saber

Operação 4: Adicionar um vértice isolado.

Estendendo a idéia de contagem das regiões a grafos planos não conexos (por exemplo, como o número de componentes conexas em que fica dividido o que sobra do plano quando se exclui o grafo), ainda assim, na operação 4, teríamos  V = +1, A = R = 0  e, então  A(V A + R) não seria zero.

Comparemos a demonstração que acabamos de fazer com a que consta dos livros-textos (demonstração de Cauchy). Lá, o grafo plano obtido retirando uma das faces do poliedro e deformando as outras sobre o plano é "desmontado", retirando-se seus vértices e arestas, até chegar à situação mais simples possível. A demonstração que demos aqui procede no sentido inverso: a partir do grafo formado por um único ponto, "montamos" um grafo conexo plano, arbitrário.

Resolução do problema proposto

Voltando ao problema: é possível ligar água, luz e telefone a três casas, sem que as ligações se cortem (supondo que todas as ligações, fios è canos estejam situados em um mesmo plano)?

A situação pode ser representada geometricamente como segue

O problema é verificar se o grafo de vértices  C₁, C₂, C₃, A, L, T e arestas AC₁, AC₂, AC₃, LC₁, LC₂, LC₃, TC₁ TC₂ e TC₃   é, ou não, plano.

Este grafo é obviamente conexo (por quê?). Além disso, para ele,   V = 6 e  A = 9.

Suponhamos que ele seja plano. Pela fórmula de Euler, devemos, então, ter

V A + R = ^.2

donde R = 2 V + A = 2 6 + 9 = 5, ou seja, devemos ter 5 regiões do plano determinadas pelo grafo. Assim, como uma destas regiões é ilimitada, devemos ter exatamente 4 regiões limitadas por arestas do grafo.

Considere agora as regiões limitadas pelas arestas mostradas nas figuras

2 regiões limitadas                 2 regiões limitadas                    2 regiões limitadas

Assim, temos pelo menos 6 regiões limitadas por arestas do grafo, o que viola a fórmula de Euler. Logo, o grafo não pode ser plano.

(O autor agradece as sugestões do Comitê Editorial da RPM, que contribuíram para melhorar a apresentação deste artigo.)

Referências Bibliograficas

[1] Ore, O. Graphs and their uses. The Mathematical Association of America, 1963, cap. 1 e 8

[2] Luchesi, C. Introdução à Teoria dos Grafos. IMPA, 1979.

[3] Cohen, D.I.A. Basic Techniques of Combinatorial Theory. J. Wiley, 1978, cap.7.