Fwd: ATA 8.1.2 e 8.1.30.
8 views
Skip to first unread message
ED
Jun 16, 2012, 6:32:34 PM6/16/12
to mo405_...@googlegroups.com
Desculpe. Não vi que foi errado.
Maldito TDA.
-----Original Message-----
From: ED <edgar...@netscape.net>
To: ""\"mo405 <mo405_2012s1\"" <"mo405 <mo405_2012s1""@googlegroups.com>
Sent: Fry, Jun 15, 2012 23:16 pm
Subject: ATA 8.1.2 e 8.1.30.
From: ED <edgar...@netscape.net>
To: ""\"mo405 <mo405_2012s1\"" <"mo405 <mo405_2012s1""@googlegroups.com>
Sent: Fry, Jun 15, 2012 23:16 pm
Subject: ATA 8.1.2 e 8.1.30.
Segue ATA 8.1.2 e 8.1.30
Joao Meidanis
Jun 18, 2012, 6:58:22 AM6/18/12
to mo405
Caro Ed,
Nao esta' boa a sua ata. Vejamos.
- O enunciado da 8.1.2 esta' ok, fiel ao livro.
- Nao deixou explicito que cada professor corresponderia a um intervalo.
Suas palavras deixam entrever isto implicitamente, mas nao e' o ideal.
Seria melhor explicitamente resslatar este fato.
- "Na tentativa de construir um grafo de intervalos". Esta frase nao
esta' boa. So ha' um grafo a construir, e temos que verificar se e' de
intervalos.
- "ciclo nao cordal": linguajar estranho, nao utilizado, e so' pertinente
ao problema se for induzido. Seria melhor dizer "ciclo induzido nao
cordal". Ou, melhor ainda: "ciclo sem corda".
- "nao caracteriza um grafo de intervalos": melhor dizer, "nao pode
existir num grafo de intervalos". 'Nao caracterizar' nao e' suficiente
para nossos propositos. A palavra 'caraterizar' evoca 'se e somente se',
o que nao e' o caso.
- a figura esta' correta, mas se bem me lembro tinhamos colocado multiplas
arestas para indicar que A viu B e B viu A tambem. Ou talvez peso 2
nas arestas que vem de dois depoimentos. Ou, voce pode fazer um grafo
orientado. E' importante na investigacao, como veremos a seguir.
- voce testa as coisas removendo o depoimento inteiro de cada pessoa.
Aqui esta' o maior problema. Nao foi isso que fizemos. Analisamos aresta
por aresta. Se tirar o depoimento inteiro, como voce sugere, removendo o
depoimento de Abe ficamos com um grafo cordal, *ao contrario do que voce
diz* na ata. Abe entao seria candidato a mentiroso.
- O raciocicio correto, que voce nao fez, deveria passar pela analise de
cada aresta. Quais arestas, quando removidas, deixam um grafo de
intervalos? Nao basta ser cordal. E, dentre estas, quais as que tem
menor suporte (apenas um depoimento)? Assim chegaria a Desmond sem
ambiguidade.
- Este exercicio, portanto, esta' resolvido erroneamente.
- No outro exercicio, do menor grafo imperfeito, tambem ha' problemas
graves. Voce parece ir considerando os valores de chi=2,3,... Isto esta'
errado. Estamos procurando o menor grafo, nao o menor numero cromatico.
O certo e' ir considerando os valores de n=1,2,3,...
- Ai' voce fala em "menor grafo nao cordal de ciclo impar". O que e' um
grafo de ciclo impar?
- Por mim, apagaria tudo e comecaria de novo. Falaria que, com n=1,2,3,4,
todos os grafos sao perfeitos, por nao caber ciclo impar de tamanho maior
ou igual a 5 ou seu complemento.
- Dai' pegaria grafos de 5 vertices. Para ser imperfeito, tem que conter
C_5 (ou seu complemento, que no caso e' o proprio C_5) induzido, ou seja,
sem cordas. A unica possibilidade e' o proprio C_5.
- So' que em C_5 nao temos chi=omega. Entao nao ha' exemplo com 5
vertices.
- Passamos para 6 vertices. Tem que ter um C_5 induzido, e mais um
vertice v. Nao podemos ter arestas entre os vertices do ciclo, senao
seriam cordas. Se houver apenas uma aresta entre o ciclo e v,
continuariamos sem chi=omega. Com duas arestas entre o ciclo e v, se
forem com vertices consecutivos do ciclo, ai' sim teriamos chi=omega, e e'
o exemplo buscado: menor grafo imperfeito com chi=omega.
- Pronto, este seria o roteiro para arrumar a ata. Por favor, refaca e
mande de novo.
Sua nota sera' bem baixa, nao sei quanto ainda. Nao resolveu nenhum dos
problemas satisfatoriamente.
--Joao
--
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
Nao esta' boa a sua ata. Vejamos.
- O enunciado da 8.1.2 esta' ok, fiel ao livro.
- Nao deixou explicito que cada professor corresponderia a um intervalo.
Suas palavras deixam entrever isto implicitamente, mas nao e' o ideal.
Seria melhor explicitamente resslatar este fato.
- "Na tentativa de construir um grafo de intervalos". Esta frase nao
esta' boa. So ha' um grafo a construir, e temos que verificar se e' de
intervalos.
- "ciclo nao cordal": linguajar estranho, nao utilizado, e so' pertinente
ao problema se for induzido. Seria melhor dizer "ciclo induzido nao
cordal". Ou, melhor ainda: "ciclo sem corda".
- "nao caracteriza um grafo de intervalos": melhor dizer, "nao pode
existir num grafo de intervalos". 'Nao caracterizar' nao e' suficiente
para nossos propositos. A palavra 'caraterizar' evoca 'se e somente se',
o que nao e' o caso.
- a figura esta' correta, mas se bem me lembro tinhamos colocado multiplas
arestas para indicar que A viu B e B viu A tambem. Ou talvez peso 2
nas arestas que vem de dois depoimentos. Ou, voce pode fazer um grafo
orientado. E' importante na investigacao, como veremos a seguir.
- voce testa as coisas removendo o depoimento inteiro de cada pessoa.
Aqui esta' o maior problema. Nao foi isso que fizemos. Analisamos aresta
por aresta. Se tirar o depoimento inteiro, como voce sugere, removendo o
depoimento de Abe ficamos com um grafo cordal, *ao contrario do que voce
diz* na ata. Abe entao seria candidato a mentiroso.
- O raciocicio correto, que voce nao fez, deveria passar pela analise de
cada aresta. Quais arestas, quando removidas, deixam um grafo de
intervalos? Nao basta ser cordal. E, dentre estas, quais as que tem
menor suporte (apenas um depoimento)? Assim chegaria a Desmond sem
ambiguidade.
- Este exercicio, portanto, esta' resolvido erroneamente.
- No outro exercicio, do menor grafo imperfeito, tambem ha' problemas
graves. Voce parece ir considerando os valores de chi=2,3,... Isto esta'
errado. Estamos procurando o menor grafo, nao o menor numero cromatico.
O certo e' ir considerando os valores de n=1,2,3,...
- Ai' voce fala em "menor grafo nao cordal de ciclo impar". O que e' um
grafo de ciclo impar?
- Por mim, apagaria tudo e comecaria de novo. Falaria que, com n=1,2,3,4,
todos os grafos sao perfeitos, por nao caber ciclo impar de tamanho maior
ou igual a 5 ou seu complemento.
- Dai' pegaria grafos de 5 vertices. Para ser imperfeito, tem que conter
C_5 (ou seu complemento, que no caso e' o proprio C_5) induzido, ou seja,
sem cordas. A unica possibilidade e' o proprio C_5.
- So' que em C_5 nao temos chi=omega. Entao nao ha' exemplo com 5
vertices.
- Passamos para 6 vertices. Tem que ter um C_5 induzido, e mais um
vertice v. Nao podemos ter arestas entre os vertices do ciclo, senao
seriam cordas. Se houver apenas uma aresta entre o ciclo e v,
continuariamos sem chi=omega. Com duas arestas entre o ciclo e v, se
forem com vertices consecutivos do ciclo, ai' sim teriamos chi=omega, e e'
o exemplo buscado: menor grafo imperfeito com chi=omega.
- Pronto, este seria o roteiro para arrumar a ata. Por favor, refaca e
mande de novo.
Sua nota sera' bem baixa, nao sei quanto ainda. Nao resolveu nenhum dos
problemas satisfatoriamente.
--Joao
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
Joao Meidanis
Jun 24, 2012, 9:23:10 AM6/24/12
to mo405
Oi Ed,
Vou dar nota 6,0 (seis) para esta sua ata. Corrija, por favor.
--Joao
Vou dar nota 6,0 (seis) para esta sua ata. Corrija, por favor.
--Joao
Joao Meidanis
Jul 1, 2012, 7:18:19 AM7/1/12
to mo405_...@googlegroups.com
Obrigado, colega Ed. A primeira melhorou a ponto de eu coloca-la no site
como oficial. A segunda melhorou, mas ainda contem afirmacoes erradas.
Por exemplo, diz la' que o unico grafo com ate' 5 vertices que nao e'
cordal nem bipartido e' o casa. E o C_5? Esta ainda falta aprefeicoar.
Nao posso colocar no site como oficial.
Abracos,
--Joao
como oficial. A segunda melhorou, mas ainda contem afirmacoes erradas.
Por exemplo, diz la' que o unico grafo com ate' 5 vertices que nao e'
cordal nem bipartido e' o casa. E o C_5? Esta ainda falta aprefeicoar.
Nao posso colocar no site como oficial.
Abracos,
--Joao
Reply all
Reply to author
Forward
0 new messages