0. Como usar este guia
Estratégia
Não tente decorar todos os conceitos de uma vez. Em grafos, o que mais resolve exercício é reconhecer o tipo de pergunta e aplicar o procedimento correto.
- Identifique o tema: coloração, árvore, fluxo, emparelhamento etc.
- Conte o que importa: vértices, arestas, graus, capacidades ou custos.
- Aplique o algoritmo ou critério.
- Justifique a resposta com uma regra objetiva.
Quando há animação
As animações aparecem nos pontos em que o estado muda passo a passo: remoção de vértices, percursos, Kruskal/Prim, coloração, caminho aumentante e fluxo residual.
Use os botões Anterior e Próximo para estudar como se estivesse resolvendo no papel.
1. Conceitos básicos, conectividade e grafos h-conexos
Este bloco é a base para praticamente todo o restante. A ideia central é entender como o grafo se comporta quando removemos vértices, arestas ou quando analisamos sua estrutura.
Dual direcional
Em um grafo orientado, o dual direcional inverte o sentido de todos os arcos. Se havia (x,y), no dual aparece (y,x).
Prática: para construir, mantenha os mesmos vértices e vire todas as setas.
Grafo complementar
O complementar mantém os mesmos vértices, mas troca presença por ausência de arestas. Se dois vértices eram adjacentes em G, não serão em Ḡ; se não eram, passam a ser.
Prática: liste todos os pares possíveis e retire os pares que já existem em G.
Grafo regular
Um grafo não orientado é k-regular quando todo vértice tem grau k. Se k = 3, é um grafo cúbico.
Prática: calcule o grau de cada vértice; se todos forem iguais, é regular.
Conectividade
A conectividade k(G) é o menor número de vértices cuja remoção desconecta o grafo ou o reduz a um único vértice.
Prática: teste remover 1 vértice; se não der, teste pares; depois trios.
Subconjunto de articulação e h-conexidade
G é h-conexo se k(G) ≥ h.
Também: G é h-conexo ⇔ entre todo par de vértices existem pelo menos h caminhos internamente disjuntos.
Caminhos internamente disjuntos podem ter os mesmos extremos, mas não compartilham vértices internos. Isso aparece quando o exercício pede robustez do grafo.
Animação — remoção de vértices e conectividade
Roteiro de prova para conectividade
- Veja se o grafo original é conexo. Se já não for, a conectividade usual não é tratada como nos exercícios de grafos conexos.
- Procure vértice de articulação: remova mentalmente um vértice e veja se separa o grafo.
- Se existir um vértice que desconecta, então k(G)=1.
- Se nenhum vértice sozinho desconecta, teste pares.
- O menor tamanho de conjunto que desconecta é o valor de k(G).
- O grafo é h-conexo para todo h ≤ k(G).
2. Grafos planares e k-partidos
Um grafo é planar se pode ser desenhado no plano sem cruzamento de arestas. Cuidado: um desenho com cruzamentos não prova que o grafo não é planar; talvez exista outro desenho sem cruzamentos.
Fórmula de Euler
Vale para grafo simples, conexo e planar. Aqui:
- n: número de vértices;
- m: número de arestas;
- r: número de regiões, incluindo a região externa.
Como resolver exercício
- Conte vértices e arestas.
- Tente redesenhar sem cruzamentos.
- Conte as regiões fechadas e a região externa.
- Substitua em n - m + r = 2.
- Se a conta não fechar para um desenho supostamente planar, revise a contagem de regiões.
Grafos k-partidos
Um grafo é k-partido quando os vértices podem ser divididos em k conjuntos independentes. Dentro de um mesmo conjunto não pode haver aresta. Arestas só podem aparecer entre conjuntos diferentes.
Bipartido é o caso especial com 2 partes. Na prática, é parecido com tentar colorir os vértices usando apenas duas cores.
Roteiro de prova para k-partido
- Escolha um vértice e coloque no conjunto A.
- Todos os vizinhos dele devem ir para B.
- Todos os vizinhos dos vértices de B devem voltar para A.
- Se aparecer uma aresta dentro do mesmo conjunto, não é bipartido.
- Se não der com 2 partes, tente 3 ou mais, dependendo da pergunta.
3. Percursos abrangentes — Eulerianos e Hamiltonianos
Percurso abrangente é um percurso que usa todos os vértices ou todas as arestas. Os dois tipos mais importantes são:
| Tipo | O que precisa usar? | Regra prática |
|---|---|---|
| Euleriano | Todas as arestas uma única vez | Olhe os graus dos vértices. |
| Hamiltoniano | Todos os vértices uma única vez | Tente montar um ciclo/caminho passando por todos. |
Euleriano — regra dos graus
- Todos os vértices pares → circuito euleriano.
- Exatamente 2 vértices ímpares → caminho euleriano aberto.
- Mais de 2 vértices ímpares → não existe percurso euleriano usando todas as arestas uma vez.
Hamiltoniano — cuidado
O exercício geralmente pede encontrar ou verificar um ciclo. Teoremas como Dirac/Ore são condições suficientes, mas não necessárias.
Se o grafo não satisfaz o teorema, isso não prova sozinho que ele não é hamiltoniano.
Animação — Euleriano x Hamiltoniano
4. Árvore geradora de custo mínimo — Kruskal e Prim
Uma árvore é conexa e não possui ciclos. Se o grafo tem n vértices, uma árvore geradora usa todos os vértices e tem exatamente n - 1 arestas.
A árvore geradora de custo mínimo, também chamada APCM, escolhe as arestas de menor custo total possível mantendo todos os vértices conectados e sem formar ciclo.
Kruskal
Ordena todas as arestas por peso crescente. Vai escolhendo a menor aresta disponível, desde que ela não forme ciclo. Para quando tiver n - 1 arestas.
Prim
Começa em um vértice. Mantém um conjunto T de vértices já alcançados. A cada passo, escolhe a menor aresta entre T e V - T.
Animação — Kruskal e Prim no mesmo grafo
Como responder no papel
- Mostre a lista de arestas com pesos.
- Em Kruskal, ordene por peso crescente.
- Marque arestas aceitas e rejeitadas por ciclo.
- Em Prim, mantenha a tabela com T, V-T, aresta escolhida e custo acumulado.
- Finalize quando houver n-1 arestas ou quando todos os vértices estiverem em T.
5. Coloração de vértices
Colorir vértices significa atribuir cores aos vértices de modo que dois vértices adjacentes não tenham a mesma cor. Uma k-coloração usa k cores. O menor k possível é o número cromático χ(G).
A aplicação clássica é agendamento de provas: cada prova é um vértice; se algum aluno faz duas provas, elas recebem uma aresta e não podem ocorrer no mesmo dia. O número cromático vira o número mínimo de dias.
Também aparece o Teorema das 4 cores: todo grafo planar pode ser colorido com no máximo 4 cores. Em mapas, regiões vizinhas não podem ter a mesma cor.
Animação — coloração gulosa de vértices
Roteiro prático para coloração de vértices
- Procure cliques: um triângulo exige pelo menos 3 cores; um K₄ exige 4.
- Colora os vértices mais restritivos primeiro, geralmente os de maior grau.
- Para cada vértice, use a menor cor que não aparece em seus vizinhos já coloridos.
- No fim, verifique aresta por aresta se há conflito.
- Para provar que o número é mínimo, aponte uma clique ou explique a impossibilidade com menos cores.
6. Coloração de arestas
Agora as cores vão nas arestas. A coloração é própria quando arestas incidentes no mesmo vértice têm cores diferentes. O menor número de cores é o índice cromático χ'(G).
Limites importantes
Como um vértice de grau máximo Δ(G) possui várias arestas incidentes, todas essas arestas precisam ter cores diferentes.
Teorema de Vizing
Na prática, tente primeiro com Δ(G) cores. Se não conseguir, use Δ(G)+1.
Cada cor forma um emparelhamento, pois duas arestas da mesma cor não podem compartilhar vértice.
Animação — coloração de arestas
7. Emparelhamentos
Um emparelhamento é um conjunto de arestas sem vértices em comum. Nenhuma aresta escolhida pode encostar em outra aresta escolhida.
| Conceito | Significado prático |
|---|---|
| Emparelhamento | Arestas escolhidas sem repetir vértices. |
| Maximal | Não dá para adicionar mais aresta sem quebrar a regra. |
| Máximo | Tem o maior número possível de arestas. |
| Perfeito | Satura todos os vértices. |
Pegadinha: maximal não é a mesma coisa que máximo. Maximal só significa que você ficou travado; máximo significa que não existe solução maior.
Caminho alternante e aumentante
Aumentante: alternante e começa/termina em vértices livres.
Se existe caminho aumentante, M ainda não é máximo.
O truque é inverter o caminho: as arestas que estavam fora entram, e as que estavam dentro saem. O emparelhamento aumenta em uma unidade.
Animação — caminho aumentante
8. Coberturas
Uma cobertura de vértices é um conjunto K de vértices tal que toda aresta do grafo tem pelo menos uma extremidade em K.
Exemplo mental: instalar câmeras em esquinas para vigiar todas as ruas. As ruas são arestas; as esquinas são vértices. Queremos o menor conjunto de esquinas que cobre todas as ruas.
Relação com emparelhamento
Como as arestas de um emparelhamento não compartilham vértices, cada uma delas exige pelo menos um vértice diferente na cobertura.
Como achar cobertura mínima
- Liste todas as arestas.
- Escolha vértices que cobrem muitas arestas.
- Verifique se toda aresta foi coberta.
- Tente remover vértices escolhidos.
- Compare com um emparelhamento: se |M| = |K|, você tem uma forte evidência de mínimo.
Animação — cobertura de vértices
9. Fluxos em grafos — Ford-Fulkerson
Fluxo em grafos representa quanto de um recurso passa pelos arcos de uma rede direcionada. Existe uma fonte s, um sumidouro t, capacidades nos arcos e fluxos respeitando essas capacidades.
Ideia principal
O fluxo máximo é a maior quantidade possível que sai de s e chega em t.
Grafo residual / folgas
Para cada arco com capacidade c e fluxo f:
- se f < c, existe folga direta c - f;
- se f > 0, existe arco reverso com folga f.
Animação — aumento de fluxo e residual
Roteiro Ford-Fulkerson para prova
- Comece com fluxo zero.
- Construa o grafo residual.
- Encontre um caminho de s até t.
- A folga do caminho é a menor folga entre seus arcos.
- Some essa folga no caminho.
- Atualize os arcos reversos.
- Repita até não existir caminho de s até t.
- O fluxo encontrado é máximo; o corte mínimo confirma.
10. Fluxo com custo mínimo
Fluxo com custo adiciona um custo a cada arco. A pergunta típica é: qual quantidade máxima pode ser enviada e qual o custo total mínimo?
No grafo residual, quando um arco já tem fluxo, o arco reverso aparece com custo negativo. Se o custo original é y, o reverso tem custo -y. Isso permite desfazer uma escolha anterior se aparecer uma opção melhor.
Por poder haver custos negativos no residual, não basta usar qualquer algoritmo ingênuo. Em muitos exercícios da disciplina, a lógica prática é: a cada iteração, escolher o caminho aumentante de menor custo, calcular a folga, enviar fluxo e atualizar o residual.
Animação — fluxo máximo com custo mínimo
10.1 Exercícios resolvidos - fluxo com custo mínimo (lista de fluxo)
Esta seção resolve a lista de exercícios de fluxo com custo mínimo. Em cada iteração, todos os caminhos possíveis no residual são listados; cada caminho eliminado mostra custo unitário, gargalo e arco de bloqueio.
Quando aparece arco residual invertido, a seta é desenhada no sentido invertido e o custo troca de sinal. Nos exercícios 2 e 3 aparece explicitamente o arco residual invertido 6 -> 2 com custo -3, reverso de 2 -> 6.
Exercício 1
Fluxo máximo: 90
Custo mínimo: 915
Exercício 2
Fluxo máximo: 120
Custo mínimo: 1115
Exercício 3
Fluxo máximo: 135
Custo mínimo: 1340
Exercício 4
Fluxo máximo: 175
Custo mínimo: 1370
Resolução passo a passo
11. Exercícios N2 resolvidos
Esta seção reúne as resoluções detalhadas das quatro questões enviadas. A leitura comum entre elas é: transforme a matriz em grafo, identifique o tipo de problema e justifique a resposta com a propriedade estrutural correta.
Questão 1 — Segurança dos centros de treinamento
Modelo: coloração de vértices. Cada centro é um vértice; uma aresta indica que dois centros não podem ficar no mesmo turno.
A matriz gera, entre outras arestas, o subgrafo induzido pelos vértices {1,2,3,4}. Nele existem todas as arestas possíveis:
Logo, G[{1,2,3,4}] = K4. Como todo vértice de uma clique precisa receber cor diferente, qualquer cronograma precisa de pelo menos 4 turnos:
Agora basta exibir uma coloração válida com exatamente 4 turnos. Uma distribuição mínima é:
| Turno | Centros alocados | Verificação |
|---|---|---|
| Turno 1 | 1 e 5 | Não há aresta 1-5. |
| Turno 2 | 2 e 6 | Não há aresta 2-6. |
| Turno 3 | 3 e 7 | Não há aresta 3-7. |
| Turno 4 | 4 e 8 | Não há aresta 4-8. |
Conclusão: o número mínimo de turnos é 4. O limite inferior vem da clique K4, e a tabela prova que 4 turnos são suficientes.
Questão 2 — Iluminação temática das barracas
Modelo: bipartição/2-coloração de vértices. As duas modalidades de lâmpadas funcionam como duas cores; barracas ligadas por cabo precisam ficar em grupos diferentes.
Pela matriz, aparece o ciclo:
Esse ciclo usa 9 arestas. Portanto, é um ciclo ímpar C9. Um grafo é bipartido se, e somente se, não possui ciclo ímpar. Como há um ciclo ímpar, não existe distribuição com apenas duas modalidades de lâmpadas.
| Item | Resposta | Justificativa |
|---|---|---|
| (a) | Não é possível. | A estrutura contém o ciclo ímpar C9, então o grafo não é bipartido. |
| (b) | Também não é possível após adicionar a aresta 1-3. | Adicionar aresta não remove o C9 já existente. Além disso, a nova aresta cria outro ciclo ímpar: 1 - 3 - 7 - 2 - 6 - 1, de tamanho 5. |
Conclusão: a prefeitura não consegue usar somente duas modalidades de lâmpadas sem violar a restrição, nem no grafo original nem após a ligação direta entre as barracas 1 e 3.
Questão 3 — Rede central de distribuição de som
Modelo: árvore geradora mínima. É preciso conectar todos os 6 pontos com o menor comprimento total de cabo, sem circuitos fechados.
Aplicando Kruskal, ordenamos as conexões viáveis por peso e escolhemos apenas as que não fecham ciclo:
| Ordem | Aresta | Peso | Decisão | Motivo |
|---|---|---|---|---|
| 1 | 1-3 | 1 | Seleciona | É a menor aresta e conecta dois componentes distintos. |
| 2 | 2-6 | 2 | Seleciona | Conecta dois componentes distintos. |
| 3 | 2-5 | 3 | Seleciona | Inclui o ponto 5 sem formar ciclo. |
| 4 | 4-6 | 4 | Seleciona | Inclui o ponto 4 no componente de 2 e 6. |
| 5 | 1-4 | 5 | Seleciona | Une os dois componentes restantes. |
Uma topologia ótima é:
O comprimento total mínimo é:
Como o problema tem n = 6 vértices, uma árvore geradora deve ter exatamente n - 1 = 5 arestas. A solução encontrada tem 5 arestas, conecta todos os pontos e não possui ciclo. Portanto, é uma árvore geradora. Como Kruskal sempre escolhe a menor aresta segura em cada etapa, pela propriedade do corte a árvore obtida tem custo mínimo.
Conclusão: o menor gasto total é 15 metros. Existem empates possíveis nas arestas de peso 5, então pode haver mais de uma árvore geradora mínima com o mesmo custo.
Questão 4 — Tabela de jogos da Supercopa das Nações
Modelo: coloração de arestas. Cada partida é uma aresta; partidas incidentes no mesmo vértice não podem ocorrer no mesmo dia, pois uma seleção não joga duas vezes no mesmo dia.
Os graus dos vértices são:
| Seleção | Adversários | Grau |
|---|---|---|
| 1 | 2, 3, 4 | 3 |
| 2 | 1, 3, 5, 6 | 4 |
| 3 | 1, 2, 4, 5 | 4 |
| 4 | 1, 3, 5, 6 | 4 |
| 5 | 2, 3, 4, 6 | 4 |
| 6 | 2, 4, 5 | 3 |
O grau máximo é Δ(G)=4. Esse é um limite inferior físico: uma seleção com 4 jogos precisa de pelo menos 4 dias, pois só pode jogar uma vez por dia.
Um cronograma válido com exatamente 4 dias é:
| Dia | Partidas | Checagem |
|---|---|---|
| Dia 1 | 1-4, 2-3, 5-6 | Nenhuma seleção se repete. |
| Dia 2 | 2-5, 3-4 | Nenhuma seleção se repete. |
| Dia 3 | 1-2, 3-5, 4-6 | Nenhuma seleção se repete. |
| Dia 4 | 1-3, 2-6, 4-5 | Nenhuma seleção se repete. |
Como há uma coloração de arestas com 4 cores e já foi provado que menos de 4 dias é impossível, temos:
Conclusão: o número mínimo de dias é 4. Como o índice cromático é igual ao grau máximo, o grafo é de Classe 1 na classificação de coloração de arestas.
12. Checklist final para resolver exercícios
Quando aparecer...
- “sem cruzar arestas”: planaridade e fórmula de Euler.
- “menor número de cores nos vértices”: número cromático.
- “menor número de cores nas arestas”: índice cromático e grau máximo.
- “conectar todos com menor custo”: árvore geradora mínima.
- “maior quantidade que sai de s e chega em t”: fluxo máximo.
- “maior fluxo com menor custo”: fluxo com custo mínimo.
- “pares sem repetir vértice”: emparelhamento.
- “vértices que cobrem todas as arestas”: cobertura.
Pegadinhas frequentes
- Desenho com cruzamento não significa automaticamente não planar.
- Maximal não é máximo em emparelhamento.
- Kruskal não pode formar ciclo, mesmo que a aresta seja barata.
- Prim escolhe menor aresta saindo de T, não a menor global do grafo.
- No residual, arco reverso existe quando já existe fluxo positivo.
- Em fluxo com custo, arco reverso tem custo negativo.
- Teoremas de Hamilton são suficientes, não necessários.
- Em coloração de arestas, arestas incidentes não podem repetir cor.