Descrevendo grafos

Este é um modo 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 "se conhecem" é bidirecional. Por exemplo, como Andreia conhece Gina, isso significa que Gina também conhece Andreia.

Esta rede social é um gráfico. Os nomes são os vértices do gráfico. (Se você estiver falando sobre apenas um dos vértices, é um vértice.) Cada linha é uma aresta, que conecta dois vértices. Denotamos uma aresta que conecta os vértices $u$‍ e $v$‍ pelo par $(u,v)$‍. Como a relação "se conhecem" é bidirecional, este gráfico é não direcionado. Uma aresta não direcionada $(u,v)$‍ é igual a $(v,u)$‍. Mais tarde, vamos aprender sobre gráficos direcionados, nos quais as relações entre os vértices não são necessariamente bidirecionais. Em um gráfico não direcionado, uma aresta entre dois vértices, como o vértice entre Andreia e Gina, é incidente às duas arestas, e dizemos que os vértices conectados por uma aresta são adjacentes, ou vizinhos. O número de arestas incidentes a um vértice é o grau do vértice.

Andreia e Francisco não se conhecem. Suponha que Francisco queira ser apresentado a Andreia. Como podemos conseguir isso? Bem, ele conhece Emília, que conhece Carlos, que conhece Andreia. Dizemos que há um caminho de três arestas entre Francisco e Andreia. Na verdade, esse é o modo mais direto para Francisco conhecer Andreia. Não há caminho entre eles com menos de três arestas. Chamamos 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, isso é chamado ciclo. A rede social contém muitos ciclos. 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 Andreia, mostrado abaixo: Andreia, Carlos, Gina e de volta para Andreia. Que outros ciclos você consegue 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 conhecem uma à outra. Como outro exemplo, vamos representar um mapa rodoviário como um gráfico. Supondo que não existam ruas de mão única, um mapa rodoviário é também um gráfico não direcionado, com cidades como vértices, estradas como arestas e os valores nas arestas indicando as distâncias de cada rodovia. Por exemplo, aqui está um mapa rodoviário (fora de escala) de algumas das rodovias interestaduais no nordeste dos Estados Unidos, com as distâncias ao lado das arestas:

O termo geral que usamos para um número que atribuímos a uma aresta é seu peso, e um gráfico cujas arestas possuem pesos é um gráfico pesado. No caso de um mapa rodoviário, se você quiser encontrar a rota mais curta entre duas localidades, você está procurando por um caminho entre dois vértices com a menor soma de pesos das arestas entre os dois vértices. Assim como nos gráficos não pesados, chamamos um caminho assim de caminho mais curto. Por exemplo, o caminho mais curto entre Nova York e Concord neste gráfico 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 mão única. Aqui está um gráfico que mostra a ordem em que um goleiro de hóquei no gelo pode se vestir:

Agora as arestas, representadas com setas, são direcionadas, e temos um gráfico direcionado. 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 até o suéter indica que a proteção deve ser colocada antes do suéter. Os números ao lado dos vértices mostram uma dos possíveis ordens nas quais colocar o equipamento, de forma que as roupas de baixo vêm primeiro, então as meias, então os shorts de compressão e assim por diante, com a luva de bloqueio vindo por último. Você pode ter notado que este gráfico direcionado em particular não possui ciclos. Chamamos esse tipo de gráfico de gráfico direcionado acíclico, ou gda. É claro, podemos ter gráficos direcionados pesados, como mapas rodoviários com ruas de mão única 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. O número de arestas deixando um vértice é chamado grau de fora, e o número de arestas entrando é chamado grau de dentro

Como você deve imaginar, os gráficos — tanto direcionados quanto não direcionados — têm muitas aplicações na modelagem de relações no mundo real.

Quando trabalhamos com gráficos, é interessante poder falar sobre o conjunto de vértices e o conjunto de arestas. Nós usualmente denotamos o conjunto dos vértices por $V$‍ e o conjunto das arestas por $E$‍. Quando representamos um gráfico ou executamos um algoritmo em um gráfico, muitas vezes queremos usar os tamanhos dos conjuntos dos vértices e das arestas em notação assintótica. Por exemplo, suponha 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 o tamanho de um conjunto. Mas usar essa notação de tamanho de conjunto na forma assintótica é 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 tamanho de conjunto, entendendo que estamos falando sobre tamanhos de conjuntos. Então, em vez de escrever $\mathrm{\Theta }(|V|)$‍, escrevemos apenas $\mathrm{\Theta }(V)$‍. Então, ao invés de escrevermos $\mathrm{\Theta }(\lg |E|)$‍, nós 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 equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.