Teoria dos Grafos — Vértices, Arestas e Conceitos Básicos

A teoria dos grafos é o estudo dos grafos, que são estruturas formadas por vértices e arestas. Um vértice é um objeto, e uma aresta mostra uma relação entre dois objetos.

Se você está procurando o básico de teoria dos grafos, comece por esta ideia: um grafo é uma forma simples de modelar conexões. Pessoas em uma rede social, cidades ligadas por estradas e páginas da web conectadas entre si podem ser representadas por grafos.

O Que Um Grafo Significa Na Matemática

Em um grafo não direcionado, uma aresta diz que dois vértices estão conectados, e essa conexão não tem direção. Se $A$ está ligado a $B$, então $B$ também está ligado a $A$.

Em um grafo direcionado, as arestas têm direção, então $A \to B$ e $B \to A$ são afirmações diferentes. Muitos exemplos introdutórios usam grafos simples não direcionados, o que significa sem laços e sem arestas repetidas entre os mesmos dois vértices.

Essa condição importa porque as definições costumam ser apresentadas primeiro no caso simples e não direcionado. Se o tipo de grafo muda, o significado dos termos também pode mudar.

Termos Básicos de Teoria dos Grafos Que Você Precisa Primeiro

Vértices e arestas

Um vértice é o elemento que você quer acompanhar. Uma aresta é a conexão que você quer acompanhar.

Se um grafo modela cidades e estradas, as cidades são os vértices e as estradas são as arestas.

Grau

Em um grafo não direcionado, o grau de um vértice é o número de arestas que incidem nele.

Se uma cidade tem estradas para outras três cidades, seu grau é $3$.

Caminho

Um caminho é uma sequência de vértices em que cada par consecutivo está conectado por uma aresta.

Se existe um caminho de um vértice até outro, você pode ir de um ao outro seguindo as arestas.

Ciclo

Um ciclo é um caminho que começa e termina no mesmo vértice. Na definição básica mais comum, nenhum outro vértice se repete.

Um ciclo mostra que existe um laço fechado no grafo.

Grafo conexo e componentes conexas

Um grafo não direcionado é conexo se todo vértice pode ser alcançado a partir de qualquer outro por algum caminho.

Se isso não acontece, o grafo se divide em componentes conexas. Cada componente é uma parte conexa do grafo.

Exemplo Resolvido: Um Grafo Pequeno

Suponha que um grafo tenha vértices $A$, $B$, $C$, $D$ e $E$, com arestas

$$AB,\ AC,\ BC,\ CD$$

Isso forma um triângulo em $A$, $B$ e $C$, uma aresta extra de $C$ até $D$ e um vértice isolado $E$.

Agora as ideias principais ficam fáceis de ver.

Os graus são

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Existe um caminho de $A$ até $D$:

$$A-C-D$$

Existe um ciclo:

$$A-B-C-A$$

O grafo não é conexo porque $E$ não pode ser alcançado a partir dos outros vértices. Então o grafo tem duas componentes conexas: uma contendo $A,B,C,D$ e outra contendo apenas $E$.

Este único exemplo mostra como grau, caminho, ciclo, vértices isolados e componentes conexas se encaixam.

Uma Verificação Rápida: Soma Dos Graus

Para qualquer grafo finito não direcionado,

$$\sum \deg(v) = 2|E|$$

Isso funciona porque toda aresta toca exatamente duas extremidades, então cada aresta acrescenta $1$ a duas contagens de grau.

No exemplo acima, a soma dos graus é

$$2+2+3+1+0=8$$

e o número de arestas é $4$, então

$$2|E| = 2 \cdot 4 = 8$$

Essa é uma verificação útil quando você conta graus à mão. Se os números não baterem, algo está errado.

Erros Comuns em Teoria dos Grafos

Confundir vértices com arestas

Vértices são os objetos. Arestas são as relações entre eles.

Esquecer que tipo de grafo você tem

Uma afirmação que é verdadeira para um grafo simples não direcionado pode precisar ser ajustada para um grafo direcionado ou para um grafo que permite laços.

Tratar um caminho como se fosse um ciclo

Um caminho não precisa voltar ao ponto de partida. Um ciclo precisa.

Ignorar vértices isolados

Um vértice com grau $0$ ainda faz parte do grafo. Ele pode mudar se o grafo é conexo ou não.

Onde Os Conceitos Básicos de Teoria dos Grafos São Usados

Essas ideias aparecem em redes de computadores, planejamento de rotas, escalonamento, sistemas de recomendação e redes sociais. O contexto muda, mas as mesmas perguntas continuam aparecendo: o que está conectado, o que pode ser alcançado e onde estão os ciclos?

É por isso que a teoria dos grafos aparece cedo tanto em matemática discreta quanto em ciência da computação.

Tente Um Grafo Parecido

Desenhe quatro vértices $P$, $Q$, $R$ e $S$. Adicione as arestas $PQ$, $QR$, $RS$ e $SP$.

Depois responda a três perguntas: qual é o grau de cada vértice, o grafo é conexo e o grafo contém um ciclo?