| Autor |
Mensaje |
marfer
Nivel 1
Registrado: 29 Ago 2010
Mensajes: 4
|
|
Necesito una demostracion clara de la siguiente implicacion:
"G es conexo y aciclico" -> " La cantidad de aristas = cantidad de vertices - 1 "
Muchas Gracias.
|
|
|
|
|
|
| |
    |
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
¿Por inducción completa no sale?
Es tema de la materia, vió...
|
|
|
|
_________________
 ![[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]")
|
|
   |
 |
|
Ajax08
Nivel 5
Registrado: 30 Dic 2008
Mensajes: 168
|
|
Si, es por inducción, el planteo seria asi:
G conexo y G aciclico y |V| = n entonces |A| = |V| - 1
Hace con esta proposición la inducción.
|
|
|
|
|
|
| |
|
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
Mmm... en realidad yo me tiraría a demostrar que independientemente del número de aristas que tengas cuando |V| = n, no hay chances ni de quitar ni de agregar una nueva arista, y que si agregás un nuevo vértice, para que sea conexo y acíclico necesitás agregar una y solo una arista más. O sea, como paso de la inducción, demostraría que si n => a, n + 1 => a + 1.
Lo de que |A| = |V| - 1, lo despejaría después del caso base.
Es muy similar el planteo, pero no metés la condición que tenés que demostrar como hipótesis.
|
|
|
|
_________________
|
|
| |
|
|
marfer
Nivel 1
Registrado: 29 Ago 2010
Mensajes: 4
|
|
Pense en resolverlo por induccion pero no se si lo hago de forma correcta, aca les copio lo que hice. Gracias
Paso base: trivial
Paso inductivo:
(|V|=h --> |A| = h + 1) --> (|V| = h + 1 --> |A| = h)
Sea v° un vertive de V talque su grado de incidencia es 1 y a° la arista correspondiente.
Sea G = (V,A) y sea G° = (V°,A°) = (V-{v°},A-{a°})
entonces |V°| = |V| - 1 y |A°| = |A| - 1
si |V|= h + 1 entonces |V°| = h implica por hipotesis que |A°| = h - 1 = |A| - 1 entonces |A| = h y quedaria demostrada la implicacion.
|
|
|
|
|
|
| |
|
|
marfer
Nivel 1
Registrado: 29 Ago 2010
Mensajes: 4
|
|
Escribi mal el enunciado abierto, es este
(|V|=h --> |A| = h - 1) --> (|V| = h + 1 --> |A| = h)
|
|
|
|
|
|
| |
|
|
Lautaz
Nivel 8
Registrado: 05 Sep 2008
Mensajes: 550
Carrera: Informática y Sistemas
|
|
| Consulta sobre Euler: si un grafo tiene un circuito de Euler también tiene un camino o son excluyentes?
|
|
|
|
_________________
61.7
Death ... By exile
|
|
| |
|
|
GREgO
Nivel 8
Registrado: 21 Abr 2009
Mensajes: 771
Ubicación: New Belsen
Carrera: Electrónica
|
|
| Lautaz escribió:
|
|
Consulta sobre Euler: si un grafo tiene un circuito de Euler también tiene un camino o son excluyentes?
|
Tengo entendido que también tiene un camino.
- "Circuito de Euler" es un circuito que no repite aristas.
- "Camino de Euler" es un camino que no repite aristas.
Un circuito es un camino cerrado. Entonces si un grafo tiene un circuito de Euler, también tiene un camino de Euler. (Tomás todo menos una arista que lo cierre).
La recíproca no es válida.
|
|
|
|
_________________
El ser humano primero cree en Papá Noel,
Después en Dios,
Luego en la Izquierda,
Y finalmente advierte que la posta es Hermanos Bladimir
................
Ya salió la Bladimir Papel nº 3! Conseguila en el baño de tu Ugi's!
|
|
| |
 |
|
Lautaz
Nivel 8
Registrado: 05 Sep 2008
Mensajes: 550
Carrera: Informática y Sistemas
|
|
| GREgO escribió:
|
| Lautaz escribió:
|
|
Consulta sobre Euler: si un grafo tiene un circuito de Euler también tiene un camino o son excluyentes?
|
Tengo entendido que también tiene un camino.
- "Circuito de Euler" es un circuito que no repite aristas.
- "Camino de Euler" es un camino que no repite aristas.
Un circuito es un camino cerrado. Entonces si un grafo tiene un circuito de Euler, también tiene un camino de Euler. (Tomás todo menos una arista que lo cierre).
La recíproca no es válida.
|
Me parecía, muchas gracias.
|
|
|
|
|
|
| |
|
|
|
|
