| Autor |
Mensaje |
Paloma
Nivel 3
Registrado: 09 Jul 2009
Mensajes: 34
Carrera: Electrónica
|
|
Buenasss! etaba haciendo la guia d grafos..
ejercicio 14: analice si los siguientes grafos y digrafos son eulerianos. en caso afirmativo halle el camino o el circuito d euler correspondiente. en caso negativo justifiq.
b)
1----------------2
- ----------------
---------------
- ------4------------3
----------------
- ----------------
5------------6
(es un grafo , los numeros representan los vertices, y las lineas rojas son las aristas con algo d imaginacion  ahhh lo tuve q dibujar por q no pude adjuntar el .doc)
bueno para mi es un camino de euler (camino que no repite aristas), ya q
no repite aristas..... como dberia escribir el camino hallado????????
segun yo sigue est orden el camino (3,4,2,1,6,5,1). alguna ayuda? gracias!
|
|
|
|
_________________
Great people talk about ideas,
Average people talk about things,
Small people talk about .... other people
La ignorancia es la noche de la mente, pero una noche sin luna ni estrellas
|
|
 |
    |
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
| Por ahí es una gansada lo que digo pero bue.... no había un teorema que decía algo como que si todos los vértices tienen grado par excepto uno o dos existía un camino euleriano o algo así???
|
|
|
|
|
|
   |
  |
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
El teorema dice si tiene dos vertices de grado impar existe un CAMINO eureliano y si no tiene ningun vertice de grado impar existe un CIRCUITO eureliano.
Para armar el camino lo poder hacer a tu placer mientras respetes q solo pases una vez por cada arista, t paras en un vertice y paseas.
En caso de q tenga dos vertices con grado impar empesa el camino siempre por uno de ellos y procurá terminar en el otro.
El ejercicio q planteas tiene dos vertices impares y el resto par por lo q existe un camino eureliano, el camino q planteas vos me parece q esta mal (3,4,2,1,6,5,1) no entiendo por cual de las aristas llegas de 1 a 6 ya q tendrias q pasar por 4 o por 5. El camino q plantie yo fue el siguiente
me paro en v1 y paseo entonces me queda: v1 v2 v4 v6 v5 v1 v3 de esa forma pasas una sola vez por cada arista.
espero q sirva si esta mal lo q digo q alguien corrija. saludos
|
|
|
|
|
|
| |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
ese es el teo q decía  con lo que dice paloma de como demostrar si el grafo es euleriano ..etc... diciendo que tiene dos vertices de grado impar y el resto par alcanza supongo.... no te pedía ningún camino ...
|
|
|
|
|
|
| |
|
|
MakeSurf
Nivel 4
Registrado: 19 Feb 2009
Mensajes: 97
Carrera: Informática
|
|
Si pide camino, el ejercicio dice demostrar si tiene un camino o circuito euleriano,( para eso usas el teorema ), en caso afirmativo halle un camino o circuito euleriano, q es lo q pregunta paloma:
como dberia escribir el camino hallado????????
segun yo sigue est orden el camino (3,4,2,1,6,5,1). alguna ayuda?
Asi q la respuesta q di es correcta, mas halla del teorema.
|
|
|
|
|
|
| |
|
|
moonlight
Nivel 4
Edad: 36
Registrado: 07 Nov 2006
Mensajes: 61
Carrera: Informática
|
|
Alguien sabe cómo hacer las demostraciones de los ejercicios 8 y 11?
 "Demuestre que en todo grafo simple de n vértices siempre existe al menos un par de vértices con igual grado (Ayuda: considere el rango de valores que pueden tomar los grados de los vértices)"
11) "Demuestre que, dado un grafo simple G, o bien es conexo o bien lo es su complemento."
|
|
|
|
|
|
  |
|
|
SaaS
Nivel 7
Edad: 34
Registrado: 17 Dic 2008
Mensajes: 310
Ubicación: San Martín
Carrera: Informática
|
|
te doy una mano con el 11...
11) "Demuestre que, dado un grafo simple G, o bien es conexo o bien lo es su complemento."
si G es conexo es conexo y punto...
si G=(V,A) NO es conexo y separemos V en dos partes... V1 formado por los vértices tales que existe un camino con un vértice v aleatorio y V2 los vértices tales que no existe un camino entre ellos y v...
el complemento de G tendrá las aristas que conecten a los vértices de V2 con v y con todos los vértices de V1 por lo tanto existe un camino entre todo par vértices de G complemento por lo tanto G complemento es conexo...
el de los vértices de igual grado no se me ocurre nada por ahora... si se me ocurre algo actualizo...
|
|
|
|
|
|
| |
|
|
moonlight
Nivel 4
Edad: 36
Registrado: 07 Nov 2006
Mensajes: 61
Carrera: Informática
|
|
| Gracias por la respuesta!
|
|
|
|
|
|
| |
|
|
Pipa
Nivel 0
Edad: 35
Registrado: 17 Ene 2008
Mensajes: 1
Ubicación: Acassuso
|
|
| moonlight escribió:
|
Alguien sabe cómo hacer las demostraciones de los ejercicios 8 y 11?
"Demuestre que en todo grafo simple de n vértices siempre existe al menos un par de vértices con igual grado (Ayuda: considere el rango de valores que pueden tomar los grados de los vértices)"
|
Por si a alguno le sirve, para el ejercicio 8 hay que hacer 2 cosas:
1) El grado de cada vértice en un grafo simple está entre 0 y n-1 (n es la cantidad de vértices).
2) Hacer la demostración utilizando el absurdo, como en la guía 1. Usar:
Hipótesis: Tengo un grafo simple de n vértices
Tesis: Existe al menos un par de vértices con igual grado
Entonces haces hipótesis y NO tesis (o sea, decis que todos los vértices tienen distinto grado).
Vas a ver que llegas a un absurdo.
Ayudita por si no pueden arrancar:
Pones g(V1) = 0
g(V2) = 1
g(V3) = 2
...
g(Vn) = n-1
O sea que el vértice Vn es adyacente a todos los demas vértices, pero el vértice V1 está aislado...absurdo blablabla conclusión existe al menos un par de vértices que tienen igual grado.
Espero haber ayudado a alguien.
|
|
|
|
|
|
 |
|
|
Philipos
Nivel 3
Edad: 35
Registrado: 25 May 2008
Mensajes: 43
Ubicación: Cap Fed
Carrera: Informática
|
|
| Pipa escribió:
|
| moonlight escribió:
|
Alguien sabe cómo hacer las demostraciones de los ejercicios 8 y 11?
"Demuestre que en todo grafo simple de n vértices siempre existe al menos un par de vértices con igual grado (Ayuda: considere el rango de valores que pueden tomar los grados de los vértices)"
|
Por si a alguno le sirve, para el ejercicio 8 hay que hacer 2 cosas:
1) El grado de cada vértice en un grafo simple está entre 0 y n-1 (n es la cantidad de vértices).
2) Hacer la demostración utilizando el absurdo, como en la guía 1. Usar:
Hipótesis: Tengo un grafo simple de n vértices
Tesis: Existe al menos un par de vértices con igual grado
Entonces haces hipótesis y NO tesis (o sea, decis que todos los vértices tienen distinto grado).
Vas a ver que llegas a un absurdo.
Ayudita por si no pueden arrancar:
Pones g(V1) = 0
g(V2) = 1
g(V3) = 2
...
g(Vn) = n-1
O sea que el vértice Vn es adyacente a todos los demas vértices, pero el vértice V1 está aislado...absurdo blablabla conclusión existe al menos un par de vértices que tienen igual grado.
Espero haber ayudado a alguien.
|
Me ayudaste, gracias!!
|
|
|
|
|
|
 |
 |
|
|
|
