quarta-feira, 23 de fevereiro de 2011

Solucionando o problema das 3 casas através da Teoria do Grafos - Parte 2



Vamos então à solução. O texto dizia: ...deixamos os seguintes desafios para o leitor interessado e curioso: Achar a solução para o caso de duas casas ... Achar a solução para o caso de três casas ... Como responder os desafios????

Para o caso em que temos apenas duas casas, basta algumas poucas tentativas (ou uma única) para conseguirmos desenhar a figura, uma solução é a seguinte:


 Para o caso em que há três casas... vamos responder algumas perguntas:

Pergunta 1: quantas ligações teriam que existir para o problema ser resolvido?


Veja que a eletricidade tem que se conectar com as 3 casas (são 3 ligações).
 A água também tem que se conectar com as 3 casas (mais 3 ligações).
 E de igual modo o esgoto tem que se conectar com as 3 casas (mais 3 ligações).

Portanto terá que existir 9 ligações, ou seja, nove riscos no papel.

Antes de continuar vamos simplificar nossa figura e adaptar nossa linguagem de acordo com a teoria dos grafos.

Comecemos desenhando apenas pontos em vez retângulos e de casinhas:


 Vamos chamar cada ponto da figura acima de vértice.

Em vez de dizermos ligação de água (ou de esgoto ou de eletricidade) vamos simplesmente dizer arestas.

E em vez de dizermos “figura” ou “desenho” vamos dizer grafo.

Então nosso problema pode ser enunciado da seguinte maneira: Construir um grafo que tem 6 vértices e 9 arestas, no qual as arestas não se intersectem (ou não se cortem, ou não se cruzem, ou não passem uma por cima da outra...).

Para expressar esse fato (de as arestas não se cortarem) vamos dizer que o grafo deverá ser planar, portanto temos simplesmente que construir um grafo planar que tem 6 vértices e 9 arestas.

Note ainda, e isso é importante, que nosso grafo deverá ser conexo, ou seja, colocando uma formiga em qualquer um dos 6 vértices e dando-lhe a ordem de caminhar somente sobre as 9 arestas ela poderá perfeitamente chegar em qualquer um dos outros 5 vértices.

Pergunta 2: quantas regiões o nosso grafo deverá ter?

Para responder a esta questão, é necessário usar o Teorema de Euler (lê-se óiler) que prova-se ser válido para grafos planares conexos: V+R=A+2, onde V é o número de vértices, A é o número de arestas e R é o número de regiões.
Portanto, pelo teorema de Euler (lê-se óiler) podemos garantir que nosso grafo deverá ter 5 regiões:

V+R=A+2
6+R=9+2
6+R=11
R=11-6
R=5

Pergunta 3: no grafo que pretendemos construir, de todas as 5 regiões, qual será o grau daquela que tiver o menor grau?

Observe que nenhuma das três casas se ligará a outra casa e nenhuma das três distribuidoras (de água, eletricidade ou esgoto) se ligará a outra distribuidora, ou seja, não haverá três vértices conectados entre si, logo não haverá este tipo de ligações (traçada em preto):


 Em outras palavras: não haverá região triangular , logo o menor grau de uma das 5 regiões deverá ser 4 (maior do que 3).

Importante: note que em qualquer grafo planar conexo cada aresta é bordo (ou seja, é uma divisa) de exatamente duas regiões. Isso significa que se você somar os graus das regiões cada aresta será contada duas vezes (pois faz parte de duas regiões). Escrevendo isso como uma equação: SG=2A, onde SG é a soma dos graus e A é o número de arestas.

Vejamos um exemplo de um caso particular para compreendermos melhor o que acaba de ser dito:


No grafo acima (que foi desenhado três vezes com destaque em vermelho ao bordo de cada região) observamos que:

O grau da região 1 é 4.
O grau da região 2 é 3.
O grau da região 3 é 3.

Somando os graus das três regiões obtemos 4+3+3=10. Note que o grafo possui 5 arestas, então neste grafo, assim como em qualquer outro que seja planar conexo, a soma dos graus (10) é igual ao dobro (2 vezes) do número de arestas (5): 10=2.5.

Usando estas informações podemos chegar a uma conclusão: propomos que o leitor que desconhece a resposta medite nas informações apresentadas acima para tentar elaborar um argumento que responde ao desafio para o caso em que há três casas. E só então leia a parte final.

Referência:

LIPSCHUTZ, Seymour; LIPSON, Marc L. Teoria dos Grafos. In: Teoria e Problemas de Matemática Discreta2. ed. Porto Alegre: Bookman, 2004. (p.188-228)

*Qualquer crítica ao conteúdo apresentado pode ser feita aqui.

11 comentários :

  1. Respostas
    1. Sugiro que leia todas as postagens sobre este tópico (basta clicar nos links no início e no fim do texto). Abraço.

      Pedro R.

      Excluir
  2. kkkk' que porra é essa²

    ResponderExcluir
    Respostas
    1. Sugiro que leia todas as postagens sobre este tópico (basta clicar nos links no início e no fim do texto)². Abraço.

      Pedro R.

      Excluir
  3. Não consigo entender.Tentei,mas não consigo.Haaaa,não gostei do site não não é bem explicado em desenhos.Péssimo.:(

    ResponderExcluir
    Respostas
    1. Olá Anônimo de 14/10. Que bom que, ao menos, tentou entender. Certamente, num futuro próximo, se continuar se esforçando conseguirá compreender. Matemática é assim mesmo... às vezes precisamos de tempo...

      Quanto a não ter gostado do site, sinto muito. Afinal, sempre nos esforçamos ao máximo para deixarmos as coisas bem claras. De qualquer modo, tentarei elaborar melhores explicações com desenhos no futuro.

      Ah, só um último aviso: por uma série de motivos que não listarei, é normal não compreender coisas. Por isso, não se desmotive! Provavelmente, o problema não está em você. Abraço.

      Pedro R.

      Excluir
  4. não entendi tentei e não consegui da a resposta ai que eu vou ver mais da a resposta explicando que ai eu irei entender por favor obrigado

    ResponderExcluir
    Respostas
    1. Basta clicar em "parte final", ao fim do texto, para ler a resposta. Pedro R.

      Excluir
  5. q bosta vei nem funciona issae mor comunista

    ResponderExcluir
  6. venho tentando encontrar essa resposta há 20 anos, kkkk, só hoje tive a ideia de olhar na internet. eu sempre desconfiei que não tinha solução, mas não fazia ideia de como saber. agora, depois de ter me formado em matemática e depois desta bela explicação,entendo perfeitamente. obrigado. foi brilhante.

    ResponderExcluir

Arquivo do BLOG MANTHANO

Atualizações dos nossos parceiros: