Autor Tema: Fuertemente conexo

0 Usuarios y 1 Visitante están viendo este tema.

09 Diciembre, 2019, 03:17 am
Leído 659 veces

Julio_fmat

  • Héroe
  • Mensajes: 2,258
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre la siguiente afirmacion o encuentre un contraejemplo. Sea \( G \) un grafo y \( D \) una orientacion de \( G. \) Si \( D \) es fuertemente conexo, entonces \( G \) no tiene puentes.
"Haz de las Matemáticas tu pasión".

09 Diciembre, 2019, 10:52 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,763
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Demuestre la siguiente afirmacion o encuentre un contraejemplo. Sea \( G \) un grafo y \( D \) una orientación de \( G. \) Si \( D \) es fuertemente conexo, entonces \( G \) no tiene puentes.

Es verdadero.

Si \( G \) tuviese un puente entre dos vértices \( u,v \) de manera que con la orientación dada la arista va de \( u\to v \), al retirar tal arista tendríamos al menos dos componentes conexas en el grafo, una conteniendo a \( u \) y otra a \( v \).

Sin embargo por ser el grafo fuertemente conexo debe de haber un camino \( v\to u \) que una ambos vértices, luego incluso retirando la arista \( u\to v \) ambos vértices están en la misma componente conexa, lo cuál contradice la existencia de la dos componentes indicadas antes.

Saludos.

10 Diciembre, 2019, 03:56 am
Respuesta #2

Julio_fmat

  • Héroe
  • Mensajes: 2,258
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

Demuestre la siguiente afirmacion o encuentre un contraejemplo. Sea \( G \) un grafo y \( D \) una orientación de \( G. \) Si \( D \) es fuertemente conexo, entonces \( G \) no tiene puentes.

Es verdadero.

Si \( G \) tuviese un puente entre dos vértices \( u,v \) de manera que con la orientación dada la arista va de \( u\to v \), al retirar tal arista tendríamos al menos dos componentes conexas en el grafo, una conteniendo a \( u \) y otra a \( v \).

Sin embargo por ser el grafo fuertemente conexo debe de haber un camino \( v\to u \) que una ambos vértices, luego incluso retirando la arista \( u\to v \) ambos vértices están en la misma componente conexa, lo cuál contradice la existencia de la dos componentes indicadas antes.

Saludos.

Muchas Gracias, quiero saber si la siguiente demostración es correcta:

Demostración: Sea \( D \) una orientación fuertemente conexa de \( G \). Por contradicción. Supongamos que existe \( e=xy\in E(G) \) puente. Como \( D \) es orientacion, entonces\(  \forall u,v\in V(G): (u,v) \veebar (v,u)\in A(D). \) Supongamos sin perdida de generalidad que \( \exists a=(x,y)\in A(D). \) Como \( e \) es puente en \( G \), \( a \) es puente en \( D \). Luego, necesariamente no existe \( P_{yx} \) tal que \( y-x \) es un camino en \( D \). De lo contrario, \( C: (x,y)P_{yx} \) es un ciclo en \( D \), lo que implica que \( a \) no es puente. En resumen, como no existe \( P_{yx}, y-x \) camino en \( D \), entonces \( D \) no es fuertemente conexo, contradicción.

¿Esta bien redactado?
"Haz de las Matemáticas tu pasión".

10 Diciembre, 2019, 08:51 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,763
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Demostración: Sea \( D \) una orientación fuertemente conexa de \( G \). Por contradicción. Supongamos que existe \( e=xy\in E(G) \) puente. Como \( D \) es orientacion, entonces\(  \forall u,v\in V(G): (u,v) \veebar (v,u)\in A(D). \) Supongamos sin perdida de generalidad que \( \exists a=(x,y)\in A(D). \) Como \( e \) es puente en \( G \), \( a \) es puente en \( D \). Luego, necesariamente no existe \( P_{yx} \) tal que \( y-x \) es un camino en \( D \). De lo contrario, \( C: (x,y)P_{yx} \) es un ciclo en \( D \), lo que implica que \( a \) no es puente. En resumen, como no existe \( P_{yx}, y-x \) camino en \( D \), entonces \( D \) no es fuertemente conexo, contradicción.

Está bien con un matiz; no estoy seguro de a que estás llamando \( P_{yx} \); diría que te refieres a un camino con origen \( y \) e final \( x \). Pero luego escribes \( y-x \) para referirte a lo mismo. ¿No es redundante?¿qué diferencia haces entre  \( P_{yx} \) e \( y-x \)?.

Saludos.

P.D. Te puede servir de ejemplo mi respuesta para entender como se especifica de manera precisa una duda sobre lo que ha escrito otra persona.

¿Qué te hubiera parecido si te hubiese contestado: "está bien excepto en una cosa que no me queda clara", sin más?. Pues así me contestas tu muchas veces. ¿Qué reflexión haces sobre eso? Y no es una pregunta retórica; me gustaría que la contestases.