Grafos

Um grafo é uma estrutura discreta usada para modelar relações entre objetos. Formalmente, é o par G = (V, E), onde V é um conjunto de vértices (ou nós) e E é um conjunto de arestas que ligam pares de vértices. Em grafos não dirigidos, as arestas são pares não ordenados; em grafos dirigidos, também chamados dígrafos, as arestas são pares ordenados. Grafos podem ser simples (sem laços nem múltiplas arestas) ou mais gerais, como multigrafos ou pseudógrafos, que permitem arestas repetidas e laços.

Os grafos podem ser representados de várias formas. A lista de adjacência associa a cada vértice os vértices vizinhos. A matriz de adjacência usa uma matriz onde a posição (i, j) indica a presença de uma aresta entre i e j. Grafos podem ser ponderados, atribuindo um peso a cada aresta, o que facilita modelar custos ou distâncias. Exemplos de classes comuns incluem grafos completos, grafos bipartidos, grafos regulares e grafos planares.

Principais propriedades incluem o grau de um vértice, que em grafos não dirigidos é o número de arestas incidentes; em grafos dirigidos existem grau de entrada e grau de saída. Conceitos como caminho, circuito, ciclo, conectividade e componentes conectadas ajudam a descrever a estrutura. O isomorfismo de grafos verifica se duas representações são essencialmente iguais. Algoritmos clássicos exploram trajetos e otimizações, como busca em largura (BFS), busca em profundidade (DFS), Dijkstra, Kruskal e Prim.

Os grafos encontram aplicações em ciência da computação, redes de telecomunicações, transporte, redes sociais, química e biologia. A história da teoria dos grafos remonta ao problema das pontes de Königsberg, proposto por Euler no século XVIII, que popularizou o estudo matemático dos grafos. Hoje, eles são fundamentais em modelagem, análise de estruturas e resolução de problemas de conectividade e caminho ótimo.