domingo, 20 de fevereiro de 2011

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


Este texto é uma introdução à solução que apresentaremos  para o problema das três casas.

O que é um grafo?

Um grafo é um conjunto de pontos com linhas contínuas (retas ou não) que unem alguns desses pares de pontos. Aos pontos chamaremos de vértices e às linhas que conectam os pontos chamaremos de arestas.

Exemplo:


A figura ao lado é um grafo, os pontos azuis são os vértices e as linhas verdes são as arestas.








A figura ao lado não é um grafo. Não consideraremos figuras deste tipo como sendo um grafo por dois motivos: há uma aresta com os dois extremos no mesmo vértice a e há duas arestas distintas que conectam os mesmos vértices b e c.




O que é um grafo finito?

Um grafo finito é um grafo com um número finito de vértices.

O que é um grafo planar?

Um grafo planar é um grafo que pode ser desenhado no papel sem que suas arestas se cortem (em outras palavras, sem que se cruzem, ou se intersectem, ou passe uma por cima da outra).

Exemplo:


A figura ao lado é um grafo planar, pois nenhuma aresta passa por cima da outra.







A figura ao lado não é considerada um grafo planar pois a aresta df corta a aresta ae (ou vice versa).










O que é um caminho?

Um caminho é uma sequência alternada de vértices e arestas, na qual cada aresta conecta o vértice anterior ao próximo.

Exemplo:

 Na primeira figura, a sequência alternada de vértices e arestas a, E1, b, E2, d, E3, c é um caminho (imagine que se você colocasse uma formiga no vértice a ela seria capaz de chagar ao vértice c andando apenas pelas arestas marcadas de vermelho).


Na segunda figura, a sequência alternada de vértices e arestas a, E1, b, E2, c, E3, d não é um caminho, pois o vértice E3 não conecta o vértice c ao d (imagine que colocando uma formiga no vértice a ela não seria capaz de chegar até o vértice d andando apenas pelas arestas marcadas de vermelho). Do mesmo modo a sequência a, E1, b, E2, e, E3, d não é um caminho, pois E2 não conecta o vértice b ao e.



O que é um caminho fechado?

Um caminho é fechado quando o primeiro vértice da sequência é igual ao último.

Exemplo:



Na primeira figura, o caminho a, E1, b, E2, c, E3, d, E4, b, E1, a é um caminho fechado, pois o vértice inicial é igual ao vértice final (ou seja, o ponto de saída é também o ponto de chegada).










Já o caminho na segunda figura não é fechado, pois o vértice inicial a é diferente do vértice final d (ou seja, o ponto de saída é diferente do ponto de chegada).








O que é um ciclo?

Um ciclo é um caminho fechado de comprimento 3 ou mais onde todos os vértices são distintos, exceto o primeiro que é igual ao último.

Exemplo:


No primeiro desenho, o caminho a, E1, b, E2, c, E3, d, E4, a é um ciclo, pois cada vértice aparece apenas uma vez e, além disso, o vértice final é igual ao vértice inicial (ou seja, o ponto de saída é igual ao ponto de chegada e além disso a formiga passaria apenas uma vez em cada um dos vértices do caminho).



No segundo desenho, o caminho fechado a, E1, b, E2, c, E3, d, E4, b, E1, a não é um ciclo, pois o vértice b se repete (ou seja, para chegar ao ponto de chegada, que foi também o ponto de partida, a formiga teria que passar duas vezes pelo vértice b).









O que é comprimento?

O comprimento de um caminho é o número de arestas que formam o caminho.

Exemplo:

O comprimento do caminho representado no grafo ao lado é 3, pois ele tem três arestas (ou seja, para percorrer este caminho a formiga teria que passar por 3 arestas diferentes).

O que é um grafo conexo?

Um grafo é conexo se existe um caminho entre quaisquer dois dos seus vértices.

Exemplo:



No desenho ao lado o grafo é conexo (imagine que colocando uma formiga em um vértice qualquer ela pode chegar a qualquer um dos outros vértices andando apenas em cima das arestas)








O grafo nesta outra figura não é conexo, pois não existe, por exemplo, um caminho conectando o vértice g ao vértice a (ou seja, saindo do vértice g a formiga não seria capaz de chegar ao vértice a andando apenas em cima das arestas).






O que é uma região?

No grafo, uma região é uma das partes do plano limitada por arestas.

Exemplo de regiões:
  
Diz-se que este primeiro grafo tem 3 regiões (que estão representadas por cores diferentes: cinza claro, cinza escuro e branco). A “parte exterior” (colorida de branca) também é considerada uma região, portanto todo grafo pode ser pensado como estando desenhado dentro de um retângulo. 







O grafo ao lado tem 4 regiões (contando, como já dissemos, a "parte de fora" que é branca).










O grafo ao lado tem 3 regiões.










 O que é grau?

O grau de uma região é o comprimento do ciclo ou do caminho fechado que forma o bordo de uma região (ou seja, é o número de arestas que a formiga terá que atravessar para chegar ao ponto final. O ponto final deverá ser, necessariamente, igual ao ponto de partida).

Exemplo:


No grafo acima:

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

As informações acima nos serão muito úteis para resolvermos o problema das três casas usando a linguagem da teoria dos grafos.


A 2ª parte da solução pode ser vista aqui.

Referência:

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


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

2 comentários :

  1. Olá, Pedro!
    Rapaz! Que tesouro encontrei agora! Procurava justamente, encontrar uma explicação desse quilate sobre os grafos! Vou recomendar e enviar esse link para uma pá de gente que sei que, vai gostar de ter essa aula nota 10!
    Obrigado, por ser tão generoso em detalhar todos os pormenores do assunto e, tão didático, que mesmo estendendo na explanação, não cansa a nossa mente!
    Um abraço!!!!!

    ResponderExcluir
  2. Olá Francisco Valdir, realmente a explanação se estendeu um pouco mas é que eu tentei deixá-la o mais clara possível, de modo que o único pré-requisito necessário ao leitor é o Teorema de Euler que foi utilizado (mas que eu pretendo demonstrar aqui no BLOG MANTHANO futuramente). Por isso eu tive que escrever a solução em 3 partes do que resultou que a 1ª ficou quase como uma introdução a linguagem da teoria dos grafos.

    Muito obrigado pelo elogio! Gostei muito de saber que achou a exposição didática!!!

    A propósito, eu já encontrei seu banner! inclusive já o adicionei na minha lista.

    Até.

    ResponderExcluir

Arquivo do BLOG MANTHANO

Atualizações dos nossos parceiros: