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

[veja o problema aqui]

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

O que é um grafo?

Um "grafo simples" é 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.

Exemplos:

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

A figura abaixo não é um grafo simples. Não consideraremos figuras deste tipo como sendo um grafo simples 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.
 

No que segue, grafos simples serão chamados apenas de "grafos", pois nesta sequência de postagens não consideraremos outros tipos de grafos.

 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).

Exemplos:

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

A figura abaixo 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.

Exemplos:

Na figura acima, 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 figura abaixo, 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 vértice e.

O que é um caminho fechado?

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

Exemplos:

Na figura acima, 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 figura abaixo 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.

Exemplos:

No desenho acima, 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 desenho abaixo, 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 abaixo é 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 acima 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 a figura abaixo 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 o grafo acima tem 3 regiões (que estão representadas por cores diferentes: cinza claro, cinza escuro e branco). A “parte exterior” (de cor branca) também é considerada uma região, portanto todo grafo pode ser pensado como estando desenhado dentro de um retângulo. 

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

O grafo abaixo 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.