Investigathon2025

Investigathon 2025 organizado por Y-hat en FCEN-UBA

Grupo 4: Track de grafos.

Estructura del repositorio:

/informe se encuentra un archivo markdown con el informe que incluye:

• Propiedades que fuimos encontrando.
• Definiciones.
• Explicación a algunos de los algoritmos que hicimos.
• Demostraciones.
• Referencias que nos resultaron útiles.

Códigos:

• /codigoLineal:

  • En caminitudV2 esta la implementación del algoritmo de decisión en $\mathcal{O}(n)$.
  • En codigoComentado.cpp hay una explicación a alto nivel del código.

• /codigoTrivialOrdenFijo se encuentra:

  • El algoritmo decisión en $\mathcal{O}(n! \cdot n)$.
  • La función el_orden_puede_ser_coloreado que dado un orden, verifica si existe una coloración válida y podría dar el testigo en $\mathcal{O}(n)$.

• /codigoEric es la implementación por fuerza bruta dada originalmente junto al enunciado del problema.

Los algoritmos toman al principio un número t de cantidad de tests.

En /tests se encuentra un generador de tests y carpetas, con los casos de prueba, nombradas para cada $n$ cantidad de vértices. Actualmente la implementación en tiempo lineal fue testeada hasta $n=12$.

En /docs se encuentra el enunciado original del problema.