3 - Grafo

Primeiramente é bom registrar que grafo não é gráfico, apesar de os nomes serem parecidos e de o grafo poder ser representado graficamente.

Segundo João Dovicchi:

Grafos são estruturas matemáticas usadas para representar ideias ou modelos, por intermédio de uma ilustração, gráfico ou esquema.

Estritamente, em matemática, a teoria dos grafos é utilizada para representar o relacionamento entre dois ou mais conjuntos, grandezas ou valores. A representação de um mapa de rotas, redes e outros modelos semelhantes podem ser feita por meio do que se denominam grafos.

Vamos tomar, por exemplo, um mapa de rotas aéreas. Na figura abaixo, nota-se que existem várias rotas de um ponto a outro, por exemplo, de Florianópolis a Brasília existem as possibilidades via Curitiba, via São Paulo ou via Rio de Janeiro. Algumas rotas podem ter mais escalas, por exemplo, pode-se ir a Brasília por São Paulo, passando por Curitiba, Rio e Belo Horizonte. Podemos ter também um voo panorâmico, onde o avião sai de um lugar e volta para o mesmo lugar. Por exemplo, voo de São Paulo para São Paulo, onde o avião sai do aeroporto de Congonhas sobrevoa a cidade e volta para Congonhas.

Neste exemplo, temos a linha que liga cada dois pontos. Quando esse movimento acontece chamamos de laços. O mapa de rotas contém pontos, que representam as cidades, e estão ligados por linhas, que representam as rotas aéreas. Cada um dos pontos de um grafo é denominado nó e cada uma das ligações é denominada arcos.