Introdução
Olá, nesse post iremos discutir um pouco sobre
grafos. Esse é um dos assuntos principais para a transição de iniciante (em olimpíadas de programação) para intermediário (ao meu ver, claro).
Quado eu não sabia ao certo o que era um grafo, ou de outra forma não sabia codificar alguns algoritmos clássicos de grafos, quando alguém falava de grafos/me perguntava sobre o assunto o que eu pensava era:
"Grafos é um assunto muito difícil(principalmente de codificar), que aparece de vez em quando numas questões que eu até sei que envolvem grafos, mas não sei nem pra onde vai na hora de codificar"
Bem, o objetivo desse post é transformar esse pensamento em algo mais estruturado como:
"Grafos não é algo difícil, apenas por ser algo novo e um pouco mais avançado requer alguns conhecimentos prévios e pode levar algum tempo pra se acostumar com a ideia, mas nada de outro mundo. Várias questões abordam grafos, é difícil haver uma competição sem nenhuma questão de grafos. E no momento que você entende os algoritmos, a maioria é tranquilo de entender e de codificar".
Ps: achei que a frase ficaria mais curta, mas isso representa bem a visão que alguém(generalizando, claro) que nunca codificou nada de grafos terá.
Esse post será organizado nos seguintes tópicos:
- Assuntos prévios que devem ser estudados
- Grafos, o que são?
- Grafos, como representar?
- Bibliografia/Sugestão de leituras
Assuntos prévios que devem ser estudados
Então vamos lá, antes de saber o que é um grafo, alguns assuntos que devem ser dominados, ou pelo menos você já deve ter codificado/utilizado, são:
- Recursão
- Estruturas de dados básicas (pilha, fila, fila de prioridade)
- Se sentir seguro na linguagem que utiliza (bibliotecas, sintaxe)
Ps: planejo fazer posts sobre cada tópico e colocarei o link :).
Se você nunca ouviu falar em algum dos assuntos, ou não se sente seguro, aconselho dar uma estudada nisso antes, já que ao meu ver algumas das dificuldades em entender grafos surgem devido a pouca experiência nos assuntos base acima.
Grafos, o que são?
Para maratonas e provas uma definição "suficiente" de grafos é: Uma forma de organizar dados, definida a partir de um conjunto de vértices/nós e um conjunto de arestas são utilizadas para ligar 2 vértices.
Certo... mas para que serve essa representação? Há várias situações onde um grafo é um ótimo modelo estrutural para representar a situação, os exemplos mais clichês, porém também bastante comuns em questões é: estradas e rodovias, redes sociais, rede de amizades, relações de dependências.
Um exemplo de enunciado de uma questão envolvendo grafos é a questão pedágio da OBI 2002:
Como prêmio pela primeira colocação na Olimpíada Brasileira de Informática, Juquinha e sua
família ganharam uma viagem de uma semana à Coréia do Sul. Como o país é deslumbrante, com
tradições, cultura, arquitetura e culinária muito diferentes das do Brasil, o pai de Juquinha, o Sr.
Juca, decidiu alugar um carro para conhecer melhor o país. As estradas(1) são muito bem cuidadas;
todas são de sentido duplo(2), e duas cidades podem ser ligadas diretamente por mais de uma
estrada(3). No entanto, em todas as estradas paga-se um pedágio de valor fixo(4) (há um pedágio em
cada direção, entre duas cidades). Como o Sr. Juca não tem muito dinheiro para gastar, as viagens
com o carro devem ser muito bem planejadas.
Tarefa: Escreva um programa que, conhecidas as cidades(5) e estradas existentes no país, e a cidade onde
Juquinha e sua família estão, encontre cada cidade (que não a cidade onde eles estão) que possa
ser visitada por eles, dada a restrição de que o Sr. Juca deseja pagar no máximo P pedágios (considerando
apenas a viagem de ida)(6).
Onde está o grafo nessa questão? Bem, esse é um exemplo clássico, as estradas são as arestas e as cidades são os vértices.
 |
| Exemplo de estradas representadas por um grafo |
Mas no texto há algumas palavras interessantes que definem o
tipo do grafo, sim existem tipos de grafos! E isso muitas vezes interfere na nossa solução e representação.
Seguem abaixo...
Expressões importantes
Caminho: sequência de vértices tal que de cada vértice existe uma aresta para o seguinte.
Caminho mínimo: menor caminho que liga um vértice à outro(essa definição muda se o grafo por ponderado)
Grau: o grau de um vértice é o número de arestas que saem deste vértice em direção a qualquer outro vértice.
Laços: aresta que liga um vértice a ele mesmo.
Ponto de articulação: vértice cuja remoção desliga um grafo.Vizinhos: vértices ligados.
Ponte: aresta cuja remoção desliga um grafo.Ciclos: caminho que começa e acaba no mesmo vértice.
Componentes: parte conectada de um grafo. (se um grafo é conectado ele só tem 1 componente)
As principais características que definem o grafo
Grafo conectado: existe um caminho de um vértice para qualquer outro.
Grafo desconectado: existe algum vértice que não conseguimos chegar de algum outro vértice.
Grafo esparso: se o número de arestas for muito menor que o número de vértices ao quadrado.
Grafo denso: se o número de arestas for aproximadamente o número de vértices ao quadrado.
Grafo direcionado: as arestas tem direções. Ou seja, a existência de uma aresta de A para B (A e B são vértices) não implica na existência de uma aresta de B para A.
Grafo não direcionado: as arestas não tem direções. Ou seja, a existência entre A e B (A e B são vértices) implica na existência de uma aresta entre B e A.
Grafo ponderado: as arestas tem pesos.
Grafo não ponderado: as arestas não tem pesos, de outra forma: todas as arestas tem o mesmo peso.
Tipos de grafo
Árvore: grafo sem ciclos e conectado.
Floresta: grafo sem ciclos.
Grafo simples: grafo não direcionado, sem laços e há no máximo uma aresta entre 2 vértices.
Grafo regular: todos os vértices tem o mesmo grau.
Grafo bipartido:
Grafo completo: grafo simples onde para cada vértice existe uma aresta conectando este vértice a cada um dos demais. Esse grafo tem n(n-1)/2 arestas, n é o número de vértices.
Há váááários temos específicos como já deu pra perceber. Vão aparecendo mais e mais com o tempo haha, mas ao utilizar e fazer questões você não precisa decorar, vai aprendendo com o tempo, então calma!
Certo, voltando ao texto do exemplo, um desafio: o que cada expressão indexada no texto representa para o grafo que iremos formar?
(1) - arestas
(2) - grafo não direcionado
(3) - não é simples
(4) - não ponderado
(5) - vértices
(6) - E o que ele quer como resposta? O número de vértices cujo caminho mínimo entre 2 pontos é menor ou igual a P.
Comparação: lista de adjacência VS matriz de adjacência
 |
| Lista VS Matriz |
Matriz: em geral ocupa menos memória e se o grafo for denso é uma escolha melhor, fácil e eficiente verificação se há uma aresta entre 2 vértices.
Lista: em geral é mais eficiente no que tange ao tempo, fácil e eficiente verificação de quem são os vizinhos de um certo vértice.
Bibliografia
- https://pt.wikipedia.org/wiki/Teoria_dos_grafos
- http://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/grafos.html
- http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf
- https://www.codechef.com/wiki/tutorial-graph-theory-part-1
- http://noic.com.br/informatica/curso-noic-de-informatica/aula-8-grafos-parte-i-uma-breve-historia-de-grafos/
