O que é um grafo: vértices e arestas

Pontos e ligações, nada mais

Desenhe alguns pontos numa folha e ligue alguns deles com traços. Pronto, você desenhou um grafo. Os pontos têm nome técnico: vértices. Os traços também: arestas. Toda a teoria dos grafos, que sustenta desde o roteador do seu Wi-Fi até o aplicativo que traça o caminho até o trabalho, nasce dessa dupla simples. Um vértice representa uma coisa (uma pessoa, uma parada de ônibus, um site) e uma aresta representa uma relação entre duas dessas coisas (são amigos, há uma linha entre as paradas, um site aponta para o outro). Quando dois vértices estão ligados por uma aresta, dizemos que eles são vizinhos, ou adjacentes, e a quantidade de arestas que saem de um vértice é o seu grau.

A grande diferença para a árvore, que você viu no módulo passado, é a liberdade. Na árvore, cada nó tinha um pai só e o desenho descia sempre em um sentido, sem nunca se cruzar. No grafo não há essa disciplina: qualquer vértice pode se ligar a qualquer outro, um vértice pode ter muitos vizinhos, e os caminhos podem se fechar em círculo. Esse círculo tem nome: ciclo. Um ciclo é um caminho que sai de um vértice, passa por outros e volta ao ponto de partida sem repetir arestas. Árvores nunca têm ciclos; grafos, quase sempre têm. É essa liberdade que torna o grafo a estrutura certa para representar redes de verdade, onde as relações vão e voltam.

A árvore é só um grafo bem comportado

Se o grafo aceita qualquer ligação, e a árvore só aceita ligações que descem sem se cruzar, então a árvore é um tipo particular de grafo, o mais organizado deles. Formalmente, uma árvore é um grafo conexo (dá para chegar de qualquer vértice a qualquer outro) e sem ciclos, com um vértice eleito raiz. Tire a exigência de não ter ciclo e a de ter raiz, e você volta ao grafo geral. Pensar assim ajuda: tudo que você aprendeu sobre nós e ligações na árvore continua valendo, só que agora sem as amarras. Um vértice pode ter vários vizinhos como um nó tinha vários filhos, mas também pode se ligar de volta a um vizinho de quem já veio, algo que a árvore proibia. Essa é a única mudança conceitual, e ela abre um mundo de problemas novos.

Por que essa estrutura tão simples é tão poderosa

A força do grafo vem justamente da sua simplicidade. Como qualquer relação entre pares de coisas cabe no molde vértice-aresta, uma quantidade enorme de problemas diferentes vira o mesmo problema disfarçado. Achar o caminho mais curto no mapa, sugerir amigos numa rede social, ordenar tarefas com dependências, descobrir se dois computadores conseguem se comunicar: por baixo, tudo isso é caminhar por um grafo. Aprender a estrutura uma vez rende em dezenas de aplicações. Nas próximas aulas você vai ver que existem tipos de grafo (com direção, com peso) e formas de guardá-lo na memória, mas a ideia central não muda: pontos e as ligações entre eles.