Hoje vamos estudar uma das estruturas mais fundamentais da computação e da matemática: os grafos. Eles estão presentes em redes sociais, mapas, sistemas de recomendação, análise de circuitos, e muito mais. Um grafo é uma abstração que modela relações entre objetos. Formalmente, definimos um grafo \(G = (V, E)\), onde \(V\) é um conjunto de vértices (ou nós) e \(E\) é um conjunto de arestas (ou arcos) que conectam pares de vértices.

Definição e tipos de grafos

Os grafos podem ser classificados de várias maneiras. Quando as arestas possuem uma direção (ou seja, a ordem entre os vértices importa), temos um grafo direcionado (ou digrafo). Caso contrário, o grafo é não direcionado. Em um grafo não direcionado, a aresta \(\{u, v\}\) é equivalente a \(\{v, u\}\). Em um digrafo, a aresta \((u, v)\) é diferente de \((v, u)\).

Outra classificação importante é quanto à presença de arestas múltiplas ou laços. Um grafo simples não possui laços (arestas que ligam um vértice a ele mesmo) nem arestas paralelas. Já um multigrafo permite arestas paralelas (duas ou mais arestas entre o mesmo par de vértices).

Grau de um vértice

O grau de um vértice \(v\) em um grafo não direcionado é o número de arestas incidentes a \(v\). Em grafos direcionados, distinguimos grau de entrada (número de arestas que chegam) e grau de saída (número de arestas que partem). O grau total é a soma dos dois. O conceito de grau é útil para diversas propriedades, como o lema do aperto de mãos (handshaking lemma): a soma dos graus de todos os vértices é igual ao dobro do número de arestas.

Caminhos, ciclos e conectividade

Um caminho em um grafo é uma sequência de vértices onde cada par consecutivo está conectado por uma aresta. Se o caminho começa e termina no mesmo vértice e não repete arestas, temos um ciclo. Grafos que não possuem ciclos são chamados acíclicos. A conectividade é uma propriedade fundamental: um grafo é conexo se existe um caminho entre qualquer par de vértices. Caso contrário, o grafo é formado por componentes conexos, que são subgrafos maximais conexos.

Em grafos direcionados, a conectividade é mais complexa: falamos em conectividade forte (existe caminho orientado entre qualquer par) e conectividade fraca (ignorando a orientação).

Árvores

Uma árvore é um grafo conexo acíclico. As árvores são estruturas extremamente importantes em ciência da computação: representam hierarquias, estruturas de dados (como árvores binárias de busca), algoritmos de ordenação, compressão, etc. Uma propriedade clássica: uma árvore com \(n\) vértices possui exatamente \(n-1\) arestas. Além disso, qualquer grafo conexo com \(n-1\) arestas é uma árvore. Se adicionarmos uma única aresta a uma árvore, criamos exatamente um ciclo.

Principais conceitos sobre grafos

  • Ordem: número de vértices do grafo.
  • Tamanho: número de arestas do grafo.
  • Subgrafo: um grafo obtido a partir de um subconjunto de vértices e arestas do grafo original.
  • Isomorfismo: dois grafos são isomorfos se existe uma bijeção entre seus vértices que preserva as arestas.
  • Grafo bipartido: grafo cujos vértices podem ser particionados em dois conjuntos independentes, sem arestas internas.
  • Grafo completo: grafo onde todos os pares de vértices estão conectados por uma aresta (denotado \(K_n\)).

Representação computacional

Na prática, podemos representar grafos em computadores de duas maneiras principais: matriz de adjacência e lista de adjacência. A matriz de adjacência é uma matriz \(n \times n\) onde a posição \((i,j)\) indica se existe aresta entre os vértices \(i\) e \(j\). A lista de adjacência armazena para cada vértice uma lista de seus vizinhos. A escolha depende da densidade do grafo e das operações necessárias.

Aplicações de grafos

Os grafos estão por toda parte. Em redes de computadores, os roteadores e suas conexões formam um grafo. Em redes sociais, os usuários são vértices e as amizades são arestas. Mapas e sistemas de navegação usam grafos para calcular rotas. Algoritmos de busca em largura (BFS) e busca em profundidade (DFS) são a base para resolver problemas como encontrar o menor caminho, verificar conectividade, detectar ciclos, e muito mais. A teoria dos grafos também é fundamental em áreas como inteligência artificial, otimização combinatória e bioinformática.

Perguntas Frequentes

O que é um grafo?

Um grafo é uma estrutura matemática composta por um conjunto de vértices e um conjunto de arestas que conectam esses vértices. É usado para modelar relações e redes.

Qual a diferença entre grafo direcionado e não direcionado?

Em um grafo não direcionado, as arestas não têm direção: a conexão entre dois vértices é simétrica. Em um grafo direcionado, cada aresta tem um sentido, ou seja, uma origem e um destino.

O que é uma árvore?

Uma árvore é um grafo conexo e acíclico. Ela possui \(n\) vértices e exatamente \(n-1\) arestas. É amplamente utilizada em estruturas de dados e algoritmos.

Como calcular o grau de um vértice?

Em um grafo não direcionado, o grau é o número de arestas incidentes ao vértice. Em um digrafo, somamos o grau de entrada e o grau de saída.

O que é um grafo completo?

Um grafo completo é aquele em que todos os pares de vértices estão diretamente conectados por uma aresta. O grafo completo com \(n\) vértices é denotado por \(K_n\) e possui \(\frac{n(n-1)}{2}\) arestas.

Com isso, terminamos mais uma aula da disciplina. Os grafos são um tópico vasto e essencial; nos próximos dias veremos algoritmos em grafos, como busca em largura, busca em profundidade e aplicações práticas. Até a próxima!