18 Grafos aresta-biconexos

18 Grafos aresta-biconexos

por Alexandre Harano -
Número de respostas: 6
Olá a todos.

Professor, estive lendo a teoria introduzida no capítulo 18 - página 47 - das notas de aulas e acredito que existe um trecho que precisa ser modificado.

Vejamos dois trechos do texto:
  • 'Um grafo é aresta-biconexo (= edge-biconnected) se for conexo e não tiver pontes (veja seção 9). Em outras palavras, um grafo G é aresta-biconexo se |nabla(N)| >= 2 para toda parte não-vazia e própria de Vg.'
  • 'Para evitar discussões inúteis, usaremos a expressão G é "aresta-biconexo" somente se G é um grafo com 2 ou mais vértices.'
Mas um grafo com 2 vértices não seria possível aplicar o primeiro fato, a menos que pudessem exisitr arestas "paralelas" entre dois vértices adjacentes.

Até mais,
Alexandre
Em resposta à Alexandre Harano

Re: 18 Grafos aresta-biconexos

por André Gomes -
Realmente, pra definição fazer sentido, o mínimo necessário seriam 3 vértices, certo?
Em resposta à André Gomes

Re: 18 Grafos aresta-biconexos

por Paulo Feofiloff -

> * 'Um grafo é aresta-biconexo 
> se for conexo e não tiver pontes
> Em outras palavras, um grafo G é aresta-
> biconexo se |nabla(N)| >= 2 para toda parte
> não-vazia e própria de Vg.'

VG

> * 'Para evitar discussões inúteis, usaremos
> a expressão G é "aresta-biconexo" somente
> se G é um grafo com 2 ou mais vértices.'

> Mas um grafo com 2 vértices não seria possível
> aplicar o primeiro fato, a menos que pudessem
> exisitr arestas "paralelas" entre dois vértices
> adjacentes.

Nossos grafos não têm arestas paralelas.

Minha definição funciona mesmo para grafos
com apenas 1 ou 2 vértices.
Mas eu não quero entrar em conflito com
alguns livros que não consideram aresta-biconexos
grafos com 2 ou menos vértices.

Em resposta à Paulo Feofiloff

Re: 18 Grafos aresta-biconexos

por Alexandre Harano -
  • 'Um grafo é aresta-biconexo (= edge-biconnected) se for conexo e não tiver pontes (veja seção 9). Em outras palavras, um grafo G é aresta-biconexo se |nabla(N)| >= 2 para toda parte não-vazia e própria de VG.'

> Minha definição funciona mesmo para grafos
> com apenas 1 ou 2 vértices.
> Mas eu não quero entrar em conflito com
> alguns livros que não consideram aresta-biconexos
> grafos com 2 ou menos vértices.

Como a definição do senhor funciona para grafos de 2 vértices que são 'conexos e não tiverem pontes'?

G = { VG={a, b}, EG={ab} }

No caso de um grafo G conexo e n(G) = 2, o grafo G é conexo porém existe uma ponte, então não entendo a afirmação do senhor em relação a definição do senhor funcionar mesmo para grafos com 2 vértices.
Em resposta à Alexandre Harano

Re: 18 Grafos aresta-biconexos

por Paulo Feofiloff -

> G = { VG={a, b}, EG={ab} }

(Notação errada.)

> No caso de um grafo G conexo e n(G) = 2, o
> grafo G é conexo porém existe uma ponte, então
> não entendo a afirmação do senhor em relação a
> definição do senhor funcionar mesmo para grafos
> com 2 vértices.

Nenhum dos grafos que têm 2 vértices é
aresta-biconexo.

De modo mais geral, dado qualquer número n,
alguns (possivelmente nenhum) dos grafos que
têm n vértices são aresta-biconexos enquanto
outros não são aresta-biconexos.



Em resposta à Paulo Feofiloff

Re: 18 Grafos aresta-biconexos

por Alexandre Harano -
> Nenhum dos grafos que têm 2 vértices é
> aresta-biconexo.

Justamente.

O motivo da dessa discussão toda é para o senhor modificar o seguinte trecho das notas de aula (leia a expressão sublinhada):

'Para evitar discussões inúteis sobre grafos pequenos, usaremos a expressão “G é
aresta-biconexo” somente se G é um grafo com 2 ou mais vértices.'
Em resposta à Alexandre Harano

Re: 18 Grafos aresta-biconexos

por Paulo Feofiloff -

> Justamente.

> O motivo da dessa discussão toda é para o
> senhor modificar o seguinte trecho das notas
> de aula (leia a expressão sublinhada):

> Para evitar discussões inúteis sobre grafos
> pequenos, usaremos a expressão “G é
> aresta-biconexo” somente se G é um grafo com
> 2 ou mais vértices.'

Como eu expliquei na mensagem anterior,
não há nada de errado com a observação!

(Mas eu fiz alterações por outros motivos.)