Olá a todos.
Estou com dificuldades para conseguir resolver o seguinte exercício:
E 19.33 Seja P um caminho de comprimento máximo em um grafo G. Mostre
que X(G) ≤ n(P).
Estava pensando em considerar que cada vértice do caminho P formará um conjunto estável distinto. Dessa forma, teremos P conjuntos estáveis. Estava tentando provar que qualquer outro vértice que não pertença ao caminho deve estar em pelo menos um dos P conjuntos formados. Assim, a união dos conjuntos cobrirá o conjunto de vértices de G. Mas não estou conseguindo sair daí.
Será que é por aí mesmo? Alguém poderia me dar uma dica?
Obrigado,
Pedro.
Caminho de comprimento máximo e coloração de vértices.
por Pedro Losco Takecian -
Número de respostas: 16
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Charles Martins -
Blz Pedro?
Então, eu estava tentando resolver esse problema por contradição, mas também tenho dúvidas se ele está correto. Vamos ver se ajuda...
Suponha que X(G)>n(P). Isso me diz que posso colorir os vértices de G com no mínimo n(P) + 1 cores. Suponha que eu pinte cada vértice de P com uma cor diferente e a última cor possível para colorir seja aplicada a outro vértice em G que seja vizinho, ou não, a um vértice de P. Porém, existirá um outro caminho P' tal que |P'|>|P| o que contradiz a hipótese, já que P é um caminho máximo em G. Portanto, X(G)≤n(P).
Alguém poderia verificar se está correto?
Obrigado!
Então, eu estava tentando resolver esse problema por contradição, mas também tenho dúvidas se ele está correto. Vamos ver se ajuda...
Suponha que X(G)>n(P). Isso me diz que posso colorir os vértices de G com no mínimo n(P) + 1 cores. Suponha que eu pinte cada vértice de P com uma cor diferente e a última cor possível para colorir seja aplicada a outro vértice em G que seja vizinho, ou não, a um vértice de P. Porém, existirá um outro caminho P' tal que |P'|>|P| o que contradiz a hipótese, já que P é um caminho máximo em G. Portanto, X(G)≤n(P).
Alguém poderia verificar se está correto?
Obrigado!
Em resposta à Charles Martins
Re: Caminho de comprimento máximo e coloração de vértices.
por Lucas Piva Rocha Corrêa -
Porém, existirá um outro caminho P' tal que |P'|>|P|.
Não entendi da onde vem essa implicação. Se colorirmos P com |P| cores diferentes, podemos colorir qualquer outro vértice não adjcente a algum vértice de P com a outra cor e isso não implica que existe um caminho maior que P. Na verdade, o vértice só precisa não ser adjacente às pontas de P.
Não entendi da onde vem essa implicação. Se colorirmos P com |P| cores diferentes, podemos colorir qualquer outro vértice não adjcente a algum vértice de P com a outra cor e isso não implica que existe um caminho maior que P. Na verdade, o vértice só precisa não ser adjacente às pontas de P.
Em resposta à Charles Martins
Re: Caminho de comprimento máximo e coloração de vértices.
por Paulo Feofiloff -
> Suponha que X(G)>n(P). Isso me diz que posso
> colorir os vértices de G com no mínimo
> n(P) + 1 cores.
Não. Isso me diz que NÃO posso colorir G com
n(P) cores.
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Giseli Ramos -
Pedro,
Também comecei meio que da mesma forma que você, mas usando a mesma notação. Acho que só precisa dizer que não é necessário criar novos conjuntos estáveis em G - P.
Só não usei a notação de conj estáveis. Fiz mais ou menos assim:
Colore cada um dos vértices de P com uma cor diferente. Então, no máximo, tem n(P) cores. Agora, para colorir os vértices em G - P, basta atribuir a cada vértice de G - P uma cor que foi usada em P, desde que não seja a mesma cor de algum vértice adjacente ao que estou colorindo. Então podemos concluir que n. cromático =< n(P)
Foi uma prova meio algorítmica, não sei se convenceu....
Também comecei meio que da mesma forma que você, mas usando a mesma notação. Acho que só precisa dizer que não é necessário criar novos conjuntos estáveis em G - P.
Só não usei a notação de conj estáveis. Fiz mais ou menos assim:
Colore cada um dos vértices de P com uma cor diferente. Então, no máximo, tem n(P) cores. Agora, para colorir os vértices em G - P, basta atribuir a cada vértice de G - P uma cor que foi usada em P, desde que não seja a mesma cor de algum vértice adjacente ao que estou colorindo. Então podemos concluir que n. cromático =< n(P)
Foi uma prova meio algorítmica, não sei se convenceu....
Em resposta à Giseli Ramos
Re: Caminho de comprimento máximo e coloração de vértices.
por Lucas Piva Rocha Corrêa -
Gisele,
Acredito que o caminho da prova seja algoritmico mesmo. No entanto, sua prova está incompleta, justamente porque você não prova que é possível colorir os vértices de G - P com alguma cor usada em P.
Acredito que o caminho da prova seja algoritmico mesmo. No entanto, sua prova está incompleta, justamente porque você não prova que é possível colorir os vértices de G - P com alguma cor usada em P.
Em resposta à Giseli Ramos
Re: Caminho de comprimento máximo e coloração de vértices.
por Paulo Feofiloff -
> Colore cada um dos vértices de P com uma cor
> diferente. Então, no máximo, tem n(P) cores.
> Agora, para colorir os vértices em G - P,
> basta atribuir a cada vértice de G - P uma cor
> que foi usada em P, desde que não seja a mesma
> cor de algum vértice adjacente ao que estou
> colorindo.
COMO você vai fazer isso?
Quem garante que isso é possível?
(Eu acho que não é possível...)
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Paulo Feofiloff -
Em resposta à Paulo Feofiloff
Re: Caminho de comprimento máximo e coloração de vértices.
por Pedro Losco Takecian -
Ok. Muito obrigado a todos. Vou tentar resolver usando a dica.
Abraços,
Pedro.
Abraços,
Pedro.
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Edwin Delgado H. -
Eu tentei resolver assim, mas fiquei no caminho...
E 19.33 Seja P um caminho de comprimento máximo em um grafo G. Mostre
que X(G) ≤ n(P).
Seja W uma clique máxima em G, w(G) = |W|. Seja P o caminho de comprimento máximo em G que pasa por todos os vértices de W, observe que n(P) tem pelo menos |W| vértices, isso quer dizer que w(G) <= n(P). Temos que X(G) >= w(G)., pensando...
estou no caminho correto?, está certo?
Edwin
Em resposta à Edwin Delgado H.
Re: Caminho de comprimento máximo e coloração de vértices.
por Gabriel R. C. Peixoto -
Uma observação é que o caminho de comprimento máximo não necessariamente passa por um clique máximo.
E eu também não sei concluir a partir disso não.
E eu também não sei concluir a partir disso não.
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Lucas Piva Rocha Corrêa -
Prova baseada na dica da apostila de exercícios:
Seja {X1, X2, ..., Xk} uma coloração mínima de G. Aplicamos o algoritmo de recoloração sugerido: Para todo x em X1 que não tem nenhum vizinho em X2, coloque x em X2, para todo x em X2 que não tem nenhum vizinho em X3, coloque x em X3 e assim por diante. Como a coloração inicial era mínima, nenhum conjunto fica vazio.
Agora, vamos mostrar que existe um caminho que possui um vértice em cada Xi. Pegue um caminho com ponta inicial em algum vértice v1 de X1. Necessariamente, v1 possui uma aresta para algum vértice v2 de X2, senão ele teria sido recolorido com X2. Adicione v2 ao caminho e aplique o mesmo raciocínio para v2 para adicionar um vértice de X3 ao caminho e assim por diante. Portanto, temos um caminho de comprimento k. Como esse caminho é menor ou igual ao maior caminho de G e o número cromático de G é menor ou igual ao comprimento do caminho construído, o número cromático é menor ou igual ao comprimento do maior caminho.
Seja {X1, X2, ..., Xk} uma coloração mínima de G. Aplicamos o algoritmo de recoloração sugerido: Para todo x em X1 que não tem nenhum vizinho em X2, coloque x em X2, para todo x em X2 que não tem nenhum vizinho em X3, coloque x em X3 e assim por diante. Como a coloração inicial era mínima, nenhum conjunto fica vazio.
Agora, vamos mostrar que existe um caminho que possui um vértice em cada Xi. Pegue um caminho com ponta inicial em algum vértice v1 de X1. Necessariamente, v1 possui uma aresta para algum vértice v2 de X2, senão ele teria sido recolorido com X2. Adicione v2 ao caminho e aplique o mesmo raciocínio para v2 para adicionar um vértice de X3 ao caminho e assim por diante. Portanto, temos um caminho de comprimento k. Como esse caminho é menor ou igual ao maior caminho de G e o número cromático de G é menor ou igual ao comprimento do caminho construído, o número cromático é menor ou igual ao comprimento do maior caminho.
Em resposta à Lucas Piva Rocha Corrêa
Re: Caminho de comprimento máximo e coloração de vértices.
por Paulo Feofiloff -
> Seja {X1, X2, ..., Xk} uma coloração mínima de
> G. Aplicamos o algoritmo de recoloração
> sugerido:
. . .
> Como a coloração inicial era mínima, nenhum
> conjunto fica vazio.
. . .
> Agora, vamos mostrar que existe um caminho que
> possui um vértice em cada Xi. Pegue um caminho
> com ponta inicial em algum vértice v1 de X1.
> Necessariamente, v1 possui uma aresta para
> algum vértice v2 de X2,
Humm. Isto era verdade depois do primeiro passo
da recoloração. Mas o vizinho de x1 em X2 pode
ter sido deslocado para X3 no passo seguinte...
Acho que o algoritmo de recoloração deve ser
aplicado repetidas vezes. Dizendo isso de maneira
mais sofisticada: escolha a coloração
{X1, X2, ..., Xk} de modo a maximizar a soma
1|X1| + 2|X2| + ... + k|Xk|.
Em resposta à Paulo Feofiloff
Re: Caminho de comprimento máximo e coloração de vértices.
por Lucas Piva Rocha Corrêa -
Entendi professor, obrigado pela correção.
Se eu aplicar o algoritmo até que nenhum vértice seja recolorido, a prova fica correta, certo? Pois se um vértice em v1 não tivesse vizinho em X2 ele teria sido movido na última aplicação do algoritmo e o algoritmo não teria parado. O mesmo vale para qualquer vi e Xi + 1.
Está certo?
Se eu aplicar o algoritmo até que nenhum vértice seja recolorido, a prova fica correta, certo? Pois se um vértice em v1 não tivesse vizinho em X2 ele teria sido movido na última aplicação do algoritmo e o algoritmo não teria parado. O mesmo vale para qualquer vi e Xi + 1.
Está certo?
Em resposta à Pedro Losco Takecian
Re: Caminho de comprimento máximo e coloração de vértices.
por Murilo Santos de Lima -
Eu consegui uma prova por indução em n(G) bem simples.
Se n = 1, n(P) = 1, \chi(G) = 1, então a afirmativa é válida.
Se n > 1, seja v uma ponta de P e P' um caminho de comprimento máximo em G-v. Como n(G-v) < n(G), por hipótese de indução \chi(G-v) <= n(P'). Além disso, n(P') <= n(P), logo \chi(G-v) <= n(P).
Tome uma coloração de G-v com n(P) cores. Em G, todos os vizinhos de v estão em P, senão P não teria comprimento máximo. Logo v tem no máximo n(P)-1 vizinhos e sobra ao menos uma cor para pintar v. A coloração resultante também tem n(P) cores, logo \chi(G) <= n(P).
Em resposta à Murilo Santos de Lima
Re: Caminho de comprimento máximo e coloração de vértices.
por Murilo Santos de Lima -
Agora que eu vi, a dica do professor era justamente utilizar indução em n.
Em resposta à Murilo Santos de Lima
Re: Caminho de comprimento máximo e coloração de vértices.
por Paulo Feofiloff -
> Eu consegui uma prova por indução em n(G)
> bem simples.
Boa!