Este subtema (TANS 3.16) cierra el bloque de teoría de grafos y, con él, todo el Tema 3 de Geometría y Trigonometría. Es exclusivo del Nivel Superior. Aplica el vocabulario de TANS 3.14 y las matrices de TANS 3.15 a cuatro problemas algorítmicos clásicos: recorridos eulerianos, recorridos hamiltonianos, árbol generador mínimo (AGM) y problema del viajante (TSP). Es el subtema más procedimental de todo el tema: el examen pide ejecutar algoritmos paso a paso.
Los algoritmos en grafos son una de las áreas matemáticas con mayor impacto industrial: la logística (Amazon, UPS), la planificación de redes (telecomunicaciones, eléctricas), la circuitería de chips (VLSI), el GPS y las recomendaciones de Netflix usan, todas, variantes de los algoritmos que veremos. El subtema cubre los cuatro problemas canónicos y los algoritmos para resolverlos exactamente o, cuando es imposible (NP-difícil), aproximadamente con garantías.
Pregunta originaria: ¿se puede recorrer todos los puentes de Königsberg sin cruzar ninguno dos veces?
En un grafo conexo:
Accede a apuntes, prácticas y herramientas de Matemáticas: Aplicaciones e Interpretación sin pagar nada. Sin tarjeta. Solo tu email — los usuarios gratuitos pueden leer 10 páginas distintas por semana.
¿Ya tienes cuenta? Inicia sesión.