teoria dos grafos
344 palavras
2 páginas
Ciência da computaçãoTeoria dos Grafos
Trabalho 1
Em equipe de 4 pessoas, para entregar em PDF no 15/04/2014 via MOODLE
PROFESSORA: Diane Castonguay
JUSTIFIQUE TODAS AS SUAS RESPOSTAS
Consideramos todos os grafos simples e conexos.
Questão 1
[4 pts] Consideramos o seguinte grupo de alunos: Beatriz, Chen,
Filipe, Giseli, Lucas, Sara e Thiago. Temos as seguintes rivalidades no grupo:
1. Beatriz não gosta do Thiago
2. Chen não suporta Filipe
3. Filipe não se entende com Thiago
4. Giseli e Beatriz sempre brigam
5. Lucas e Filipe não podem estar junto.
6. Sara faz sempre a Giseli chorar
Queremos dividir o grupo em duas equipes de tal forma que não tem membros da mesma equipe com rivalidade.
(a) Existe uma tal divisão considerando que Beatriz e Lucas não pertence a mesma equipe?
(b) Existe uma tal divisão considerando que Beatriz e Lucas pertence a mesma equipe? (c) Em cada um dos itens acima, explica como seria a estrutura de grafos utilisada. (d) Como seria um metodo geral dado um entrada qualquer de um grupo e de uma lista de rivalidade?
Questão 2 [2 pts]
Existe um grafo bipartido autocomplementar?
1
Questão 3 [4 pts]
Consideramos quinze tarefas
T 1, . . . , T 15.
Sabendo que tem que:
• T1
depende de
T 2.
T2
depende de
T 7.
• T3
depende de
T 8.
T4
depende de
T 8.
• T5
depende de
T 1.
T5
depende de
T 9.
• T5
depende de
T 10.
• T6
depende de
T 8.
T6
depende de
T 9.
• T7
depende de
T 1.
T7
depende de
T 10.
• T8
depende de
T 14.
T9
• T9
depende de
T 13.
T 10
depende de
T 2.
T6
depende de
depende de
T 5.
T 12.
• T 10
depende de
T 3.
T 11
depende de
T 3.
• T 11
depende de
T 4.
T 12
depende de
T 6.
• T 12
depende de
T 15.
T 13
depende de
T 12.
• T 14
depende de
T 11.
T 15
depende de
T 9.
• T 15
depende de