¿Qué significa "Lista de Tareas"?
Tabla de contenidos
La asignación de listas es una forma de darle opciones a los elementos en un grafo. En este contexto, asignamos un conjunto de valores a cada vértice (los puntos en el grafo) y a cada arista (las líneas que conectan los puntos).
Por ejemplo, cada vértice puede tener una lista de números, y cada arista también puede tener su propia lista de números. Esta configuración nos permite encontrar una forma de elegir números de estas listas de manera que se cumplan ciertas condiciones, especialmente al mirar las partes conectadas del grafo.
Cuando hablamos de cómo hacer esto, a menudo nos enfocamos en propiedades específicas del grafo que ayudan a determinar si es posible hacer estas elecciones. Algunos grafos son más fáciles de trabajar que otros, especialmente si siguen ciertas reglas sobre cuántas aristas tienen en comparación con sus vértices.
Número de Empaque de Listas
El número de empaque de listas es un concepto que nos ayuda a entender cuántas formas diferentes podemos colorear los vértices de un grafo con las listas que hemos asignado. Cada color debe provenir de la lista asociada a ese vértice.
El objetivo es encontrar el número más pequeño 'k' donde siempre podemos hacer 'k' conjuntos diferentes de colores que no compartan colores entre los conjuntos. Esta idea es particularmente interesante cuando miramos grafos que no tienen muchas aristas conectadas a cada vértice.
Queremos ver si hay un límite en cuántos colores podemos usar según cuántas aristas conectan a cada vértice. Esta conexión nos ayuda a ver las diferencias entre el empaque de listas y otros métodos de coloración usados para grafos.