Matemática
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).
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.
- Seção De Problemas - 8ª Edição
Hoje vamos ter nossa seção de problemas de número 8. Chegamos até aqui com muitos problemas já propostos, com níveis de dificuldade crescente e, em maioria, interessantíssimos. Nesta edição, não vai ser diferente: problemas extremamente interessantes,...
- Um Problema, Várias Soluções
O objetivo desta postagem é apresentar um problema muito interessante no que diz respeito à variedade de soluções possíveis. O enunciado do problema é o seguinte: Tome muitas varetas, tais quais a representada na figura 1, e comece a construir...
- Solucionando O Problema Das 3 Casas Através Da Teoria Do Grafos - Parte 2
[veja o problema aqui] [veja a 1ª parte da solução aqui] 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...
- Por Que Só Existem 5 Sólidos Platônicos?
Essa pergunta pode ser comum para muitos estudantes durante sua vida, pelo menos para mim foi. Quando estudamos Geometria Espacial nos deparamos com esses sólidos bem peculiares descobrimos que só existem apenas cinco deles, mas por quê? É isso que...
- Pirâmides
Pirâmides Sejam uma região poligonal convexa A1A2A3...An, contida em um plano α. Consideramos todos os segmentos de reta que possuem em extremo pertencente à região poligonal e o outro extremo V: A união de todos esses segmentos de reta é um poliedro...
Matemática
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 é 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 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:
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.
- Seção De Problemas - 8ª Edição
Hoje vamos ter nossa seção de problemas de número 8. Chegamos até aqui com muitos problemas já propostos, com níveis de dificuldade crescente e, em maioria, interessantíssimos. Nesta edição, não vai ser diferente: problemas extremamente interessantes,...
- Um Problema, Várias Soluções
O objetivo desta postagem é apresentar um problema muito interessante no que diz respeito à variedade de soluções possíveis. O enunciado do problema é o seguinte: Tome muitas varetas, tais quais a representada na figura 1, e comece a construir...
- Solucionando O Problema Das 3 Casas Através Da Teoria Do Grafos - Parte 2
[veja o problema aqui] [veja a 1ª parte da solução aqui] 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...
- Por Que Só Existem 5 Sólidos Platônicos?
Essa pergunta pode ser comum para muitos estudantes durante sua vida, pelo menos para mim foi. Quando estudamos Geometria Espacial nos deparamos com esses sólidos bem peculiares descobrimos que só existem apenas cinco deles, mas por quê? É isso que...
- Pirâmides
Pirâmides Sejam uma região poligonal convexa A1A2A3...An, contida em um plano α. Consideramos todos os segmentos de reta que possuem em extremo pertencente à região poligonal e o outro extremo V: A união de todos esses segmentos de reta é um poliedro...