Autor Tema: Ayuda con este punto urgente python

0 Usuarios y 1 Visitante están viendo este tema.

26 Agosto, 2019, 09:01 am
Leído 797 veces

FelipeCardoxo

  • Nuevo Usuario
  • Mensajes: 8
  • Karma: +0/-0
  • Sexo: Masculino
Debo realizar el siguientes ejercicio

Implemente un algoritmo en Python que determine si existe al menos un ciclo simple
en un grafo no dirigido G = V;E, el algoritmo implementado deberá correr en tiempo
O(V ), independiente de |E|

Me pueden ayudar no tengo idea de como hacerlo

26 Agosto, 2019, 11:33 am
Respuesta #1

feriva

  • Matemático
  • Mensajes: 9,054
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Debo realizar el siguientes ejercicio

Implemente un algoritmo en Python que determine si existe al menos un ciclo simple
en un grafo no dirigido G = V;E, el algoritmo implementado deberá correr en tiempo
O(V ), independiente de |E|

Me pueden ayudar no tengo idea de como hacerlo

Hola.

Yo, los grafos no los estudiado, pero algo sé por afición.

Supongo que el programa lo que tiene que hacer es aplicar el teorema de Rédei.

Dado que los grafos pueden ser infinitos y complicadísimos, supongo que has de empezar la rutina con un input para que el usuario meta los vértices que quiera con el grado asociado a cada vértice.

Para esto se me ocurre que uses diccionarios de Python (supongo que sabes lo que son, pero te paso un enlace y te explico un poco por si no los has usado):

https://devcode.la/tutoriales/diccionarios-en-python/

Como ves, en un diccionario tiene datos de clave (key) y el valor, que se separa por dos puntos pero van en parejas, asociados.

Para poner un ejemplo de uso, imagina la factorización de un número, por ejemplo 12; tendríamos este diccionario:

{2: 2, 3: 1}

donde el primer 2 es el factor primo 2 y detrás de los dos puntos nos dice la potencia de 2; con el tres igual.

Ahora tú puedes poner, en vez de un 2 en la llave, un vértice “A” con ésta u otra variable alfanumérica. Detrás de los dos puntos vendría el grado del del vértice.

Con el input el usuario iría metiendo los vértices y su grado asociado, la cantidad que quisiera. Una vez que terminara podría pulsar una tecla de escape o lo que fuera.

Para aplicar el teorema de Rédei necesitarías un bucle “for in diccionario” para luego ir comparando los grados de A con B, con C... etc., las combinaciones necesarias y así hasta completar la comprobación (si luego puedo intento programar algo a ver cómo funciona lo que digo, que tampoco sé seguro, esto es así a vuelapluma).

De todas maneras, quizá sea más cómodo usar una matriz con elementos [vértice, grado], no sé.

Saludos.