Este é um modo de representar uma rede social:
Grafo de 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 grafo. Os nomes são os vértices do grafo. (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 left parenthesis, u, comma, v, right parenthesis. Como a relação "se conhecem" é bidirecional, este grafo é não direcionado. Uma aresta não direcionada left parenthesis, u, comma, v, right parenthesis é igual a left parenthesis, v, comma, u, right parenthesis. Mais tarde, vamos aprender sobre grafos direcionados, nos quais as relações entre os vértices não são necessariamente bidirecionais. Em um grafo 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:
Rede social com o caminho mais curto destacado
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?
Rede social com ciclo destacado
À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 grafo. Supondo que não existam ruas de mão única, um mapa rodoviário é também um grafo 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:
Mapa rodoviário
O termo geral que usamos para um número que atribuímos a uma aresta é seu peso, e um grafo cujas arestas possuem pesos é um grafo 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 grafos não pesados, chamamos um caminho assim de 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 mão única. Aqui está um grafo que mostra a ordem em que um goleiro de hóquei no gelo pode se vestir:
Equipamento de goleiro
Agora as arestas, representadas com setas, são direcionadas, e temos um grafo 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 grafo direcionado em particular não possui ciclos. Chamamos esse tipo de grafo de grafo direcionado acíclico, ou gda. É claro, podemos ter grafos 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 left parenthesis, u, comma, v, right parenthesis, e a ordem dos vértices no par é importante. The number of edges leaving a vertex is its out-degree, and the number of edges entering is the in-degree.
Como você deve imaginar, os grafos — tanto direcionados quanto não direcionados — têm muitas aplicações na modelagem de relações no mundo real.

Tamanhos de grafos

Quando trabalhamos com grafos, é 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 grafo ou executamos um algoritmo em um grafo, 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 é Θ(V) \Theta(|V|) , usando a notação vertical bar, dot, vertical bar 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 Θ(V) \Theta(|V|) , escrevemos apenas Θ(V) \Theta(V) . Similarly, instead of Θ(lgE) \Theta(\lg |E|) , we write Θ(lgE) \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.