Grafos fantásticos e onde habitam: uma introdução à teoria dos grafos
E aí, pssoas! Esse texto foi adaptado do artigo escrito pela Vaidehi Joshi, que com o projeto basecs criou uma série de artigos que exploram o básico da computação: fundamentos, estruturas de dados e algoritmos. Estou estudando grafos nesse semestre e achei uma leitura extremamente relevante e simples de entender para um assunto que me assombra desde o início do curso. As figuras estavam tão bem feitas que nem mexi em nada! xD Vamos lá?
Várias coisas no mundo nunca chegariam a existir se não houvesse um problema que precisasse ser resolvido. É óbvio que essa verdade se aplica a tudo, mas cara, isso é muito mais óbvio no mundo da ciência da computação.
Alguém precisava de uma forma para acompanhar a ordem das coisas, então brincaram com isso e criaram estruturas de dados diferentes até encontrarem uma que funcionasse melhor para o problema em específico que estavam tentando resolver. Outra pessoa precisava de uma forma boa de armazenar dados, então brincaram com diferentes sistemas numéricos até descobrirem o que funcionava melhor para o tipo de informação que queriam conter. As pessoas precisavam de uma boa forma de descrever e processar tarefas, então descobriram uma forma de construir coisas em cima das ferramentas que tinham e criaram uma forma de fazer malabarismo com todas as coisas que aquele sistema precisava fazer, em determinado tempo.
É claro que a ciência da computação não é a única área a inovar e criar coisas, mas acho que isso é feito de uma forma única: as inovações da ciência da computação dependem e são criadas a partir de suas próprias abstrações.
Nesse artigo vamos entender uma estrutura de dados bem conhecida. Na computação, as árvores, na verdade são um subconjunto de algo que você já deve ter ouvido falar: os grafos. Mas, para realmente saber por que usamos grafos e o que eles são, vamos precisar mergulhar nas raízes de algo que se origina da matemática discreta: a teoria dos grafos.
Se é sua primeira vez estudando sobre matemática discreta, não tenha medo — tamo junto! Vamos enfrentar esse desafio juntos — e tentar não perder nossa sanidade no processo.
Grafos fantásticos e onde habitam
Quando começamos a pesquisar por estruturas não-lineares, aprendemos sobre sua característica mais fundamental: que seus dados não seguem uma ordem — pelo menos, não uma ordem numérica óbvia, como vemos nos arrays ou listas ligadas. Árvores começam com um nó raiz e podem se conectar a outros nós, o que significa que podem conter subárvores dentro deles. Árvores são definidas por algumas regras: um nó raiz pode ou não se conectar a outros, mas o mais importante é que todos eles partem de um lugar em específico. Algumas árvores têm regras mais específicas, como as árvores de busca binária, que só podem ter duas ligações com dois nós por vez.
Mas se fizéssemos algo bem louco e simplesmente… jogássemos essas regras pela janela? Bem, acontece que sim, podemos fazer isso! Só que aí não estaríamos mais lidando com árvores — estaríamos lidando com algo chamado de grafo.
Árvores nada mais são do que tipos restritos de grafos, só que com muito mais regras para seguir. Uma árvore sempre será um grafo, mas nem todos os grafos serão árvores.
Então, o que faz uma árvore ser diferente de um grande guarda-chuva de grafos?
Bem, para começar, uma árvore pode fluir em apenas uma direção, do nó raiz para os nós folhas ou nós filhos. Uma árvore também pode ter conexões de via única — um nó filho só pode ter um pai, e uma árvore não pode ter nenhum loop ou ligações cíclicas.
Com os grafos, todas essas restrições vão direto para a janela. Os grafos não têm nenhum conceito de nó “raiz”. E por que teriam? Nós podem ser conectados de qualquer forma possível. Sério mesmo. Um nó pode ser conectado a outros cinco! Grafos também não têm dessa noção de fluxo “unidirecional” — ao invés disso, eles podem ter uma direção, ou podem simplesmente não ter direção nenhuma. Ou, para complicar ainda mais as coisas, eles podem ter algumas ligações que têm direção e outras que não têm! Mas não vamos falar disso aqui hoje.
Vamos começar com a parte simples.
Grafos com direção e sem direção
Certo, então já sabemos que os grafos quebram todas as regras que conhecemos. No entanto, existe uma característica que todo grafo deve ter: todo grafo sempre precisa ter pelo menos um nó. Assim como as árvores precisam de pelo menos um nó para serem consideradas “árvores”, um grafo precisa de pelo menos um nó para ser considerado um “grafo”. Um grafo com apenas um nó costuma ser conhecido como grafo singleton, mas não vamos falar sobre ele aqui.
A maioria dos grafos que vamos ver são um pouco mais complicados. Mas não se preocupe — não vamos falar sobre os grafos super complicados hoje. E, pode acreditar, alguns grafos realmente são complicados!
Ao invés disso, vamos dar uma olhada em dois tipos de grafos que são bem simples de identificar, e também é uma questão bem comum na teoria dos grafos: grafos direcionados/dirigidos e não-direcionados/não-dirigidos.
Como já sabemos, não existem regras em relação à forma que um nó se conecta a outro nó em um grafo. As arestas (às vezes referidas como ligações) podem se conectar aos nós de qualquer forma possível.
Os tipos diferentes das arestas são muito importantes quando pensamos em reconhecer e definir grafos. De fato, esse é um dos maiores e mais óbvios diferenciadores entre um grafo e outro: os tipos de arestas que ele tem. Para a maioria dos casos (com exceção de um, que não vamos falar sobre hoje), os grafos podem ter dois tipos de arestas: uma aresta que tem uma direção ou fluxo, e uma aresta que não tem direção ou fluxo. Nos referimos a essas arestas como direcionadas/dirigidas e não-direcionadas/não-dirigidas, respectivamente.
Em uma aresta direcionada, dois nós estão conectados de forma bem específica. No exemplo abaixo, o nó A se conecta ao nó B; existe apenas uma forma de viajar entre esses dois nós — apenas uma direção que podemos ir. É bem comum se referir a esse nó de onde estamos começando como o nó origem, e o nó que estamos viajando como o nó destino. Em uma aresta direcionada, só podemos viajar da origem para o destino, e nunca da forma contrária.
No entanto, é uma história totalmente diferente com arestas não-direcionadas. Em uma aresta não-direcionada, o podemos viajar pelos dois sentidos. Sendo assim, o caminho entre os dois nós é bidirecional, o que significa que os nós de origem e destino não são fixos.
A distinção é muito importante, porque as arestas de um grafo determinam como o grafo é chamado. Se todas as arestas de um grafo são direcionadas, ou seja, apontam para um vértice, o grafo é chamado de grafo dirigido, ou dígrafo. Se todas as arestas do grafo não são direcionadas, o grafo é chamado de — é isso mesmo que você pensou — grafo não-dirigido! Quem diria, hein?
Isso tudo é super legal, mas nesse ponto queremos saber duas coisas — de onde toda essa coisa de grafo veio, exatamente? E… por que deveríamos ligar para isso?
Vamos investigar.
Não faça movimentos bruscos: agora estamos na terra dos grafos
A ciência da computação adora emprestar coisas. Mais especificamente, ela empresta vários conceitos da lógica e da matemática. E acontece que é esse mesmo caso com os grafos.
A estrutura de dados do grafo como conhecemos na computação realmente vem da matemática, assim como o estudo dos grafos, que é chamado de teoria dos grafos.
Na matemática, os grafos são uma forma de representar formalmente uma rede, que é basicamente uma coleção de objetos que estão todos conectados entre si.
Como podemos ver, quando os cientistas da computação aplicaram a teoria dos grafos no código (e implementaram os grafos como estruturas de dados), eles não mudaram muita coisa. Então, muitos dos termos que usamos para descrever e implementar os grafos são exatamente os mesmos termos que vamos ver nas referências matemáticas da teoria dos grafos.
Por exemplo: em termos matemáticos, podemos descrever grafos como pares ordenados. Lembra a matemática do ensino médio, quando aprendemos sobre coordenadas de pares ordenados (x, y)? É quase a mesma coisa aqui, com uma diferença: ao invés de x e y, as partes de um grafo consistem em: v para vértices e e para suas arestas.
A definição formal e matemática para o grafo é justamente essa: G = (V, E). É só isso, mesmo! Sério. Juro juradinho.
Uma introdução bem breve à teoria dos grafos:
Grafos são uma forma de representar formalmente uma rede ou coleção de objetos conectados.
Na matemática, os grafos são definidos como pares ordenadores com duas partes: vértices + arestas.
Mas qual é a definição do grafo?
G = (V, E), onde V é um conjunto de nós (também chamados de vértices) e E é um conjunto de arestas, também chamadas ligações.
Mas peraí — e se nosso grafo tiver mais de um nó e mais de uma aresta? Na real… ele quase sempre vai ter várias arestas se tiver mais de um nó. Como raios essa definição funciona?
Bem, ela funciona porque esse par ordenado — (V, E) — na verdade, é composto de dois objetos: um conjunto de vértices, e um conjunto de arestas.
Beleza, faz mais sentido para mim agora. Mas ficaria bem mais claro se tivesse um exemplo que de fato tenha a definição de um grafo! Vamos fazer isso, então. No exemplo abaixo, temos um grafo não-dirigido, com 8 vértices e 11 arestas.
(Formalmente) definindo um grafo
8 vértices/nós
11 arestas/ligações
As definições de arestas em E são pares desordenados!
G=(V,E) é a notação matemática para definir grafos.
Um grafo G é um par ordenado de um conjunto V de vértices e E de arestas.
Um par ordenado é um par de objetos matemáticos nos quais a ordem dos objetos no par importa.
Então o que está acontecendo aqui?
Bem, escrevemos nossos pares ordenados (V, E), mas por cada um desses itens ser um objeto, tivemos que escrevê-los também. Definimos V como um conjunto desordenado de referências para os nossos 8 vértices. A parte “desordenada” é muito importante aqui, porque se lembre, diferentemente das árvores, não há hierarquia de nós! Isso significa que não queremos ordená-los, já que a ordem não importa aqui.
Também tivemos que definir o E como um objeto, que contém um grupo de objetos de arestas dentro dele. Note novamente que nossos objetos de aresta também estão desordenados. Por que isso acontece? Bem, que tipo de grafo ele é? Existe uma direção ou fluxo? Existe um sentido fixo de “origem” e “destino”?
Não, não existe! Esse é um grafo não-dirigido, o que significa que as arestas são bidirecionais e o nó origem e destino não são fixos. Então, cada um dos nossos objetos de aresta também não pares desordenados.
Essa particularidade, é claro, nos leva a perguntar: e se esse fosse um grafo dirigido? Hora de ver outro exemplo! Aqui está um grafo dirigido, com três vértices e três arestas:
Mas os grafos dirigidos?
Nossas arestas seriam diferentes?
Essas definições de arestas são pares ordenados, porque a direção importa!
A forma que definimos os vértices aqui não parecem diferentes, mas vamos dar uma olhada mais de perto na nossa definição de aresta. Nossos objetos de aresta nesse caso são pares ordenados, porque a direção de fato importa nesse caso! Já que só podemos viajar do nó origem para o nó destino, nossas arestas devem estar ordenadas, já que o nó origem é o primeiro dos dois nós de cada uma das nossas definições de aresta.
Legal, então é assim que definimos os grafos. Mas… quando nós de fato usamos os grafos? Bem, você provavelmente já usou um hoje. Você só não sabe disso ainda! Hora de mudar isso.
Sempre vai existir um grafo perto de você
Os grafos estão ao nosso redor, nós é que nem sempre vemos como eles são.
De fato, só de estar lendo esse post, você está literalmente em um grafo nesse exato momento. A web é uma estrutura gigantesca de grafos! Quando clicamos entre os websites e navegamos entre as URLs, estamos simplesmente navegando por um grafo. Às vezes esses grafos têm nós com arestas que não são dirigidas — posso ir e voltar de uma página da web para a outra — e outras são dirigidas — só posso ir da página A para a página B, e nunca de forma contrária.
Só que existe um exemplo ainda melhor que ilustra maravilhosamente nossas interações diárias com grafos: as redes sociais.
O Facebook, uma rede social enorme, é um tipo de grafo. E se pensarmos mais sobre como ele funciona, vamos começar a entender melhor como podemos defini-lo, e exatamente que tipo de grafo ele é. No Facebook, se eu te adicionar como amigo, você precisa aceitar meu pedido. Não é possível eu ser sua amiga na rede social sem você também ser meu ou minha amiga. A relação entre dois usuários (leia-se: nós ou vértices nos termos de grafos!) é bidirecional. Não há conceito de nó “origem” nem de um nó “destino” — ao invés disso, você é meu ou minha amiga e eu também sou sua amiga.
Consegue adivinhar qual tipo de grafo em que o Facebook é implementado?
Se você chutou grafo não-dirigido, acertou! Muito bem! As relações são bidirecionais. Então, se fôssemos definir a rede de amigos do Facebook como um grafo, todas as suas arestas acabariam sendo pares desordenados.
O Twitter, por outro lado, trabalha de forma bem diferente do Facebook. Eu posso te seguir, mas você não precisa me seguir de volta. No exemplo abaixo? Eu sigo a Beyoncé, mas ela definitivamente (e infelizmente) não me segue de volta.
Podemos representar o Twitter como um grafo dirigido. Cada aresta pode representar uma relação de via única. Quando me segue no Twitter, você cria uma aresta no grafo com a sua conta como nó de origem, e minha conta como nó de destino.
Então o que acontece quando te sigo de volta? Eu mudo a aresta que você criou quando me seguiu? Ele de repente vira bidirecional? Bem, não, porque eu poderia deixar de te seguir em algum momento. Quando eu te sigo de volta no Twitter, eu crio uma segunda aresta, com a minha conta como nó de origem e a sua como nó de destino.
O mesmo modelo se aplica ao Medium, já que ele te permite seguir e deixar de seguir autores! De fato, esse modelo de network está por todo lugar. E é basicamente isso: uma vez que abstraímos todas as camadas, lá estará um grafo. E que conceito poderoso ele tem, não é mesmo?
Referências
Diversos livros foram escritos falando somente sobre grafos. Com certeza eu não conseguiria cobrir tanta informação a ponto de preencher um livro, mas isso não quer dizer que você não pode continuar aprendendo sobre grafos! Preencha sua mente com mais da fantástica teoria de grafos, começando com os links abaixo.
1. Difference between trees and graphs, Poonam Dhanvani
2. What’s the difference between the data structure tree and graph?, StackOverflow
3. Applications of Graph Theory In Computer Science: An Overview, S.G.Shirinivas et. al.
4. Graph Traversal, Professor Jonathan Cohen
5. Data Structures: Introduction To Graphs, mycodeschool
