Teoria Grafos

Entregar no dia da prova Grupo de 2 alunos 1 - Na Cidade ao Sol o servio de autocarros, movidos a energia solar, une diretamente algumas das 10 zonas da cidade entre as quais h mais deslocaes dirias. Os autocarros no efetuam paradas intermdiarias. No quadro descreve-se o grafo que representa as linhas e sentidos em que o servio operado, utilizando uma matriz de adjacncia de que s se escrevem os elementos no nulos. As diferentes zonas da cidade so representadas por maisculas de A a J. ABCDEFGHIJA11BC111D1E1F1G11H11I1J11 a) Para que zonas da cidade se pode deslocar um passageiro que esteja na zona F b) Para ir de C para H qual o nmero mnimo de autocarros que um passageiro deve usar c) O sistema garante o transporte de passageiros entre qualquer par de zonas d) Caso a resposta tenha sido no apresente uma soluo, inserindo novos percursos, que permita o transporte de passageiros entre qualquer par de zonas da cidade. (Isto , acrescente arcos de modo a transformar o grafo num grafo fortemente conexo). 2 Os Amigos Joo, Pedro, Antnio, Marcelo e Francisco sempre se encontram para botar conversa fora e s vezes jogar dama, xadrez e domin. As preferncias de cada um so as seguintes Joo s joga xadrez Pedro no joga domin Antnio joga tudo Marcelo no joga xadrez e domin e Francisco no joga nada. Representa atravs de um grafo bipartido G (V,E) todas as possibilidades de um amigo jogar com os demais. Defina V e E. Defina um subgrafo em que todos menos Francisco joguem ao mesmo tempo