Grafos

Trabalho de Teoria dos Grafos
Entregar no dia da prova
Grupo de 2 alunos
1 - Na Cidade ao Sol o serviço de autocarros, movidos a energia solar, une diretamente algumas das 10 zonas da cidade entre as quais há mais deslocações diárias. Os autocarros não efetuam paradas intermédiarias.
No quadro descreve-se o grafo que representa as linhas e sentidos em que o serviço é operado, utilizando uma matriz de adjacência de que só se escrevem os elementos não nulos. As diferentes zonas da cidade são representadas por maiúsculas de A a J.

A
B
C
D
E
F
G
H
I
J
A

1

1

B

C

1

1

1
D

1

E
1

F

1
G

1

1

H
1

1

I

1

J

1

1

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 número mínimo 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 não apresente uma solução, 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 João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para botar conversa fora e às vezes jogar dama, xadrez e dominó. As preferências de cada um são as seguintes: João só joga xadrez; Pedro não joga dominó; Antônio joga tudo; Marcelo não joga xadrez e dominó e Francisco não joga nada.

Representa através 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