17/02/2020, 18:45:37 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Fuertemente conexo  (Leído 109 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« : 08/12/2019, 23:17:01 »

Demuestre la siguiente afirmacion o encuentre un contraejemplo. Sea [texx]G[/texx] un grafo y [texx]D[/texx] una orientacion de [texx]G.[/texx] Si [texx]D[/texx] es fuertemente conexo, entonces [texx]G[/texx] no tiene puentes.
En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.967


Ver Perfil
« Respuesta #1 : 09/12/2019, 06:52:50 »

Hola

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

Es verdadero.

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

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

Saludos.
En línea
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« Respuesta #2 : 09/12/2019, 23:56:25 »

Hola

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

Es verdadero.

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

Sin embargo por ser el grafo fuertemente conexo debe de haber un camino [texx]v\to u[/texx] que una ambos vértices, luego incluso retirando la arista [texx]u\to v[/texx] 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 [texx]D[/texx] una orientación fuertemente conexa de [texx]G[/texx]. Por contradicción. Supongamos que existe [texx]e=xy\in E(G)[/texx] puente. Como [texx]D[/texx] es orientacion, entonces[texx] \forall u,v\in V(G): (u,v) \veebar (v,u)\in A(D).[/texx] Supongamos sin perdida de generalidad que [texx]\exists a=(x,y)\in A(D).[/texx] Como [texx]e[/texx] es puente en [texx]G[/texx], [texx]a[/texx] es puente en [texx]D[/texx]. Luego, necesariamente no existe [texx]P_{yx}[/texx] tal que [texx]y-x[/texx] es un camino en [texx]D[/texx]. De lo contrario, [texx]C: (x,y)P_{yx}[/texx] es un ciclo en [texx]D[/texx], lo que implica que [texx]a[/texx] no es puente. En resumen, como no existe [texx]P_{yx}, y-x[/texx] camino en [texx]D[/texx], entonces [texx]D[/texx] no es fuertemente conexo, contradicción.

¿Esta bien redactado?
En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.967


Ver Perfil
« Respuesta #3 : 10/12/2019, 04:51:02 »

Hola

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

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

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.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!