Notas quase finais
6 views
Skip to first unread message
Joao Meidanis
Jun 29, 2012, 6:01:52 AM6/29/12
to mo405
Oi Gente,
Apos a correcao da prova de ontem, as notas ficaram como estao la' no
site. Falta ainda eu corrigir algumas atas das ultimas semanas, o que
devo fazer durante o fim de semana.
Qualquer reclamacao, por favor, enviem por email para mim.
Abracos,
--
Joao Meidanis IC-UNICAMP
Institute of Computing Av. Albert Einstein, 1251
University of Campinas, Brazil 13083-852, Campinas, Sao Paulo
http://www.ic.unicamp.br/~meidanis Brazil
Apos a correcao da prova de ontem, as notas ficaram como estao la' no
site. Falta ainda eu corrigir algumas atas das ultimas semanas, o que
devo fazer durante o fim de semana.
Qualquer reclamacao, por favor, enviem por email para mim.
Abracos,
--
Joao Meidanis IC-UNICAMP
Institute of Computing Av. Albert Einstein, 1251
University of Campinas, Brazil 13083-852, Campinas, Sao Paulo
http://www.ic.unicamp.br/~meidanis Brazil
Lucas Oliveira
Jun 29, 2012, 10:51:20 AM6/29/12
to mo405_...@googlegroups.com
Professor, segue abaixo algumas possíveis alterações no gabarito da PG2.
Fiz breves comentários que não estão completos, mas mostram por onde eu conclui a resposta.
===================
Questão 58 - Resposta C.
Considere que ao removermos vértices do grafo G v H ainda existe pelo menos um vértice original de G e outro original de H.
No grafo resultante, sempre existe uma aresta que liga dois vértices que originalmente são de grafos diferentes.
Se dois vértices são originais de um mesmo grafo, também existe um vértice do outro grafo que conecta este dois vértices.
Isso mostra que se houver ao menos um vértice original de cada grafo, este é conexo.
Portanto, só podem existir vértices de apenas um dos grafos.
Logo, para se ter duas componentes em G v H é necessário remover todos os vértices de H ( ou G ) mais um conjunto separador de G ( ou H ).
===================
Questão 72 - Resposta C.
Considere o C4 com vértices rotulados com as letras a,b,c,d, sendo que esta é a ordem deles no ciclo.
Se o algoritmo guloso de coloração receber este grafo e a ordem dos vértices dada como entrada for a,c,b,d será obtida uma 3-coloração para o ciclo par.
Quanto a opção D. Seja X um conjunto independente máximo.
Existem w-1 vértices do grafo que não estão em X. ( n - (1 + n - w) )
Dê uma cor diferente para cada vértice que não está em X, e mais uma outra cor para todos vértices em X.
Fazendo isso conseguimos uma w-coloração própria para o grafo.
===========================
Questão 102 - Respostas C, D ou E.
Todas as quatro afirmações estão corretas.
Falta dizer se é para considerar as afirmações verdadeiras ou falsas!
Se considerarmos as verdadeiras, por falta dos advérbios "apenas" ou "somente", as opções C e D estão corretas.
Considerando as falsas, a opção E está correta.
====================
Questão 107 - Resposta D.
As opções A,B,C exibem uma ordem que se invertida é uma ordem de eliminação simplicial.
Então o grafo é cordal.
Já a resposta D, se invertida, não é uma ordem de eliminação simplicial.
Por isso, ela não poderia ser obtida pelo o algoritmo MCS.
Fiz breves comentários que não estão completos, mas mostram por onde eu conclui a resposta.
===================
Questão 58 - Resposta C.
Considere que ao removermos vértices do grafo G v H ainda existe pelo menos um vértice original de G e outro original de H.
No grafo resultante, sempre existe uma aresta que liga dois vértices que originalmente são de grafos diferentes.
Se dois vértices são originais de um mesmo grafo, também existe um vértice do outro grafo que conecta este dois vértices.
Isso mostra que se houver ao menos um vértice original de cada grafo, este é conexo.
Portanto, só podem existir vértices de apenas um dos grafos.
Logo, para se ter duas componentes em G v H é necessário remover todos os vértices de H ( ou G ) mais um conjunto separador de G ( ou H ).
===================
Questão 72 - Resposta C.
Considere o C4 com vértices rotulados com as letras a,b,c,d, sendo que esta é a ordem deles no ciclo.
Se o algoritmo guloso de coloração receber este grafo e a ordem dos vértices dada como entrada for a,c,b,d será obtida uma 3-coloração para o ciclo par.
Quanto a opção D. Seja X um conjunto independente máximo.
Existem w-1 vértices do grafo que não estão em X. ( n - (1 + n - w) )
Dê uma cor diferente para cada vértice que não está em X, e mais uma outra cor para todos vértices em X.
Fazendo isso conseguimos uma w-coloração própria para o grafo.
===========================
Questão 102 - Respostas C, D ou E.
Todas as quatro afirmações estão corretas.
Falta dizer se é para considerar as afirmações verdadeiras ou falsas!
Se considerarmos as verdadeiras, por falta dos advérbios "apenas" ou "somente", as opções C e D estão corretas.
Considerando as falsas, a opção E está correta.
====================
Questão 107 - Resposta D.
As opções A,B,C exibem uma ordem que se invertida é uma ordem de eliminação simplicial.
Então o grafo é cordal.
Já a resposta D, se invertida, não é uma ordem de eliminação simplicial.
Por isso, ela não poderia ser obtida pelo o algoritmo MCS.
Joao Meidanis
Jun 29, 2012, 7:47:49 PM6/29/12
to mo405
Suas palavras sao cheias de sabedoria, colega Lucas. Vou considera-las
atentamente apos corrigir as atas faltantes.
--Joao
atentamente apos corrigir as atas faltantes.
--Joao
Joao Meidanis
Jul 1, 2012, 8:37:47 AM7/1/12
to mo405_...@googlegroups.com
Caro Colega Lucas,
Analizei atentamente seus comentarios, e conclui' que voce tem razao em
todos eles. Modifiquei a planilha da prova de acordo, e tambem a planilha
de notas.
Obrigado por sua atencao e dedicacao.
--Joao
On Fri, 29 Jun 2012, Lucas Oliveira wrote:
Analizei atentamente seus comentarios, e conclui' que voce tem razao em
todos eles. Modifiquei a planilha da prova de acordo, e tambem a planilha
de notas.
Obrigado por sua atencao e dedicacao.
--Joao
On Fri, 29 Jun 2012, Lucas Oliveira wrote:
Reply all
Reply to author
Forward
0 new messages