10 Abril, 2020, 16:18 *
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: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Problema de Teoría de Grafos!  (Leído 2723 veces)
0 Usuarios y 1 Visitante están viendo este tema.
agu004
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 9


Ver Perfil
« : 19 Marzo, 2011, 17:24 »

El problema que quiero plantear es el siguiente:

http://www.elpais.com/videos/sociedad/problema/ciudades/carreteras/elpvidsoc/20110318elpepusoc_1/Ves/

a ver si alguien lo puede resolver!!
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.832



Ver Perfil
« Respuesta #1 : 19 Marzo, 2011, 18:08 »

El problema que quiero plantear es el siguiente:

http://www.elpais.com/videos/sociedad/problema/ciudades/carreteras/elpvidsoc/20110318elpepusoc_1/Ves/

a ver si alguien lo puede resolver!!

Hola. Son 11 puntos, pero hay que volver a casa, y eso hace que tengamos que pasar por 12 puntos (11 y uno repetido) y 11 caminos o segmentos. Por otra parte existen 18 caminos o segmentos en total; luego la parte proporcional de caminos que debemos recorrer respecto del total es  [texx]18/11[/texx], que no da un número entero; no se puede, en mi opinión.

Saludos. 
En línea

Topolino
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
United States United States

Mensajes: 260


Ver Perfil
« Respuesta #2 : 20 Marzo, 2011, 05:23 »

Hola

Me gustó este problema. Creo que no tiene solución, es decir creo que no es cíclico, pero no estoy 100% ciento seguro. Lo que si se, es que se puede reducir a "checar" la partida desde cinco puntos, como por ejemplo: los puntos 1,2,3,6 y 8 los demas por simetría se reduce a lo mismo. No creo que lo proporcional tenga que ver con la solución. Es mas, basta con trazar una línea extra en algunos lúgares y el grafo se vuelve asimétrico con una proporción de 19/11.
Digamos que trazamos una línea de 5 a 7 y podrémos seguir el cámino 1-11-9-2-6-3-10-4-7-5-8-1 con sus respéctivos cíclos 11-9-2-3.....-11, 9-2-6...-9, etc, ademas, creo que existe otra variación si cambio un poco el rumbo y en vez de ...-4-7-5.., tomo la ruta de ...-4-5-7...  . Digamos que ahora trazo una línea de 6 a 7 en vez de 5 a 7, de forma tal que tenga la misma proporción de 19/11. Entonces, prodré seguir la ruta: 1-2-9-11-10-3-6-7-4-5-8-1 con sus respéctivos cíclos.
Finalmente, creo que no tiene solución, pero como dije anteriormante no estoy 100% ciento seguro (si se pudiera saber como se explica la existéncia ó no existéncia de la solución de grafos cíclicos.) Pienso que la solución de este tipo de problemas tiene que ver con la teoría de combinaciones.
Saludos
Topolino.
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.832



Ver Perfil
« Respuesta #3 : 20 Marzo, 2011, 08:04 »

Bueno, anoche estaba un poco dormido; tal como dice Topolino no tiene que ver con la proporción, aunque creo que sí tiene que ver con la divisibilidad, que es lo que intuí por encima sin profundizar. Vaya por delante que desconozco este tema.
 Creo que, en efecto, puede estar relacionado con los grupos de permutaciones, transposiciones y ciclos.
 Si tomamos un triángulo de vértices 1,2,3, podemos cerrar el camino partiendo de cada uno de los vértices; lo que se puede ver como grupos de permutaciones según el sentido que tomemos (1 2 3) (2 3 1) (3 1 2)... Esto lleva a deducir de forma inmediata algo muy obvio: cada vértice debe estar conectado al menos a dos caminos; para poder volver por un camino distinto, ya que, volver por el mismo supondría pasar dos veces por un mismo vértice. Y, por otra parte, el número de tramos recorridos, con las condiciones que se dan, ha de ser igual al número de vértices que pisamos: si pisamos una cantidad X de vértices distintos –distintos, digo- tendremos que recorrer X segmentos, dado que hay que volver al punto del que partimos. Entonces, valga esto como el más elemental teorema para empezar a pensar sobre el asunto: vértices = segmentos.

 Luego si tenemos un gráfico con el mismo número de vértices conectados por el mismo número de segmentos se podrá conseguir lo que se pide en el problema (basta para verlo con hacer dibujos con un triángulo, un cuadrado, etc).

La cuestión es que en el problema tenemos un número distinto de vértices y de segmentos que conectan a estos vértices; y aquí es donde intuyo que se puede resolver la cuestión por algún criterio relacionado con la divisibilidad; sobran 7 caminos:

18-11=7

O se puede interpretar también que faltan siete vértices.

Si ahora ponemos en hilera 11 puntos y al lado otra hilera de 7 puntos, y seguidamente unimos los puntos en zigzag (por  biyección) nos quedan 4 puntos sueltos: 11-7=4

 Pienso que esta forma de analizarlo –simplificándolo en dos líneas paralelas de puntos- puede ser válida; dibujando no encuentro un contraejemplo, aunque es muy intuitivo, eso sí es verdad.

Saludos. 
En línea

Dogod
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 1.678


Ver Perfil
« Respuesta #4 : 20 Marzo, 2011, 10:14 »

No tiene que ver con la existencia de un "camino hamiltoniano"?

Yo no sé nada del tema pero creo que por Teorema de Dirac se podría demostrar que no existe solución.

Sea [texx] G= (V, E)[/texx] grafo no dirigido, [texx]\left |{V}\right |= n[/texx]

[texx]\delta\geq{(n - 1)/2}[/texx] [texx]\longrightarrow{}[/texx] G tiene camino hamiltoniano.

Pero creo que en este caso no se cumple, es decir, se cumple el recíproco, pero no el teorema. Digo yo no sé ustedes qué dicen. En realidad sólo me pego al post porque es muy interesante el problema.

Un saludo
En línea

Las cosas pasan es por algo, y no hay mal que por bien no venga dicen en mi tierra...
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.832



Ver Perfil
« Respuesta #5 : 20 Marzo, 2011, 11:39 »

No tiene que ver con la existencia de un "camino hamiltoniano"?

Yo no sé nada del tema pero creo que por Teorema de Dirac se podría demostrar que no existe solución.

Sea [texx] G= (V, E)[/texx] grafo no dirigido, [texx]\left |{V}\right |= n[/texx]

[texx]\delta\geq{(n - 1)/2}[/texx] [texx]\longrightarrow{}[/texx] G tiene camino hamiltoniano.

Pero creo que en este caso no se cumple, es decir, se cumple el recíproco, pero no el teorema. Digo yo no sé ustedes qué dicen. En realidad sólo me pego al post porque es muy interesante el problema.

Un saludo


Hola, Dogod, yo de esto sí que no sé pero nada de nada, para mí Hamilton es una actor de cine antiguo :cara_de_queso: Pero acabo de ver una cosa de la que no me he dado cuenta antes:

 Cuando tenemos el mismo número de puntos y segmentos sí se puede completar el camino que piden, es obvio. Entonces, en este caso tenemos siete segmentos de sobra o siete puntos que faltan; es igual verlo de un modo u otro.

 Formando una fila de 11 puntos y otra al lado de 7 (18 en total) y uniendo los 7 puntos de la fila de 7 con los 7 primeros de la fila de 11, tendremos 14 elementos unidos y, por tanto, [texx]14-1=13[/texx] segmentos. Si ahora trazamos, desde el último punto al que hemos llegado, unos segmentos para unir los cuatro puntos que quedan, tendremos cuatro segmentos sueltos más, digamos, no unidos en zig-zag (son cuatro en vez de tres porque partimos del último al que habíamos llegado). El primer grupo de segmentos representa la solución trivial del grafo (mismos puntos y mismos caminos tiene solución) el segundo grupo del grafo unido al primero podrá tener solución o no según la divisibilidad entre ambos grupos.

Y vemos que, en este caso, la razón entre los dos grupos de segmentos es [texx]13/4[/texx] que no es divisible.

 En cambio, si añadimos un segmento más, como dice Topolino, sí se puede, en efecto; veamos lo que pasa haciendo lo mismo de antes:

 Tenemos [texx]19-11=8[/texx], por tanto ahora formamos dos hileras, una de 8 puntos y otra de 11. Uniendo los 8 puntos de la fila de ocho con los 8 primeros de la fila de 11 tendremos 16 elementos unidos en zig-zag; y, por consiguiente, [texx]16-1=15[/texx] segmentos. Ahora, desde el último al que habíamos llegado, unimos los tres puntos que quedan y tenemos 3 segmentos más; y resulta que la razón entre los dos grupos de segmentos es 15/3; que sí es divisible.

Se puede simplificar el ejemplo para estudiar el porqué; pongamos cuatro puntos y dos segmentos (aquí no hace falta nacer nada, nunca podremos llegar al punto de partida por falta de caminos). Tendremos dos hileras, una de cuatro puntos y otra de dos. Uniendo 2 con 2 tenemos 3 segmentos; y otros 2 sobrantes que obtenemos de unir los que quedan: ahora se ve más claro el porqué del asunto, resulta 3/2, que  no es divisible.
 Se trata en efecto de un problema de divisibilidad en el que podemos abstraer el grafo para verlo en abstracto; es lo que yo creo, pero ya digo que yo de esto no sé.

Saludos.
En línea

makoto91
mathematicae
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Perú Perú

Mensajes: 178



Ver Perfil
« Respuesta #6 : 01 Agosto, 2011, 18:55 »

la verdad este problema no lo podria resolver porque no tengo el nivel necesario
pero cuando lo veo como un juego creo que me podria acerca algo ya que tengo mucho tiempo
desde que juego consolas.
les pediria que me hagan saber si me equivoco en la serie,1-8-6-2-9-3-7-4-5-11-1.
En línea

En matemáticas uno no entiende las cosas, se acostumbra a ellas.
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!