Questões da Prova

Questões da Prova

por Hamilton Fernandes de Moraes Junior -
Número de respostas: 6
OLa pessoal.
Em relação a questão 2 da prova (É verdade que o grafo do bispo txt é bipartido?)
O professor ja colocou uma resposta no site, mas eu fiquei com uma duvida em relação a resposta.
Em relação ao grafo 2x2:
X
 X
X X

Nesse caso para que um grafo seja bipartido, não pode existir adjacencias entre os vertices de um mesmo conjunto(nesse exemplo o conjunto dos vértices vermelhos poderia ser chamado de U) e o conjunto dos vertices pretos poderia ser chamado de W.
Mas nesse grafo, os vertices vermelhos são adjacentes. Não existe um vertice em U(vermelho) com a ponta da aresta em W(preto). Pois o bispo só anda na diagonal. Se ele esta na casa vermelha, só poderá andar nas casas vermelhas. O mesmo vale para o bispo que ficaria na casa preta.
Ao meu ver esse grafo seria bipartido. O que vocês acham?
Em resposta à Hamilton Fernandes de Moraes Junior

Re: Questões da Prova

por Tales Pinheiro de Andrade -
Foi isso que ele falou na resposta dele. Apenas uma observação. Nesse caso, teriamos 2 componentes, cada uma com um vértice vermelho e um preto. Assim, o bispo vai de um vértice preto em U para um vértice preto em W (idem para vermelho).
Em resposta à Tales Pinheiro de Andrade

Re: Questões da Prova

por Hamilton Fernandes de Moraes Junior -
Eu acabei trocando o que eu queria dizer no final da ultima mensagem. OAo meu ver o grafo do bispo não é bipartido.

Na explicação em aula, uma das dicas dadas foi que pintassemos os vertices, de modo que houvesse adjacencia entre vertices de cores diferentes. O que eu entendi é que, nesse caso, a cor preta seria do grupo U e a cor vermelha do grupo W. Cores iguais em um mesmo conjunto.

NA sala de aula, quando resolveu-se o exemplo do grafo do cavalo(dizer se é bipartido), a demonstração dada foi que de acordo com o movimento do cavalo, ele pulava de uma casa branca para uma preta e vice versa. Não acontecia do cavalo pular de uma casa preta para uma preta por exemplo.

E no caso do bispo, o bispo só se movimenta em casas da mesma cor.

Agora se a resposta da questão do bispo for aquela mesma, então não podemos considerar a questão das cores como foi falado em sala.

Quero entender direito para não cometer o mesmo erro na próxima prova.

sorriso
Em resposta à Hamilton Fernandes de Moraes Junior

Re: Questões da Prova

por Gabriel R. C. Peixoto -
> Na explicação em aula, uma das dicas dadas foi que pintassemos os vertices, de modo que houvesse adjacencia entre vertices de cores diferentes. O que eu entendi é que, nesse caso, a cor preta seria do grupo U e a cor vermelha do grupo W. Cores iguais em um mesmo conjunto.

Você tem que tentar "pintar" vértices adjacentes de cores diferentes. Casas que estejam na mesma diagonal são adjacentes no grafo do bispo, então você tem que tentar pinta-las de cores diferentes.

Não há nenhuma razão para você seguir as cores das casas do tabuleiro correspondente. Vocês fizeram isso no grafo do cavalo porque era conveniente.
Em resposta à Gabriel R. C. Peixoto

Re: Questões da Prova

por Hamilton Fernandes de Moraes Junior -
Eu pensei nessa questão sim, de pintar casas adjacentes de cores diferentes.

Mas como a questão falava do tabuleiro de xadrex então eu respeitei as cores do tabuleiro e o movimento do bispo(que só pode se movimentar em casas da mesma cor. Pois se podemos mudar as cores do tabuleiro e movimentar o bispo em cores diferentes, poderiamos fazer o mesmo no grafo do cavalo.

Bem, de qualquer forma ficarei mais atento nas próximas questões.
Em resposta à Hamilton Fernandes de Moraes Junior

Re: Questões da Prova

por Henrique Morimitsu -
O grafo é bipartido. O caso é que os conjuntos U e W que você escolheu não dão a bipartição. Suponha que o tabuleiro que você desenhou acima seja representado assim:
1 2
3 4
Você definiu U={2, 3} e W={1, 4}. Mas como 2 e 3, bem como 1 e 4 são adjacentes, isso não é uma bipartição. Para obter a bipartição correta, como o Tales falou, você teria que escolher U={1, 3} e W={2, 4}. Neste caso não existem arestas entre os vértices do mesmo conjunto e é possível colorir os vertices de U de uma cor e os de W de outra e não haverão vizinhos com a mesma cor.

Note que um grafo é bipartido se existe ALGUMA bipartição U e W, cujos vértices de um mesmo grupo não tem arestas entre si, e não que PARA QUAISQUER U e W vale a propriedade.

O caso que você mencionou de usar as cores das casas do tabuleiro para mostrar a bipartição do grafo do cavalo é um caso específico que lhe apresenta diretamente como pintar os vértices de 2 cores e obter a bipartição para aquele problema em especial, mas você tem que se lembrar que você está trabalhando com grafos, e não com um tabuleiro. Por isso, o fato do tabuleiro possuir cores iguais nas diagonais não quer dizer que o grafo do bispo deve ser também pintado com cores iguais nas diagonais. A bipartição pode ser dada por quaisquer dois subconjunto dos vértices e, portanto, você pode escolher pintar os vértices na horizontal ou vertical também no caso do seu desenho e, assim, obter a bipartição correta.

Espero ter ajudado.

abraços