| Autor |
Mensaje |
MarianAAAJ
Nivel 7
Edad: 35
Registrado: 14 Ene 2009
Mensajes: 437
Carrera: Informática
|
|
Tengo q demostrar lo siguente:
1)Si existe una arista a0 que pertenece a todos los árboles generadores de G, entonces en el grafo G*, obtenido de G quitando solo la arista a0, no es conexo.
2) Probar que si un grafo tiene un único árbol generador entonces el grafo es un árbol.
Alguna idea de como demostrar estos dos puntos?
|
|
|
|
|
|
   |
    |
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
A mí con Discreta me pasa que nunca supe qué los satisfacía como demostración válida... el final lo aprobé explicando con palabras el razonamiento que unía las dos sentencias, pero no sé si eso es válido.
De la primera, si una arista está en todos los árboles generadores, entonces tiene que ser una arista de corte. ¿Por qué tiene que ser arista de corte?, porque si hubiera otra forma de unir los nodos que conecta, no pertenecería a todos los árboles generadores. Luego, si es arista de corte, si la elimino, voy a tener un grafo no conexo.
La segunda usa el mismo concepto de la primera. Si tiene un único árbol generador es porque todas sus aristas tienen que ser aristas de corte (si se obvia el punto anterior, puede plantearse como que todos los puntos son puntos de articulación). Ergo, es un grafo acíclico (acá se puede encarar desde el punto de vista de la conectividad).
|
|
|
|
_________________
 ![[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]](images/latex/d678cf273c99d2546c259db3422b3d968b184721_0.png "[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]") ![[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]](images/latex/1e6580e1ed9e054ddefd65c0551c670c44f57f38_0.png "[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]")
|
|
  |
 |
|
MarianAAAJ
Nivel 7
Edad: 35
Registrado: 14 Ene 2009
Mensajes: 437
Carrera: Informática
|
|
Yo lo que puse fue:
1) Sea a0, la arista que pertenece a todos los árboles generadores de G, entonces dicha arista será la única que una un par de vértices del grafo G, es por eso que si se elimina dicha arista del grafo no habrá ninguna arista que una ese par de vértices, haciendo que G sea un grafo no conexo.
2) Si G no es árbol => G tiene ningún árbol generador o más de uno.
Si G no es árbol, G no es aciclico o no es conexo.
Si G no es conexo, no tendrá ningún árbol generador, ya que para que haya un árbol generador T, T tiene que ser árbol (Y para ser árbol tiene que ser conexo y aciclico) además de tener los mismos vértices y un conjunto de las aristas de G, y como entre dos vértices de G no hay una trayectoria posible (Por ser G, no conexo), T no puede ser árbol, por ende G no puede tener un árbol generador.
Si G no es aciclico, puede haber más de un árbol generador ya que hay más de un camino simple que una un par de vértices.
Está bien esa demostración?
|
|
|
|
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
|
|
[ Tiempo: 0.4148s ][ Pedidos: 20 (0.3503s) ] |
