Grafos, o que são?

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:

1. Recursão
2. Estruturas de dados básicas (pilha, fila, fila de prioridade)
3. 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.

Grafo 1

Grafo 2

Grafo 3

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.

Grafos, como representar?

Há 2 maneiras principais de representar grafos: matriz de adjacência e lista de adjacência. 
Cada uma tem seus benefícios e situações em que são mais vantajosas, ao final da explicação faremos uma tabela que expõe essa informação de maneira objetiva. Mas antes vamos falar desses modos de representação e como funcionam.
Bem, sabemos que temos que representar vértices e arestas. Mas como fazer isso?

Matriz de adjacência

A matriz de adjacência consiste em uma matriz N x N onde N é o número de vértices do grafo e as linhas representam de onde a aresta sai e as colunas para onde as arestas vão. Geralmente o valor 1 em uma certa linha:coluna representa que existe uma aresta da linha para a coluna, e o valor 0 a ausência dessa aresta. Se o grafo for ponderado é utilizado um valor muito grande(infinito) para representar a ausência e o peso da aresta representa a existência da ligação.

Grafo VS Matriz de adjacência - 1

Grafo VS Matriz de adjacência - 2

Lista de adjacência

A lista de adjacência representa cada vértice como uma lista de vértices(inteiros ou chars). Se existir uma ligação de um vértice A para um vértice B, então na lista do vértice A teremos o vértice B. Ou seja, na lista de cada vértice temos seus vizinhos. Se o grafo for ponderado em vez de termos uma lista de vértices teremos uma lista de pares onde o primeiro termo é o identificador do vértice e o segundo o peso da aresta.

Grafo VS Lista de adjacência - 1

Grafo VS Lista de adjacência - 2

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/