| Fórum de Matemática | DÚVIDAS? Nós respondemos! https://forumdematematica.org/ |
|
| Grafos https://forumdematematica.org/viewtopic.php?f=16&t=4717 |
Página 1 de 1 |
| Autor: | carlos indeque [ 04 jan 2014, 18:28 ] | ||
| Título da Pergunta: | Grafos | ||
alguém me pode ajudar neste exercício se faz favor, estou com alguma duvida(a imagem do grafo esta em anexo) (a) Considere o labirinto da figura Comece por representar o labirinto por um grafo. Indique todos os caminhos de Euler possıveis entre o centro A do labirinto e a saıda L. (b) E possıvel construir um grafo planar, simples, bipartido com 8 vertices e 13 arestas?
|
|||
| Autor: | Rui Carpentier [ 07 jan 2014, 17:14 ] |
| Título da Pergunta: | Re: Grafos |
Para cumprir as regras do forum vou só responder a uma questão (a alínea b) até porque a alínea a é 99,9% de suor 0,1% de inspiração. Para a alínea b lembre-se que se um grafo é planar então também é desenhável na esfera e terá de obedecer à fórmula de Euler V-A+F=2 onde V é o nº de vértices, A é o nº de arestas e F é o nº de faces. Logo um tal grafo com 8 vértices e 13 arestas terá de ter 7 faces. Sendo um grafo bipartido (e simples) estas faces terão de ter um nº par de arestas adjacentes maior ou igual a 4. Como cada aresta é adjacente a duas faces temos que a soma, sobre todas as faces, das arestas adjacentes será 26 que é duas vezes o nº de arestas do grafo. Mas se cada uma das 7 faces tem pelo menos 4 arestas adjacentes temos que a soma teria de ser pelo menos 4x7=28 o que é uma contradição. Logo tal grafo não pode ser planar. |
|
| Página 1 de 1 | Os Horários são TMG [ DST ] |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|