Definição de grafo

Esta é uma forma de representar uma rede social:

Uma linha entre os nomes de duas pessoas significa que elas se conhecem. Se não houver uma linha entre dois nomes, as pessoas não se conhecem. A relação "conhecerem-se" é bidirecional. Por exemplo, como a Andreia conhece a Gina, isso significa que a Gina também conhece a Andreia.

Esta rede social é um grafo. Os nomes são os vértices do grafo. (Se te referires apenas a um dos vértices, é um vértice.) Cada linha é uma aresta, que liga dois vértices. Denotamos uma aresta que liga os vértices $u$‍ e $v$‍ pelo par $(u,v)$‍. Como a relação "conhecerem-se" é bidirecional, este grafo é não orientado. Uma aresta não orientada $(u,v)$‍ é igual a $(v,u)$‍. Mais tarde, vamos aprender sobre grafos orientados ou dígrafos, nos quais as relações entre os vértices não são necessariamente bidirecionais. Num grafo não orientado, uma aresta entre dois vértices, como o vértice entre a Andreia e a Gina, é incidente às duas arestas, e dizemos que os vértices ligados por uma aresta são adjacentes, ou vizinhos. O número de arestas incidentes a num vértice é o grau do vértice.

A Andreia e o Francisco não se conhecem. Supõe que oFrancisco quer ser apresentado à Andreia. Como podemos conseguir isso? Bem, ele conhece a Emília, que conhece o Carlos, que conhece a Andreia. Dizemos que há um caminho de três arestas entre o Francisco e a Andreia. Na verdade, esse é o modo mais direto para o Francisco conhecer a Andreia. Não há nenhum caminho entre eles com menos de três arestas. Designamos o caminho entre dois vértices e que possui o menor número de arestas de caminho mais curto. Destacamos esse caminho mais curto em particular abaixo:

Quando um caminho vai de um vértice em particular de volta para ele mesmo, designa-se circuito ou ciclo. A rede social contém muitos circuitos. Um deles sai de Andreia e passa por Carlos, Emília, Jorge, Hélio e Liliana antes de voltar para Andreia. Há um ciclo mais curto que contém a Andreia, que se apresenta a seguir: Andreia, Carlos, Gina e de volta para Andreia. Que outros ciclos consegues encontrar?

Às vezes, atribuímos valores numéricos às arestas. Por exemplo, na rede social, podemos usar valores para indicar quão bem duas pessoas se conhecem uma à outra.Outro exemplo é quando pretendemos representar um mapa rodoviário como um grafo. Supondo que não existem ruas de sentido único, um mapa rodoviário é também um garfo não orientado, com cidades como vértices, estradas como arestas e os valores nas arestas indicam as distâncias entre cada cidade. Por exemplo, aqui está um mapa rodoviário (não está à escala) de algumas das estradas interestaduais no nordeste dos Estados Unidos, com as distâncias ao lado das arestas:

O valor que atribuímos a uma aresta designa-se por peso, e um grafo cujas arestas possuem pesos é um grafo ponderado ou grafo pesado. No caso de um mapa rodoviário, se quiseres encontrar a rota mais curta entre duas localidades, estás a procurar por um caminho entre dois vértices com a menor soma de pesos das arestas entre os dois vértices. Assim como nos grafos não ponderados, designamos um caminho assim por caminho mais curto. Por exemplo, o caminho mais curto entre Nova York e Concord neste grafo sai de Nova York, passa por New Haven, Hartford, Sturbridge, Weston e Reading e chega em Concord, totalizando 289 milhas.

A relação entre os vértices nem sempre é bidirecional. Em um mapa rodoviário, podem existir ruas de sentido único. Aqui está um grafo que mostra a ordem em que um jogador de hóquei no gelo se poderia vestir:

Agora as arestas, representadas com setas, são direcionadas, e temos um grafo direcionado ou orientado. Aqui, as direções mostram que peças de equipamento devem ser colocadas antes de outras peças. Por exemplo, a aresta que vai da proteção peitoral (chest pad) até à sweater indica que a proteção deve ser colocada antes do sweater. Os números ao lado dos vértices mostram uma das possíveis ordens segundo a qual o jogador deve vestir o equipamento, de forma que as roupas de baixo (undershorts) vêm primeiro, depois as meias (socks), os calções de compressão (compression shorts) e assim por diante, com a luva de bloqueio (blocker) por último. Deves ter reparado que este grafo orientado em particular não possui ciclos. Designamos este tipo de grafo de grafo direcionado acíclico, ou gda. É claro, podemos ter grafos direcionados pesados, como mapas rodoviários com ruas de sentido único e distâncias.

Usamos terminologias diferentes com arestas direcionadas. Dizemos que uma aresta direcionada deixa um vértice e entra em outro. Por exemplo, uma aresta direcionada deixa o vértice do protetor peitoral e entra no vértice do suéter. Se uma aresta direcionada deixa o vértice $u$‍ e entra no vértice $v$‍, a denotamos por $(u,v)$‍, e a ordem dos vértices no par é importante. Tem-se o número de arestas que saem do vértice e o número de arestas que entram no vértice.

Como podes imaginar, os grafos — tanto orientados como não orientados — têm muitas aplicações na modelação de relações no mundo real.

Quando trabalhamos com grafos, é interessante falarmos sobre o conjunto de vértices e o conjunto de arestas. Usualmente denotamos o conjunto dos vértices por $V$‍ e o conjunto das arestas por $E$‍. Quando representamos um grafo ou executamos um algoritmo num grafo, muitas vezes queremos usar a dimensão dos conjuntos dos vértices e das arestas. Por exemplo, supõe que queremos falar sobre um tempo de execução que é linear no número de vértices. Falando estritamente, deveríamos dizer que ele é $\mathrm{\Theta }(|V|)$‍, usando a notação $|\cdot |$‍ para denotar a dimensão de um conjunto. Mas usar essa notação de dimensão de conjunto na forma assintótica (linguagem de programação) é desajeitado, então adotamos a convenção de que em notação assintótica, e apenas em notação assintótica, abandonamos a notação de dimensão de conjunto, dado que estamos a falar sobre dimensões de conjuntos. Então, em vez de escrever $\mathrm{\Theta }(|V|)$‍, escrevemos apenas $\mathrm{\Theta }(V)$‍. Da mesma forma, em vez de $\mathrm{\Theta }(\lg |E|)$‍, escrevemos $\mathrm{\Theta }(\lg E)$‍.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipa do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.