O que significa "Lista de Tarefas"?
Índice
A atribuição de listas é um jeito de dar escolhas pros elementos num grafo. Nesse contexto, a gente atribui um conjunto de valores pra cada vértice (os pontos no grafo) e pra cada aresta (as linhas que ligam os pontos).
Por exemplo, cada vértice pode ter uma lista de números, e cada aresta também pode ter sua própria lista de números. Esse esquema permite a gente encontrar um jeito de escolher números dessas listas de forma que certas condições sejam atendidas, especialmente quando olhamos pras partes conectadas do grafo.
Quando falamos sobre como fazer isso, geralmente focamos em propriedades específicas do grafo que ajudam a determinar se é possível fazer essas escolhas. Alguns grafos são mais fáceis de trabalhar do que outros, especialmente se eles seguem certas regras sobre quantas arestas têm em comparação com seus vértices.
Número de Empacotamento de Listas
O número de empacotamento de listas é um conceito que ajuda a entender quantas maneiras diferentes a gente pode colorir os vértices de um grafo com as listas que atribuimos. Cada cor deve vir da lista associada a aquele vértice.
O objetivo é achar o menor número 'k' onde a gente sempre consegue fazer 'k' conjuntos diferentes de cores que não compartilham nenhuma cor entre os conjuntos. Essa ideia é especialmente interessante quando olhamos pra grafos que não têm muitas arestas conectadas a cada vértice.
A gente quer ver se tem um limite pra quantas cores a gente pode usar com base em quantas arestas se conectam a cada vértice. Essa conexão ajuda a gente a ver as diferenças entre o empacotamento de listas e outros métodos de coloração usados pra grafos.