Avaliações Grafos 2011

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

grafos2011/p1.pdf
Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Prova 1
341118 — Teoria dos Grafos
Caˆndida Nunes da Silva
1o Semestre de 2011
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 ale´m
daquele provido pela professora. As questo˜es podem ser respondi-
das em qualquer ordem, a la´pis ou caneta. Na correc¸a˜o, s´ımbolos
ou palavras ileg´ıveis na˜o sera˜o considerados. Questo˜es mal jus-
tificadas sera˜o consideradas erradas!
Questa˜o Valor Nota
1 2,0
2 2,0
3 2,0
4 2,0
5 2,0
Total 10,0
1. Prove ou deˆ um contra-exemplo para as afirmac¸o˜es a seguir:
(a) Um grafo simples e´ auto-complementar se e somente se e´ conexo.
(b) O complemento de um grafo bipartido e´ sempre desconexo.
(c) Todo grafo regular tem um emparelhamento perfeito.
(d) Todo grafo cu´bico tem ordem (nu´mero de ve´rtices) par.
2. Desenhe todos os grafos simples na˜o rotulados de 4 ve´rtices.
3. Responda a`s questo˜es abaixo:
(a) O que e´ um subgrafo gerador de um grafo G?
(b) Quantos sa˜o os subgrafos geradores (rotulados) de um grafo G de n ve´rtices e m arestas?
Justifique.
(c) Deˆ um exemplo de um subgrafo gerador pro´prio e na˜o vazio do prisma pentagonal.
4. Mostre que se G e´ um grafo com n ve´rtices e m arestas e tal que m ≥ n, enta˜o G conte´m um
ciclo. Ale´m disso, encontre um grafo ac´ıclico com n ve´rtices e n− 1 arestas, para todo inteiro
positivo n.
5. Considere o seguinte algoritmo guloso para resolver o Problema do Caixeiro Viajante em um
grafo ponderado completo:
• Selecione um ve´rtice arbitra´rio v.
• Partindo de v construa um caminho hamiltoniano acrescentando uma aresta a cada
iterac¸a˜o segundo o seguinte crite´rio: deve ser uma aresta incidente ao u´ltimo ve´rtice
adicionado ao caminho cujo outro extremo na˜o pertenc¸a ao caminho e de peso mı´nimo.
• Complete o ciclo hamiltoniano adicionando a aresta que liga os extremos do caminho
hamiltoniano.
Encontre um grafo ponderado completo em que esse algoritmo na˜o retorna o ciclo hamiltoni-
ano de peso mı´nimo. Indique claramente a sequeˆncia de ve´rtices no caminho hamiltoniano e
o peso do ciclo hamiltoniano encontrado pelo algoritmo guloso em seu exemplo, bem como a
sequeˆncia c´ıclica de ve´rtices e o peso do ciclo hamiltoniano de peso mı´nimo.
Resumo
Teorema 1.1 Para todo grafo G temos
∑
v∈V
d(v) = 2m.
Teorema 2.1 Seja G um grafo tal que δ(G) ≥ 2. Enta˜o G conte´m um ciclo.
Teorema de Re´dei (2.3) Todo torneio tem um caminho hamiltoniano direcionado.
Problema do Caixeiro Viajante Dado um grafo ponderado (G,w), encontre um ciclo hamilto-
niano de G de peso mı´nimo.
Teorema de Veblen (2.7) Um grafo admite uma decomposic¸a˜o em ciclos se e somente se e´ par.
grafos2011/p2.pdf
Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Prova 2
341118 — Teoria dos Grafos
Caˆndida Nunes da Silva
1o Semestre de 2011
Nome:
RA: Turma:
Instruc¸o˜es: Escolha 4 dentre as 6 questo˜es da prova para res-
ponder. Anote na tabela ao lado a sua escolha atribuindo valor
2, 5 para as questo˜es escolhidas e 0 para as demais. Caso a tabela
na˜o seja preenchida adequadamente, as questo˜es selecionadas por
padra˜o sa˜o as numeradas de 1 a 4.
A durac¸a˜o da prova e´ de 100 minutos. Na˜o e´ permitido usar qual-
quer material de consulta durante a prova ale´m daquele provido
pela professora. As questo˜es podem ser respondidas em qual-
quer ordem, a la´pis ou caneta. Na correc¸a˜o, s´ımbolos ou pala-
vras ileg´ıveis na˜o sera˜o considerados. Questo˜es mal justificadas
sera˜o consideradas erradas!
Questa˜o Valor Nota
1
2
3
4
5
6
Total 10,0
1. Um hidrocarboneto saturado e´ uma mole´cula de fo´rmula CmHn na qual cada a´tomo de carbono
(C) tem quatro ligac¸o˜es, cada a´tomo de hidrogeˆnio (H) tem uma ligac¸a˜o e nenhuma sequeˆncia
de ligac¸o˜es forma um ciclo. Mostre que, para todo inteiro positivo m, a mole´cula CmHn so´
pode existir se n = 2m + 2. Justifique cuidadosamente suas afirmac¸o˜es.
2. Execute uma busca em profundidade no grafo direcionado abaixo. Os ve´rtices sa˜o rotulados
com valores de 1 a 10. Considere que o grafo e´ representado por uma lista de adjaceˆncias em
que os vizinhos de sa´ıda de cada ve´rtice sa˜o listados em ordem crescente de ro´tulo e que a
busca e´ iniciada no ve´rtice 1. Especifique os valores registrados nos vetores d e f ao final da
busca e classifique cada aresta do grafo como aresta de floresta, de retorno, direta ou cruzada.
1 2 3
4 5 6 7
8 9 10
3. Deˆ um algoritmo de complexidade O(n + m) no pior caso para o problema de determinar se
um grafo e´ Euleriano. Qual estrutura de dados voceˆ usa para representar o grafo? Justifique
por que seu algoritmo funciona e tem a complexidade esperada.
4. Um caminho hamiltoniano e´ um caminho que passa por todos os ve´rtices de um grafo exata-
mente uma vez. Descreva um algoritmo de complexidade O(n+m) para determinar quando
um grafo direcionado ac´ıclico possui um caminho hamiltoniano direcionado. Justifique por
que seu algoritmo funciona e tem a complexidade esperada.
5. Um conjunto de n cidades e´ interligado por uma malha de 3n estradas. Todas as estradas sa˜o
de ma˜o dupla, e a malha e´ tal que a partir de uma cidade qualquer e´ poss´ıvel chegar em todas as
demais. Houve uma deteriorac¸a˜o na malha de estradas, devida a um longo per´ıodo de chuvas
intensas, tornando algumas estradas ruins e outras pe´ssimas (na˜o existem estradas em bom
estado). Para consertar uma estrada, e´ necessa´rio interdita´-la em ambos os sentidos. O DNER
pretende consertar (e interditar) o maior nu´mero poss´ıvel de estradas simultaneamente, mas
garantindo que ainda seja poss´ıvel sair de uma cidade qualquer e chegar em todas as demais.
Ale´m disso, o DNER tambe´m quer que o conjunto de estradas na˜o interditadas tenha o maior
nu´mero poss´ıvel de estradas ruins, para privilegiar o conserto das pe´ssimas.
(a) Modele o problema acima como um problema em grafos, indicando claramente que ele-
mentos sa˜o representados pelos ve´rtices e pelas arestas e se o grafo e´ ou na˜o direcionado,
se e´ ou na˜o ponderado e o que representam as orientac¸o˜es e pesos, caso existam.
(b) Quantas estradas na˜o sera˜o interditadas? Justifique sua resposta.
(c) Segundo sua modelagem, qual e´ o problema em grafos que queremos resolver? Justifique
sua resposta.
(d) Existe algoritmo de complexidade O(n log n) para resolver este problema? Justifique.
Em caso afirmativo, indique as estruturas de dados que devem ser utilizadas na imple-
mentac¸a˜o do algoritmo para garantir a complexidade dada.
6. Seja G = (V,E) um grafo ponderado orientado, com pesos positivos nas arestas, e Tv uma
a´rvore de caminhos mı´nimos de algum ve´rtice v aos demais ve´rtices de G. Prove ou deˆ um
contra-exemplo para cada uma das afirmac¸o˜es a seguir:
(a) Se o peso de todas as arestas de G for acrescido de um valor constante c positivo, a
a´rvore Tv continua sendo uma a´rvore de caminhos mı´nimos a partir de v.
(b) Se o peso de todas as arestas de G for multiplicado por uma constante positiva c, a
a´rvore Tv continua sendo uma a´rvore de caminhos mı´nimos a partir de v.
grafos2011/t1.pdf
Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Teste 1
341118 — Teoria dos Grafos
Caˆndida Nunes da Silva
1o Semestre de 2011
Nome: RA: Turma: A
Instruc¸o˜es: A durac¸a˜o da prova e´ de 30 minutos. Na˜o e´ permitido usar qualquer material de
consulta durante a prova. A questa˜o pode ser respondida
a la´pis ou caneta. Na correc¸a˜o, s´ımbolos
ou palavras ileg´ıveis na˜o sera˜o considerados.
Questa˜o
Seja G[X,Y ] um grafo bipartido.
1. Mostre que
∑
v∈X
d(v) =
∑
v∈Y
d(v).
2. Deduza que, se G e´ k-regular para k ≥ 1, enta˜o |X| = |Y |.
grafos2011/t2.pdf
Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Teste 2
341118 — Teoria dos Grafos
Caˆndida Nunes da Silva
1o Semestre de 2011
Nome: RA: Turma: A
Instruc¸o˜es: A durac¸a˜o da prova e´ de 30 minutos. Na˜o e´ permitido usar qualquer material de
consulta durante a prova. A questa˜o pode ser respondida a la´pis ou caneta. Na correc¸a˜o, s´ımbolos
ou palavras ileg´ıveis na˜o sera˜o considerados. Respostas mal justificadas sera˜o consideradas erradas.
Questa˜o
Os oito grafos conexos Gi, 1 ≤ i ≤ 8, apresentados na figura abaixo sa˜o particionados em apenas
duas classes de equivaleˆncia segundo isomorfismo. Identifique quais grafos pertencem a cada classe
de equivaleˆncia, justificando cuidadosamente sua resposta.
G1 G2 G3
G4 G5 G6
G7
G8
grafos2011/t3.pdf
Bacharelado em Cieˆncia da Computac¸a˜o Universidade Federal de Sa˜o Carlos - Campus Sorocaba
Teste 3
341118 — Teoria dos Grafos
Caˆndida Nunes da Silva
1o Semestre de 2011
Nome: RA: Turma: A
Instruc¸o˜es: A durac¸a˜o da prova e´ de 30 minutos. Na˜o e´ permitido usar qualquer material de
consulta durante a prova. A questa˜o pode ser respondida a la´pis ou caneta. Na correc¸a˜o, s´ımbolos
ou palavras ileg´ıveis na˜o sera˜o considerados. Respostas mal justificadas sera˜o consideradas erradas.
Questa˜o
Descreva um algoritmo de complexidade de tempo O(n + m) para o problema de determinar se
um grafo conexo de n ve´rtices e m arestas e´ bipartido. Indique a estrutura de dados utilizada na
representac¸a˜o do grafo. Justifique por que seu algoritmo funciona e por que tem a complexidade
esperada.
Dica: Voceˆ pode usar algoritmos vistos em aula como parte do seu algoritmo, mas deve tomar o
cuidado de levar em conta sua complexidade de tempo na ana´lise de complexidade de seu algoritmo.