Material de Algoritmos

Material

Dicas dos problemas:

1. Veja o que acontece quando temos um ciclo
2. Se temos um grafo com $2n$ vértices, prove que podemos dividir ele em dois grafos de $n$ vértices, e juntá-los com apenas uma cor a mais.
3. Seja $2m$ o maior clique do grafo.Divida o grafo em dois outros grafos $A, B$, onde o maior clique de $A$ tem tamanho $2m$. Enquanto o maior clique de $A$ for maior que o maior clique de $B$, passe um vértice de $A$ para $B$.
4. Primeiro troque $1776$ por $a$ e $2016$ por $b$, e vamos usar apenas o fato de que $a < b$. Veja que os conjuntos históricos são da forma $\{ x, x+a, x+a+b \}$ e $\{ x, x+b, x+a+b \}$. Agora, tente montar o algoritmo guloso onde sempre pegamos o menor número que ainda não está num conjunto, e colocamos ele, e tente provar que esse algoritmo sempre funciona.
5. Tente fazer um algoritmo indutivo, retirando uma folha de $T$.
6. Veja que podemos mudar a ordem das colunas sem nenhum problema, então, ordene-as pelos elementos da primeira linha em ordem crescente. Então, prove que o seguinte algoritmo funciona: Começando pelo primeiro elemento, vá escolhendo os elementos de cima, até chegar num $a_k$ de modo que a soma atual é menor que $\frac{n+1}{4}$ e a soma atual mais $a_k$ é maior. A partir de $a_k$, pegue os elementos de baixo.
8. Veja que $1 \le i-a_i \le n$. Construa um grafo que leva $i$ para $i-a_i$. Prove que se o grafo tem um ciclo, o problema acabou, e ache esse ciclo.