martes, 1 de junio de 2010

PUNTOS EXTRA

GRAFO CONEXO.

Un grafo es conexo si y sólo si tiene una única componente conexa.
Un grafo es conexo si existe algún camino entre todo par de vértices.
El siguiente grafo es conexo ya que de cualquier vértice se puede llegar a cualquier otro através de un camino.


Por ejemplo para llegar del vértice u a x, tengo que ir forzosamente por w, luego puedo ir por z, y después directamente a x, pero imagínense que entre "w" y "z" no hay arista, entonces para llegar de u a x, pasaría igual forzosamente por w, luego podría ir a t, luego por w al final a x.











El siguiente grafo no es conexo porque no existe ningún camino entre los vértices a y c.
Aunque como podemos apreciar en la imagen, hay todavía varios vértices que no se unen.





4 comentarios:

  1. hola eddy me parecio muy buena tu explicacion y ahora si ya le entendi :)
    nada mas te digo que tienes un error, no se si te hayas dado cuenta, donde dice que imaginemos que no hay arista entre w y z, dices que pasariamos forzosamente por w, luego t, luego otra vez por w y al final x, supongo que te confundiste en vez de w es z, porque primero se pasaria por w, luego t, luego z y por ultimo x :)

    ResponderEliminar
  2. Muy bien explicado me ayudo a entender mucho el tema solo una duda en el segundo problema que dices que no existe un camino entre a y c, no se podria ir de a-d-f-c o tendria que estar conectado a-d-b-c para poder llegar saludos espero puedas contestar mi duda..

    ResponderEliminar
  3. Creo que la sig definición también podría complementarse.
    Un grafo dirigido tal que para cualesquiera dos vértices a y b existe un camino dirigido de ida y de regreso se dice grafo fuertemente conexo.

    Tengo una duda, los aristas pueden cruzarse?? lo menciono por la última imágen.
    espero y despejes mi duda
    gracias.

    ResponderEliminar
  4. Neto Méndez:
    Asi es me equivoque, como tu dices, pasaría forzosamente por w, luego t, luego z y al final x.

    Rodolfo Aguirre:
    No se podría de ir de "a" a "c" porque no hay una arista que concecte a esos 2 grafos,pero como comentaste si estuviera conectado a-d-b-c, si se podría llegar, porque se están uniendo los 2 grafos.

    Erik Noé Villarreal Rodríguez:
    Así es las aristas pueden cruzarse porque no se mencionó que el grafo no fuera plano.

    ResponderEliminar