O Princípio da Casa dos Pombos – Aplicação em Grafos

Estava relendo o excelente artigo “O Princípio da Casa dos Pombos“, publicado pelo Reston aqui no blog e me lembrei de um problema em grafos que pode ser provado matemáticamente, de forma bastante elegante, utilizando-se este princípio.

Antes de falar sobre o problema, vamos primeiro recordar brevemente algumas definições sobre grafos (para maiores detalhes, existe um artigo que explora estas definições mais profundamente aqui):

Um grafo é um par ordenado (V,A), onde V e A são conjuntos disjuntos e cada elemento de A corresponde a um par não-ordenado de elementos (não necessariamente distintos) de V. Os elementos do conjunto V são chamados vértices e os elementos do conjunto A são chamados arestas.

Se G é um grafo, então denotamos seu conjunto de vértices por V(G), e o seu conjunto de arestas por A(G).

Além disso, vamos nos recordar brevemente do que é o princípio da casa dos pombos:

Imagine que você está sentado em um banco de praça, num belo domingo ensolarado. A certa altura, você percebe, e começa a contar, o número de pombos que está procurando comida na sua frente. Ao todo, você conta 10 pombos. Entretanto, uma motocicleta passa em alta velocidade e, com o barulho feito, assusta os dez pombos que voam para um pombal com 9 casas. Eles entram e se escondem por lá.

Sabendo que nenhum pombo desviou a direção, o que você pode concluir? Bem, se dez pombos entraram em 9 casas, podemos concluir que em pelos menos 1 casa esconderam-se 2 pombos!

Agora que refrescamos alguns princípios em nossa mente, vamos falar sobre o problema, que se resume a uma simples pergunta: “É verdade que todo grafo com pelo menos dois vértices tem dois vértices com o mesmo numero de vizinhos?”

A resposta é: Sim.

Prova por contradição: Suponha que exista um grafo G, com vértices {v1,v2,… vn}, tal que, os graus dos vértices em G sejam da seguinte forma: d(vn) = (n – 1), d(vn-1) = (n – 2), … , d(v1) = 0. Ora, isso é um absurdo, pois se d(vn) = (n – 1), vn tem vizinhança com todos os vértices em G, e, portanto v1 não pode ter grau 0.

Essa prova só é possível graças à utilização dos princípios de abstração para resolução de problemas.

Vocês sem lembram do nosso artigo sobre redutibilidade?

One comment

Deixe sua opinião!

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s