P1 - Segundo Semestre 2012

Prévia do material em texto

Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Prova 1
480339 — Teoria dos Grafos
Caˆndida Nunes da Silva
2o Semestre de 2012
Nome:
RA: Turma:
Instruc¸o˜es: A durac¸a˜o da prova e´ de 100 minutos. Na˜o e´ per-
mitido usar qualquer material de consulta durante a prova. As
questo˜es podem ser respondidas em qualquer ordem, a la´pis ou
caneta. Na correc¸a˜o, s´ımbolos ou palavras ileg´ıveis na˜o sera˜o con-
siderados. Questo˜es mal justificadas sera˜o consideradas er-
radas!
Questa˜o Valor Nota
1 2,0
2 2,0
3 2,0
4 2,0
5 2,0
Total 10,0
1. (2,0) Para cada uma das afirmac¸o˜es abaixo, indique se e´ verdadeira ou falsa, justificando a
sua resposta.
(a) (0,5) Todo grafo 2-regular de n ve´rtices e´ isomorfo ao Cn.
(b) (0,5) O K5 e´ euleriano.
(c) (0,5) O grafo de Petersen tem uma decomposic¸a˜o em ciclos.
(d) (0,5) O prisma triangular e´ hamiltoniano.
2. (2,0) Prove ou deˆ um contra-exemplo para as afirmac¸o˜es a seguir:
(a) (1,0) Seja G um grafo ac´ıclico com n ve´rtices, m arestas e c componentes conexas. Enta˜o
m = n− c.
(b) (1,0) Toda aresta de corte incide em um ve´rtice de grau um.
3. (2,0) Mostre que:
(a) (1,0) se G e´ um grafo com δ(G) ≥ 2, enta˜o G tem um ciclo;
(b) (1,0) se G e´ um grafo com n ve´rtices e m arestas e tal que m ≥ n, enta˜o G conte´m um
ciclo.
4. (2,0) Um torneio e´ uma orientac¸a˜o de um grafo completo. Um grafo direcionado e´ ac´ıclico
se na˜o tem um ciclo direcionado. Com base nessas definic¸o˜es, responda a`s questo˜es a seguir:
(a) (1,0) Descreva um algoritmo para encontrar uma orientac¸a˜o de um grafo completo que
seja um torneio ac´ıclico. Justifique por que seu algoritmo funciona.
(b) (1,0) Descreva um algoritmo para encontrar uma orientac¸a˜o de um grafo simples qualquer
que seja ac´ıclica. Justifique por que seu algoritmo funciona.
5. (2,0) Quais dos grafos abaixo sa˜o isomorfos e quais na˜o sa˜o? Justifique todas as suas respostas.
G1
G2
G3
G4