Ola,
hoje me perguntaram algo na monitoria que eu respondi sem pensar devidamente, e acabei falando uma tremenda besteira.
Como haviam algumas pessoas junto, então vou postar aqui em vez de mandar emails individuais e correr o risco de esquecer de alguém.
Eu concordei que se um grafo tem um vértice de articulação, então ele tem uma ponte. Essa propriedade é falsa. Tome como contra-exemplo um grafo G = (V, E), onde:
V = {a, b, c, d, e}, E = {ab, ac, bc, ad, ae, de}.
a é um vértice de articulação nesse grafo e ele não tem nenhuma ponte.
Desculpem pela engano.
Abraços,
Gabriel
Em resposta à Gabriel R. C. Peixoto
Re: Correção sobre dúvida na monitoria
por Lucas Piva Rocha Corrêa -
Acho que é interessante comentar que a confusão provavelmente veio de que o inverso parece ser verdade: se um grafo conexo com mais de 2 vértices possui uma ponte, então ele tem um vértice de articulação.
Pequena demonstração: Seja uv a ponte. Como o grafo é conexo e tem outro vértice além de u e v, pelo menos um de u ou v possuem um vizinho. Removendo esse vértice, quebramos o grafo em pelo menos duas componentes, pois uv era uma ponte (não existe outro caminho do vizinho do vértice removido ao outro vértice da ponte).
Acho que está certo, mas se eu estiver falando besteira, por favor me corrijam.
Pequena demonstração: Seja uv a ponte. Como o grafo é conexo e tem outro vértice além de u e v, pelo menos um de u ou v possuem um vizinho. Removendo esse vértice, quebramos o grafo em pelo menos duas componentes, pois uv era uma ponte (não existe outro caminho do vizinho do vértice removido ao outro vértice da ponte).
Acho que está certo, mas se eu estiver falando besteira, por favor me corrijam.
Obrigado Gabriel e Lucas pelos esclarecimentos.
Porém, no que se refere à questão 26.14, sobre coloração de arestas, o grafo G tem que ser r-regular (r>=1). O exemplo de grafo que você deu realmente não possui uma ponte, mas também não é r-regular. Ainda não consegui um contra-exemplo utilizando essa propriedade, a menos que tivesse uma ponte. Caso alguém tenha conseguido, poderia nos ajudar? Obrigado.
Porém, no que se refere à questão 26.14, sobre coloração de arestas, o grafo G tem que ser r-regular (r>=1). O exemplo de grafo que você deu realmente não possui uma ponte, mas também não é r-regular. Ainda não consegui um contra-exemplo utilizando essa propriedade, a menos que tivesse uma ponte. Caso alguém tenha conseguido, poderia nos ajudar? Obrigado.
Regularidade não ajuda muito. Tome esse grafo 4-regular como exemplo:
G = (V, E)
V = {a, b, c, d, e, d, g, h, i, j, k}
E = {ab, ac, ad, ae, bc, bd, be, cd, ce, df, ef, fg, fh, gi, gj, gk, hi, hj, hk, ij, ik, jk}
(espero não ter esquecido de nenhuma aresta ao lista-las).
Talvez seja verdade que se um grafo tem um vértice de articulação de grau ímpar, então ele tem pelo menos uma ponte. (vou pensar um pouco melhor)
G = (V, E)
V = {a, b, c, d, e, d, g, h, i, j, k}
E = {ab, ac, ad, ae, bc, bd, be, cd, ce, df, ef, fg, fh, gi, gj, gk, hi, hj, hk, ij, ik, jk}
(espero não ter esquecido de nenhuma aresta ao lista-las).
Talvez seja verdade que se um grafo tem um vértice de articulação de grau ímpar, então ele tem pelo menos uma ponte. (vou pensar um pouco melhor)
Em resposta à Gabriel R. C. Peixoto
Re: Correção sobre dúvida na monitoria
por Gabriel R. C. Peixoto -
"Talvez seja verdade que se um grafo tem um vértice de articulação de grau ímpar, então ele tem pelo menos uma ponte. (vou pensar um pouco melhor)"
Isso nao e verdade. Mas os contra-exemplos que eu consegui desenhar sao meio grandes.
Isso nao e verdade. Mas os contra-exemplos que eu consegui desenhar sao meio grandes.
Eis um grafo 4-regular com um vértice de articulação, mas sem pontes:
Ok Murilo e Gabriel.
Muito obrigado!
Muito obrigado!
Bom exemplo.