Fórum de Matemática
DÚVIDAS? Nós respondemos!

Um Fórum em Português dedicado à Matemática
Data/Hora: 28 mar 2024, 19:56

Os Horários são TMG [ DST ]




Fazer Nova Pergunta Responder a este Tópico  [ 2 mensagens ] 
Autor Mensagem
 Título da Pergunta: Grafos
MensagemEnviado: 04 jan 2014, 18:28 
Offline

Registado: 04 jan 2014, 18:08
Mensagens: 1
Localização: alemanhã
Agradeceu: 0 vez(es)
Foi agradecido: 0 vez(es)
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?


Anexos:
Sem Título.png
Sem Título.png [ 86.52 KiB | Visualizado 2642 vezes ]
Topo
 Perfil  
 
 Título da Pergunta: Re: Grafos
MensagemEnviado: 07 jan 2014, 17:14 
Offline

Registado: 14 dez 2011, 15:59
Mensagens: 897
Localização: Portugal
Agradeceu: 20 vezes
Foi agradecido: 373 vezes
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.


Topo
 Perfil  
 
Mostrar mensagens anteriores:  Ordenar por  
Fazer Nova Pergunta Responder a este Tópico  [ 2 mensagens ] 

Os Horários são TMG [ DST ]


Quem está ligado:

Utilizadores a ver este Fórum: Nenhum utilizador registado e 7 visitantes


Criar perguntas: Proibído
Responder a perguntas: Proibído
Editar Mensagens: Proibído
Apagar Mensagens: Proibído
Enviar anexos: Proibído

Pesquisar por:
Ir para:  
cron