Exercício 22.2-7 de CLRS3 ou CLRS2 - Há dois tipos de lutadores profissionais: os “bonzinhos” e os “vilões”. Entre qualquer par de lutadores profissionais pode ou não haver uma rivalidade. Suponha que tenhamos n lutadores profissionais e uma lista de r pares de lutadores entre os quais há rivalidade. Dê um algoritmo de tempo
que determine se é possível designar alguns dos lutadores como bonzinhos e os restantes como vilões, de modo que a rivalidade ocorra sempre entre um bonzinho e um vilão. Se for possível realizar tal designação, seu algoritmo deve produzi-la. (Dica: pense nos níveis da árvore da busca em largura - os vértices que têm o mesmo valor d estão no mesmo nível)
Passo 1
O enunciado pede para, dado um conjunto de
lutadores e uma lista de
pares de rivalidade, decidir se é possível classificar cada lutador como “bonzinho” ou “vilão” de modo que toda rivalidade ocorra sempre entre um bonzinho e um vilão. Se for possível, devemos produzir essa classificação. As informações relevantes dadas são:
- Temos
lutadores (vamos representá‑los como vértices de um grafo). - Temos
pares de rivalidade (vamos representá‑los como arestas do grafo). - Precisamos de um algoritmo com tempo
. - Se houver solução, o algoritmo deve também construir (produzir) a atribuição dos lutadores aos dois grupos.
Passo 2
Modelagem do problema (o que a questão realmente dá, em linguagem de grafos):
- Construímos um grafo não direcionado
onde é o conjunto dos lutadores e contém exatamente as arestas correspondentes às rivalidades. - Cada aresta
significa que e são rivais e, portanto, devem ficar em grupos diferentes. - A tarefa, então, é decidir se existe uma partição de
em dois conjuntos disjuntos (bonzinhos) e (vilões) tal que toda aresta tem uma extremidade em e a outra em . Em termos de grafos, isso é testar se é 2‑colorível (ou bipartido) e produzir tal coloração se existir.
Passo 3
Ideia principal (intuição usando níveis da busca em largura):
- Se fizermos uma busca em largura (BFS) a partir de algum vértice
, a BFS atribui a cada vértice um valor de distância (o número de arestas do caminho mais curto de até ). Os vértices com a mesma estão no mesmo “nível” da árvore de BFS. - Observação útil: se uma aresta conecta dois vértices que pertencem a níveis com paridades diferentes (um nível par e um nível ímpar), então podemos colocar todos os vértices de níveis pares em
e os de níveis ímpares em ; todas as arestas entre níveis consecutivos ficam entre e . - Se, durante a BFS, encontramos uma aresta que liga dois vértices do mesmo nível (ou, equivalentemente, com a mesma paridade de
), então não é possível 2‑colorir aquele componente (há um potencial conflito). Isso leva ao teste concreto: atribuir cores segundo e verificar arestas internas à mesma cor.
Passo 4
Estruturas de dados e representação recomendada:
- Representaremos
por listas de adjacência; isso permite percorrer todas as arestas em tempo proporcional a . - Mantemos para cada vértice
os campos: onde e representam as duas classes (por exemplo, = bonzinho, = vilão), e significa não visitado ainda. - Mantemos também
(distância) opcionalmente, mas a paridade de é exatamente . Usamos uma fila para a BFS.
Passo 5
Descrição passo a passo do algoritmo (alto nível):
- Inicialize
para todo . - Para cada vértice
tal que faça:
a. Defina; coloque na fila .
b. Enquantonão estiver vazia:
i. Retirede .
ii. Para cada vizinhode (isto é, para cada ):
- Se, então defina e enfileire .
- Se, então há um conflito: termine e declare que a atribuição é impossível. - Se o processo terminar sem conflitos, a atribuição dada por
é uma classificação válida: todos os vértices com são “bonzinhos” e os com são “vilões”.
Passo 6
Pseudocódigo (com todas as variáveis matemáticas em TeX):
Passo 7
Justificativa de correção (por que isso realmente resolve o problema):
- Se o algoritmo termina sem detectar aresta com extremidades da mesma cor, então toda aresta
tem , logo os conjuntos e formam uma partição válida em que todas as rivalidades cruzam os grupos. - Se existe uma aresta
com detectada, então mostro que não existe 2‑coloração daquela componente: suponha que . Pela construção da BFS, existe um caminho de até de comprimento com paridade e outro caminho de até de mesma paridade . Concatenando o caminho de a , a aresta e o caminho inverso de a , obtemos um ciclo de comprimento ímpar. Um grafo que contém ciclo de comprimento ímpar não é 2‑colorível; portanto, a presença desse conflito implica que não existe classificação desejada para aquele componente. Assim o algoritmo decide corretamente.
Passo 8
Complexidade (por que é
):
- Usando listas de adjacência, cada vértice entra na fila no máximo uma vez e cada aresta
é examinada no máximo duas vezes (uma ao ver em e outra ao ver em ). As operações de enfileirar/desenfileirar são cada uma. - Portanto o tempo total é
, isto é .
Passo 9
Observações práticas e dicas para a prova:
- Sempre use listas de adjacência porque matrizes de adjacência teriam custo
no pior caso e não atendem a exigência quando o grafo é ralo. - Lembre‑se de percorrer todos os vértices
que ainda estão para cobrir grafos desconexos (cada componente conexa é tratada com uma BFS separada). - Na implementação, basta guardar
(0 ou 1) — não é necessário guardar explicitamente se só nos interessa a paridade; mas guardar também é perfeitamente ok. - Quando estiver resolvendo rapidamente na prova: escreva “fazer BFS em cada componente atribuindo cor alternada por níveis; se achar aresta entre mesmos níveis → impossível; senão, conjuntos por paridade são a solução” e explique brevemente a complexidade
.
Passo 10
Exemplo curtinho para fixar a intuição (opcional para leitura rápida):
- Se tivermos um triângulo (3 vértices todos ligados entre si), a BFS a partir de um vértice
dá , seus dois vizinhos terão ; quando processarmos a aresta entre esses dois vizinhos veremos e detectamos conflito → impossível (triângulo é ciclo ímpar). - Se tivermos um caminho de comprimento 3 (4 vértices em linha), BFS produz cores alternadas
e nenhuma aresta liga vértices da mesma cor → possível.
Resposta
Algoritmo: executar BFS em cada componente de
usando listas de adjacência, atribuindo
à raiz e, ao relaxar arestas, atribuir
aos vizinhos não coloridos; se encontrar alguma aresta com
retornar “impossível”, senão retornar a partição
(bonzinhos) e
(vilões). Complexidade:
.