Uma introdução à teoria dos grafos

Como modelar conexões em pares entre objetos? 

Com uma estrutura matemática chamada grafo. E essa é a essência da teoria dos grafos – o estudo dos grafos.  

Os elementos fundamentais da teoria dos grafos são os vértices (também chamados de nós) e as arestas (também chamadas de ligações). Um vértice representa uma entidade ou ponto individual dentro de um grafo, enquanto uma aresta indica uma conexão ou relacionamento entre dois vértices. Juntos, esses componentes formam a estrutura de um grafo, que pode ser direcionado ou não direcionado, ponderado ou não ponderado, dependendo da natureza específica dos relacionamentos modelados.

Em ciência da computação, a teoria dos grafos sustenta muitos algoritmos e estruturas de dados usadas para representar redes como a internet, redes sociais e sistemas de comunicação. Ela também oferece ferramentas para resolver problemas de conectividade, busca de caminhos e otimização, e é a base para entender diversas estruturas e conceitos matemáticos como árvores, ciclos e grafos planares.

Neste artigo, vamos ensinar o que você precisa saber para começar com teoria dos grafos.  

Criado pelo autor usando Midjourney

O que é teoria dos grafos?

A teoria dos grafos é um ramo da matemática que estuda as propriedades e aplicações dos grafos. Um grafo define um conjunto de objetos chamados vértices (ou nós) conectados por arestas (ou ligações). 

O objetivo principal da teoria dos grafos é entender a estrutura desses grafos e explorar problemas relacionados à conectividade, caminhos e otimização de redes.

Ao analisar esses relacionamentos, a teoria dos grafos nos permite obter insights sobre inúmeros problemas do mundo real em diversas áreas.

De onde veio a teoria dos grafos?

As origens da teoria dos grafos remontam ao século XVIII com o trabalho do matemático suíço Leonhard Euler. A solução de Euler para o problema das pontes de Königsberg, em 1736, é considerada um dos primeiros problemas da teoria dos grafos. Esse problema envolvia encontrar um percurso a pé pela cidade de Königsberg que cruzasse cada uma de suas sete pontes exatamente uma vez. A abordagem de Euler lançou as bases para o que mais tarde se tornaria o estudo formal dos grafos.

Nos séculos XIX e XX, a teoria dos grafos se desenvolveu significativamente com contribuições de matemáticos como Carl Friedrich Gauss, que explorou propriedades de poliedros, e de pesquisadores posteriores que formalizaram conceitos e desenvolveram algoritmos para problemas relacionados a grafos. 

O advento da ciência da computação em meados do século XX acelerou ainda mais o crescimento da teoria dos grafos, levando à sua ampla aplicação em algoritmos computacionais, análise de redes e estruturas de dados.

Conceitos fundamentais da teoria dos grafos

Entender os fundamentos da teoria dos grafos é a base para explorar tópicos mais avançados na área. Para começar, vamos estabelecer alguns alicerces… 

Grafos como pares ordenados

Um grafo é formalmente definido como um par ordenado G = (V, E), em que:

• V é um conjunto de vértices (ou nós), representando as entidades individuais no grafo.
• E é um conjunto de arestas (ou ligações), representando as conexões entre pares de vértices.

Vértices (V) e arestas (E)

• Vértices (V): são as unidades ou pontos fundamentais de um grafo. Cada vértice representa uma entidade ou um local na estrutura modelada.

• Arestas (E): são as conexões ou relacionamentos entre pares de vértices. Cada aresta liga dois vértices, indicando um relacionamento ou caminho entre eles.

Tipos de arestas

• Arestas direcionadas: em um grafo direcionado (ou digrafo), as arestas têm direção, indo de um vértice para outro específico. Essa direção é geralmente representada por uma seta. Arestas direcionadas são úteis para modelar relacionamentos assimétricos, como fluxo de tráfego ou precedência em cronogramas.

• Arestas não direcionadas: em um grafo não direcionado, as arestas não têm direção e simplesmente conectam dois vértices. Esse tipo de grafo é usado para representar relacionamentos simétricos, como amizades mútuas ou conexões em uma rede em que a direção não é relevante.

Terminologia e conceitos básicos em teoria dos grafos

Agora, vamos definir alguns termos e conceitos básicos: 

Vértice (nó)

Representa uma entidade ou ponto individual dentro da estrutura do grafo. Por exemplo, em um grafo de rede social, cada pessoa pode ser representada por um vértice.

Grau de um vértice

O grau de um vértice é o número de arestas conectadas a ele. Isso traz informações sobre sua conectividade e importância dentro do grafo. A melhor forma de visualizar é imaginar uma pessoa, representada como vértice, em uma rede social. Se houver muitas arestas saindo desse vértice, dizemos que ele tem “alto grau”, o que também indica uma pessoa muito influente. Se estivéssemos modelando uma rede de transporte, um nó de alto grau sinalizaria um hub central na rede, conectando-se diretamente ao maior número de locais.   

Caminho

Um caminho em um grafo é uma sequência de vértices em que cada par adjacente é conectado por uma aresta. Eles podem ser simples (sem vértices repetidos) ou gerais (permitindo repetições). Por exemplo, em um grafo com vértices A, B, C e D, um caminho pode ser A → B → C → D, em que cada vértice está conectado ao próximo por uma aresta.

Ciclo

Um ciclo é um caminho que começa e termina no mesmo vértice, sem outras repetições de vértices ou arestas. Ciclos podem ser simples (sem repetição de arestas ou vértices, exceto início e fim) ou gerais. Exemplo: em um grafo com vértices A, B, C e D, um ciclo simples pode ser A → B → C → D → A.

Grafos conectados

Um grafo é conectado se existe um caminho entre todo par de vértices. Em outras palavras, em um grafo conectado, qualquer vértice consegue alcançar qualquer outro por alguma sequência de arestas. Um bom exemplo seria uma rede social em que todos são alcançáveis a partir de qualquer pessoa.

Tipos de grafos

A teoria dos grafos abrange vários tipos de grafos, cada um adequado a diferentes aplicações e análises. Nesta seção, vamos explorar esses tipos, discutir suas estruturas básicas e trazer exemplos de aplicação. Isso vai ajudar você a entender quando usar cada tipo para resolver problemas específicos e modelar cenários reais com precisão.

Grafo simples

Visualização de um grafo simples Fonte: Wikipedia

Um grafo simples não possui arestas múltiplas (mais de uma aresta entre um par de vértices) nem laços (arestas que conectam um vértice a si mesmo). Cada aresta em um grafo simples conecta dois vértices distintos.

Exemplos:

• Uma rede social básica em que cada amizade é representada por um único link entre duas pessoas.
• Um mapa de cidades conectadas por estradas únicas e diretas, sem múltiplas rotas ou autoconexões.

Multigrafos

Visualização de um multigrafo com arestas múltiplas em vermelho e vários laços em azul Fonte: Wikipedia

Um multigrafo permite arestas múltiplas (arestas paralelas) entre o mesmo par de vértices e também pode incluir laços. Esse tipo de grafo pode representar situações em que existem múltiplas interações ou conexões entre entidades.

Exemplos:

• Uma rede de transporte em que várias companhias aéreas operam voos entre as mesmas cidades.
• Uma rede de comunicação com múltiplos canais conectando o mesmo par de nós de comunicação.

Grafos ponderados

Visualização de um grafo ponderado Fonte: Hyperskill

Em um grafo ponderado, cada aresta tem um peso ou custo associado, que representa uma medida quantitativa como distância, tempo ou capacidade. Grafos ponderados são usados para modelar problemas em que as arestas têm intensidades ou custos diferentes.

Aplicações:

• Em um mapa de cidades conectadas por estradas, os pesos podem representar distâncias ou tempos de viagem entre cidades.
• Em um problema de otimização de rede, os pesos podem representar largura de banda ou custo de links de comunicação.

Grafos direcionados (digrafos)

Visualização de um grafo direcionado Fonte: Wikipedia

Um grafo direcionado, ou digrafo, tem arestas com direção específica, ou seja, cada aresta vai de um vértice para outro distinto. A direção geralmente é representada por uma seta, indicando fluxo ou relacionamento unidirecional.

Casos de uso:

• Um diagrama de fluxo de trabalho em que as tarefas precisam ser concluídas em uma ordem específica.
• A estrutura de links da web, em que hiperlinks apontam de uma página para outra, representando uma conexão unidirecional.

Grafos não direcionados

Visualização de um grafo não direcionado Fonte: Baeldung

Em um grafo não direcionado, as arestas não têm direção. Uma aresta simplesmente conecta dois vértices, e o relacionamento é mútuo ou bidirecional. A ordem dos vértices em uma aresta não importa.

Exemplos:

• Uma rede de amigos em que a amizade é mútua e as conexões são bidirecionais.
• Um mapa rodoviário não direcionado em que as estradas conectam cidades nos dois sentidos, sem especificar direção.

Teoria dos grafos de árvores

Uma árvore é um tipo de grafo conectado e acíclico, ou seja, não contém ciclos. Uma árvore com $$n$$ vértices tem exatamente $$n−1$$ arestas. Todo par de vértices em uma árvore é conectado por exatamente um caminho, o que garante que haja um caminho único entre quaisquer dois vértices.

Veja um resumo rápido das propriedades de uma árvore: 

• Conectada. Existe um caminho entre qualquer par de vértices.
• Acíclica. Não há ciclos, o que garante que não existem laços fechados.
• Caminho único. Há exatamente um caminho entre quaisquer dois vértices, o que implica conectividade mínima.
• Número de arestas. Uma árvore com $$n$$ vértices tem $$n−1$$ arestas.
• Subárvore: qualquer subconjunto de uma árvore, inclusive um único vértice, é em si uma árvore, chamada de subárvore.
• Folhas. Vértices com exatamente uma aresta são chamados de folhas (leaf nodes). São os pontos terminais da árvore.

Como as árvores diferem de outros grafos? 

Ao contrário dos grafos gerais, árvores não contêm ciclos. Isso significa que qualquer grafo com ciclos não pode ser classificado como árvore. 

Uma árvore com $$n$$ vértices tem exatamente $$n−1$$ arestas, enquanto grafos gerais podem ter um número variável de arestas, incluindo múltiplas arestas e autoloops. Outra diferença: árvores são sempre conectadas, enquanto grafos gerais podem ser desconectados, consistindo em vários componentes que podem ser, cada um, uma árvore. 

Além disso, em uma árvore há exatamente um caminho entre quaisquer dois vértices, diferente de outros grafos, nos quais podem existir múltiplos caminhos entre vértices, principalmente em grafos com ciclos ou arestas múltiplas.

Aplicações

Árvores são fundamentais tanto na teoria quanto na prática de computação e organização de dados. Elas oferecem soluções extremamente eficientes para muitos problemas estruturais e algorítmicos. Por exemplo: 

Estruturas de dados

• Árvores binárias: usadas em ciência da computação para organizar dados hierarquicamente. Exemplos incluem árvores de busca binária, que facilitam a recuperação e a ordenação rápidas de dados.
• Heaps: um tipo de árvore binária usado em filas de prioridade para gerenciar e recuperar com eficiência o maior ou o menor elemento.
• B-Trees: usadas em bancos de dados e sistemas de arquivos para recuperação e armazenamento eficientes, com suporte a inserções, exclusões e buscas.

Design de redes

• Roteamento: árvores são usadas em protocolos de roteamento de redes (como spanning trees) para determinar o caminho mais eficiente para transmissão de dados.
• Broadcast: no design de redes, estruturas em árvore ajudam no broadcast eficiente de dados, garantindo que a informação chegue a todos os nós com o mínimo de redundância.

Representação de hierarquias

• Sistemas de arquivos: sistemas de arquivos costumam usar árvores para representar diretórios e subdiretórios, refletindo a organização hierárquica dos arquivos.
• Organogramas: árvores são usadas para modelar hierarquias organizacionais, mostrando estruturas de reporte e relações entre cargos.

Parsing e análise de sintaxe

• Árvores de sintaxe abstrata (ASTs): usadas em compiladores e interpretadores para representar a estrutura sintática do código-fonte. ASTs facilitam a checagem de sintaxe e a otimização de código.

Aplicações da teoria dos grafos

A teoria dos grafos tem aplicações amplas em várias áreas. Ela é crucial para resolver problemas complexos e otimizar sistemas. Exemplos disso aparecem nas aplicações a seguir: 

Ciência da computação: redes, algoritmos e estruturas de dados

A teoria dos grafos é a base para projetar e analisar sistemas de rede, desenvolver algoritmos e estruturar dados em ciência da computação. Por exemplo, redes dependem intensamente da teoria dos grafos para modelar e gerenciar conexões entre dispositivos. Em especial, topologias de rede são representadas como grafos para otimizar transmissão de dados e roteamento. 

Algoritmos como Dijkstra e Kruskal são usados para resolver, respectivamente, problemas de menor caminho e de árvore geradora mínima. Além disso, a teoria dos grafos sustenta estruturas de dados como listas e matrizes de adjacência, essenciais para manipulação e recuperação eficientes de dados.

Biologia: modelagem de redes biológicas

A teoria dos grafos também é fundamental em biologia. Ela é usada para modelar e analisar redes biológicas complexas, como: 

• Redes de interação proteína-proteína
• Vias metabólicas
• Redes regulatórias gênicas

Essas redes são representadas como grafos em que vértices denotam entidades biológicas (por exemplo, proteínas, genes) e arestas representam interações ou relações entre elas. 

Essa abordagem ajuda pesquisadores a entender relações intrincadas em sistemas biológicos, prever resultados funcionais e identificar possíveis alvos para desenvolvimento de fármacos.

Ciências sociais: análise de redes sociais

Nas ciências sociais, a teoria dos grafos é usada para analisar redes sociais, em que indivíduos são representados como vértices e suas interações ou relacionamentos aparecem como arestas. 

Essa análise ajuda a entender estruturas sociais, padrões de influência e dinâmicas de comunidade. Ao aplicar conceitos como centralidade e conectividade, pesquisadores identificam influenciadores-chave, estudam a disseminação de informação e analisam comportamentos sociais.

Transporte: fluxo de tráfego e planejamento urbano 

Muita gente não sabe, mas ruas, cruzamentos e rotas de transporte são modelados como grafos para: 

• Otimizar o fluxo de tráfego
• Reduzir congestionamentos
• Melhorar o planejamento de rotas. 

Algoritmos baseados em grafos ajudam a projetar redes de transporte eficientes, gerir sistemas de transporte público e planejar a infraestrutura urbana. Ao analisar essas redes, os planejadores tomam decisões embasadas para melhorar mobilidade e conectividade nas cidades.

Passo a passo para construir e analisar um grafo simples

Você já dominou o básico e entendeu as aplicações da teoria dos grafos. 

Agora, está pronto para criar e analisar seu próprio grafo simples. Para facilitar, dividimos este passo a passo em duas partes: 

• Construção 
• Análise

O ponto mais lógico para começar é a construção – vamos nessa… 

Construindo um grafo simples

Passo 1: defina o problema. 

Suponha que queremos modelar uma pequena rede de amigos em uma rede social. 

Podemos usar a biblioteca NetworkX em Python, criada para análise de redes, para modelar isso. 

Vamos começar criando um grafo: 

# Importar bibliotecas 
import networkx as nx # Análise de redes
import matplotlib.pyplot as plt # Visualização de dados
import pydot # Interface Python para Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Criar um grafo
graph = nx.Graph() 

Passo 2: identifique os vértices. 

Na nossa rede social fictícia, temos quatro pessoas: Alice, Bob, Carol e Dave. Essas pessoas serão representadas como vértices no grafo – lembre-se: isso representa uma entidade ou um local na estrutura modelada.

Veja como criar os vértices em Python:

# Adicionar nós 
# graph.add_node("Alice") --> Adiciona um nó por vez
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Adiciona vários nós

Passo 3: determine as arestas. 

Suponha que as conexões de amizade sejam as seguintes:

• Alice é amiga de Bob e Carol.
• Bob é amigo de Alice e Dave.
• Carol é amiga de Alice.
• Dave é amigo de Bob.

Isso significa que esses relacionamentos formam as arestas:

• Alice-Bob
• Alice-Carol
• Bob-Dave

Veja como definir as arestas em Python: 

# Adicionar arestas
# graph.add_edge("Alice", "Bob") --> Adiciona uma aresta por vez
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Garantindo que todas as arestas descritas estejam incluídas
                     ]) # Adiciona várias arestas

Passo 4: desenhe o grafo.

Depois de definir os vértices e as arestas, podemos desenhar o grafo para visualizar os relacionamentos. O snippet abaixo cria uma representação gráfica da rede com vértices e arestas rotulados:

# Visualizar o gráfico
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()

Saída: isso vai gerar um grafo mostrando as conexões entre Alice, Bob, Carol e Dave, conforme descrito.

Esse código gera o seguinte grafo: 

Um grafo simples modelando uma rede social [criado pelo autor]

Se quiser modelar sua própria rede social, faça uma cópia deste DataLab Notebook e personalize como preferir. 

Analisando o grafo simples

Passo 1: verifique a conectividade. 

Como conseguimos percorrer de qualquer vértice a qualquer outro por alguma sequência de arestas, o grafo é conectado. 

Para visualizar melhor, aqui está o caminho entre cada par de vértices: 

• Alice para Bob: aresta direta.
• Alice para Carol: aresta direta.
• Alice para Dave: via Bob.
• Bob para Carol: via Alice.
• Bob para Dave: aresta direta.
• Carol para Dave: via Alice e Bob.

 Passo 2: determine o grau de cada vértice.

Lembre que definimos o grau de um vértice como “o número de arestas conectadas a ele”. Aplicando isso ao nosso exemplo, temos: 

• Alice = grau 2 (conectada a Bob e Carol)
• Bob = grau 2 (conectado a Alice e Dave)
• Carol = grau 1 (conectada a Alice)
• Dave = grau 1 (conectado a Bob)

Cada grau é determinado contando-se o número de arestas associadas a cada vértice, com base nas amizades fornecidas.

Passo 3: identifique caminhos e ciclos.

Um caminho entre Alice e Dave pode ser Alice → Bob → Dave.

O grafo não tem ciclos, pois não há caminhos que retornem ao vértice inicial sem refazer passos.

Passo 4: encontre a centralidade.

Alice e Bob são mais centrais nesta rede, pois cada um se conecta a três outros vértices. Carol e Dave são menos centrais, conectando-se a apenas um outro vértice.

Conclusão

A teoria dos grafos oferece um arcabouço robusto para examinar e resolver relacionamentos e estruturas complexas presentes em diversas áreas. Ao entender conceitos centrais como vértices, arestas e diferentes tipos de grafos, e explorar suas aplicações práticas, você pode obter insights valiosos para otimizar sistemas e resolver problemas reais.

À medida que você aprofunda seus estudos, lembre-se: os princípios de teoria dos grafos não são apenas teóricos — eles são essenciais para enfrentar desafios do mundo real, melhorar a conectividade e aumentar a eficiência de sistemas. Um bom domínio de teoria dos grafos vai aprimorar sua capacidade de resolver problemas e oferecer uma visão mais profunda dos sistemas interconectados ao seu redor.

Para desenvolver ainda mais seu entendimento, confira estes materiais avançados que expandem o que cobrimos neste artigo: 

• Uma introdução completa a Graph Neural Networks (GNNs) 
• Otimização de grafos com NetworkX em Python
• Tutorial de classificação com árvores de decisão em Python