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 \mathrm{O}(\mathrm{n}+\mathrm{r}) 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 n lutadores e uma lista de r 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 n lutadores (vamos representá‑los como vértices de um grafo).
  • Temos r pares de rivalidade (vamos representá‑los como arestas do grafo).
  • Precisamos de um algoritmo com tempo \mathrm{O}(n+r).
  • 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 G=(V,E) onde V é o conjunto dos n lutadores e E contém exatamente as r arestas correspondentes às rivalidades.
  • Cada aresta (u,v)\in E significa que u e v são rivais e, portanto, devem ficar em grupos diferentes.
  • A tarefa, então, é decidir se existe uma partição de V em dois conjuntos disjuntos B (bonzinhos) e W (vilões) tal que toda aresta tem uma extremidade em B e a outra em W. Em termos de grafos, isso é testar se G é 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 s, a BFS atribui a cada vértice um valor de distância d[v] (o número de arestas do caminho mais curto de s até v). Os vértices com a mesma d 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 B e os de níveis ímpares em W; todas as arestas entre níveis consecutivos ficam entre B e W.
  • Se, durante a BFS, encontramos uma aresta que liga dois vértices do mesmo nível (ou, equivalentemente, com a mesma paridade de d), então não é possível 2‑colorir aquele componente (há um potencial conflito). Isso leva ao teste concreto: atribuir cores segundo d[v]\bmod 2 e verificar arestas internas à mesma cor.

Passo 4

Estruturas de dados e representação recomendada:
  • Representaremos G por listas de adjacência; isso permite percorrer todas as arestas em tempo proporcional a r.
  • Mantemos para cada vértice v os campos: \text{color}[v]\in\{\text{UNCOLORED},0,1\},onde 0 e 1 representam as duas classes (por exemplo, 0 = bonzinho, 1 = vilão), e \text{UNCOLORED} significa não visitado ainda.
  • Mantemos também \text{d}[v] (distância) opcionalmente, mas a paridade de \text{d}[v] é exatamente \text{color}[v]. Usamos uma fila para a BFS.

Passo 5

Descrição passo a passo do algoritmo (alto nível):
  1. Inicialize \text{color}[v]=\text{UNCOLORED} para todo v\in V.
  2. Para cada vértice s\in V tal que \text{color}[s]=\text{UNCOLORED} faça:
    a. Defina \text{color}[s]=0; coloque s na fila Q.
    b. Enquanto Q não estiver vazia:
    i. Retire u de Q.
    ii. Para cada vizinho v de u (isto é, para cada (u,v)\in E):
    - Se \text{color}[v]=\text{UNCOLORED}, então defina \text{color}[v]=1-\text{color}[u] e enfileire v.
    - Se \text{color}[v]=\text{color}[u], então há um conflito: termine e declare que a atribuição é impossível.
  3. Se o processo terminar sem conflitos, a atribuição dada por \text{color} é uma classificação válida: todos os vértices com \text{color}[v]=0 são “bonzinhos” e os com \text{color}[v]=1 são “vilões”.

Passo 6

Pseudocódigo (com todas as variáveis matemáticas em TeX):
\text{Bipartite\_Assign}(G=(V,E))
\text{para cada } v\in V \text{ faça } \text{color}[v]\leftarrow \text{UNCOLORED}ç
\text{para cada } s\in V \text{ faça}ç
\quad\text{se } \text{color}[s]=\text{UNCOLORED} \text{ então}ã
\quad\quad \text{color}[s]\leftarrow 0
\quad\quad Q \leftarrow \text{fila vazia};\; \text{enqueue}(Q,s)
\quad\quad \text{enquanto } Q \neq \varnothing \text{ faça}ç
\quad\quad\quad u \leftarrow \text{dequeue}(Q)
\quad\quad\quad \text{para cada } v \in \text{Adj}[u] \text{ faça}ç
\quad\quad\quad\quad \text{se } \text{color}[v]=\text{UNCOLORED} \text{ então}ã
\quad\quad\quad\quad\quad \text{color}[v]\leftarrow 1-\text{color}[u];\; \text{enqueue}(Q,v)
\quad\quad\quad\quad \text{senao se } \text{color}[v]=\text{color}[u] \text{ então}ã
\quad\quad\quad\quad\quad \text{return "impossível"}í
\text{return (\{v\mid \text{color}[v]=0\},\\ \{v\mid \text{color}[v]=1\})}

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 (u,v) tem \text{color}[u]\neq\text{color}[v], logo os conjuntos \{v\mid\text{color}[v]=0\} e \{v\mid\text{color}[v]=1\} formam uma partição válida em que todas as rivalidades cruzam os grupos.
  • Se existe uma aresta (u,v) com \text{color}[u]=\text{color}[v] detectada, então mostro que não existe 2‑coloração daquela componente: suponha que \text{color}[u]=\text{color}[v]=c. Pela construção da BFS, existe um caminho de s até u de comprimento com paridade c e outro caminho de s até v de mesma paridade c. Concatenando o caminho de s a u, a aresta (u,v) e o caminho inverso de v a s, 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 é \mathrm{O}(n+r)):
  • Usando listas de adjacência, cada vértice entra na fila no máximo uma vez e cada aresta (u,v) é examinada no máximo duas vezes (uma ao ver v em \text{Adj}[u] e outra ao ver u em \text{Adj}[v]). As operações de enfileirar/desenfileirar são \mathrm{O}(1) cada uma.
  • Portanto o tempo total é \mathrm{O}(|V| + \sum_{u\in V}|\text{Adj}[u]|), isto é \mathrm{O}(n+r).

Passo 9

Observações práticas e dicas para a prova:
  • Sempre use listas de adjacência porque matrizes de adjacência teriam custo \mathrm{O}(n^2) no pior caso e não atendem a exigência \mathrm{O}(n+r) quando o grafo é ralo.
  • Lembre‑se de percorrer todos os vértices s que ainda estão \text{UNCOLORED} para cobrir grafos desconexos (cada componente conexa é tratada com uma BFS separada).
  • Na implementação, basta guardar \text{color}[v] (0 ou 1) — não é necessário guardar explicitamente \text{d}[v] se só nos interessa a paridade; mas guardar \text{d}[v] 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 \mathrm{O}(n+r).

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 s \text{color}[s]=0, seus dois vizinhos terão \text{color}=1; quando processarmos a aresta entre esses dois vizinhos veremos \text{color}[v]=\text{color}[u]=1 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 0,1,0,1 e nenhuma aresta liga vértices da mesma cor → possível.

Resposta

Algoritmo: executar BFS em cada componente de G usando listas de adjacência, atribuindo \text{color}[s]=0 à raiz e, ao relaxar arestas, atribuir \text{color}[v]=1-\text{color}[u] aos vizinhos não coloridos; se encontrar alguma aresta com \text{color}[u]=\text{color}[v] retornar “impossível”, senão retornar a partição B=\{v\mid \text{color}[v]=0\} (bonzinhos) e W=\{v\mid \text{color}[v]=1\} (vilões). Complexidade: \mathrm{O}(n+r).

Exercícios relacionados