S6.6- Sucesiones de De Bruijn | | UPV

Título: S6.6- Sucesiones de De Bruijn Descripción automática: En este video, se explica el concepto de sucesiones de un área específica y su relación con la teoría de grafos, particularmente con los grafos eulerianos. Se comienza proponiendo el desafío de decodificar una combinación de cuatro dígitos mediante fuerza bruta y se plantea cómo minimizar el número de teclas presionadas aprovechando dígitos entre intentos. Se introduce el ejemplo de la cadena "0011", la cual permite generar todas las posibles combinaciones de dos dígitos conformadas por ceros y unos. Se define que una sucesión es de este tipo si tiene 2^n caracteres y cada cadena posible de n caracteres se presenta una única vez, permitiendo la concatenación de la cadena consigo misma. A continuación, se relacionan las sucesiones con la teoría de grafos; se utilizaron grafos dirigidos para su construcción. Se describe cómo se construye un grafo dirigido para el caso n=2, donde cada vértice representa una cadena posible de n-1 caracteres, y cada arista se etiqueta con el carácter que añade al nodo de salida para alcanzar el nodo de llegada. Se resalta que el grafo es euleriano y se muestra cómo, al buscar un ciclo euleriano, se obtienen las sucesiones deseadas. Se extiende el proceso a grafos más complejos para obtener sucesiones de mayor longitud y se ejemplifica con el caso n=3. Finalmente, se sugiere que hallar estas sucesiones en grafos también es posible mediante ciclos hamiltonianos, pero el enfoque del video está en ciclos eulerianos. El video termina resumiendo el proceso de generación de sucesiones a partir de grafos eulerianos. Autor/a: Conejero Casares José Alberto + Universitat Politècnica de València UPV: https://www.upv.es + Más vídeos en: https://www.youtube.com/valenciaupv + Accede a nuestros MOOC: https://upvx.es #teoría de grafos #grafos eulerianos