Grafos: fundamentação matemática, problema do caixeiro viajante e das sete pontes

Olá, leitor! Você já parou para pensar de quantas maneiras diferentes é possível fazer um percurso? 

Em um cenário que sua mãe te pede para ir na casa da sua tia entregar uma Tupperware, passar no mercado e comprar os ingredientes para fazer um bolo, passar na padaria, e voltar para casa, você provavelmente tentou traçar as possibilidades para fazer esse percurso no caminho mais rápido possível, certo? Ou, para os que gostam de correr, você possivelmente já pensou em como fazer um percurso passando pelos lugares apenas uma vez, sem repetir nenhum?

Se sim, saiba que em ambos os casos você esbarrou em um problema complexo da matemática e ciência da computação, devido a dificuldade de encontrar um resposta em tempo hábil. 

Na matemática, Esse problema tem duas vertentes, sendo uma o Problema do Caixeiro Viajante (o pedido da sua mãe) e a outra o Problema das Sete Pontes (a corrida sem repetir nenhum ponto).

Problema do Caixeiro Viajante (PCV)

Problema das Sete Pontes (PSP)

Para compreender a diferença entre os dois, entenda que o Problema do Caixeiro Viajante está preocupado em passar por todas as cidades pela rota mais curta (não pode passar pela mesma cidade 2 vezes). Já o Problema das Sete Pontes busca passar por todos os caminhos somente uma vez (pode passar pela mesma cidade 2 vezes).

Nós usamos esses desafios como base para estudar Grafos, um modelo matemático que surgiu com Euler. Um grafo é um conjunto (não vazio) de pontos chamados vértices e linhas chamadas arestas, conectando 1 vértice a outro.

De modo prático, um grafo é composto por dois conjuntos finitos G(V, E), onde 

V(G) = vértices ou nós;

E(G) = arestas (conjunto formado de pares de 2 elementos de V). 

Na imagem abaixo, visualizamos o V(G) sendo os círculos X, Y e Z. Já o E(G) é os traços entre eles.

Imagem da Olimpíada Brasileira de Informática

Grau do Vértice

O grau do vértice corresponde ao número de arestas que incide no vértice. A soma dos graus dos vértices em um grafo é igual ao dobro do número de arestas.

Ne = s/2

Ne = número de arestas

s = soma dos graus dos vértices

Teoremas

Problema das Sete Pontes

Esse problema representa a possibilidade de atravessar cada ponte 1 vez e retornar ao ponto inicial.

• Para passar sem repetição de aresta
• Cada ponto deve ter 2 arestas, 1 de entrada e 1 de saída (ou seja, os pontos devem ter número par de arestas)
• Sem retornar ao ponto de partida
• É possível com os pontos de partida e/ou chegada tendo número ímpar de arestas
• Os outros pontos devem ter número par de arestas 

Problema do Caixeiro Viajante

Aqui explora-se um caminho que passe por todos os pontos 1 vez e retornar ao ponto inicial.

Passeio, Trilha, Caminho e Ciclo

Passeio

É uma sequência de Vértices. Se V e W são consecutivos, sua aresta (E) é v-w.

No caso de arestas paralelas, ou seja, que conectam os mesmos vértices, diferencia-se eles no passeio.

Imagem ilustrativa de grafo

Observe que na imagem, cada aresta possui uma identificação "e" seguido de uma numeração. Isso é usado para diferenciar o a-b, por exemplo. onde poderia ser a-e1-b ou a-e6-b.

Trilha

É um passeio onde todas as arestas são distintas.

Caminho

É um passeio onde todos os vértices são distintos.

OBS: um caminho também pode ser uma trilha e vice-versa.

Ciclo ou Circuito

É uma trilha fechada.

Laços 

Aresta que conecta o vértice a ele próprio.

Arestas Paralelas

Arestas têm os mesmos vértices como extremidades.

Trilha Euleriana

Passa por todas as arestas 1 vez.

Circuito Euleriano

Trilha que começa e termina no mesmo vértice.

Grafo Euleriano

É aquele que contém 1 circuito Euleriano.

Caminho Hamiltoniano

Passa por todos os vértices 1 vez.

Circuito (ciclo) Hamiltoniano

É caminho que começa e termina no mesmo vértice.

Grafo Hamiltoniano

Tem ciclo hamiltoniano.

Grafo Conexo

Se existir um caminho entre qualquer par de vértices.

Grafo Regular

Todos os vértices têm o mesmo grau.

Para calcular o número de vértices em um grafo regular, com apenas o número de arestas e o grau do vértice, usa-se a seguinte fórmula:

V = (2 . E)/Gv

V = vértices

E = arestas

Gv = grau do vértice

Grafo completo

Existe aresta entre cada par de vértice.

Cálculo do Número de Arestas

Ne = n(n -1)/2

Teorema do Grafo Euleriano

É um grafo euleriano se o grafo é conexo e se todos os seus vértices tem grau par.

Teorema da Trilha Euleriana

É uma trilha euleriana se o grafo é conexo e se tiver 0 ou 2 vértices de grau ímpar (1 no início e 1 chegada).

Grafos Direcionados

As arestas têm direção, que podem ser representadas por pares ordenados (U, V), onde começa em U e termina em V.

OBS: Pares ordenados: (1, 6) ≠ (6, 1) / Conjuntos: {1, 6} = {6, 1}

Algoritmo Guloso

Esse algoritmo constrói uma solução por uma sequência de decisões para o melhor cenário de curto prazo.

Nele, não há garantia de que levará a 1 solução ótima. É importante destacar que na maioria das vezes não leva a uma solução ótima, pois esse algoritmo preocupa-se muito mais com a solução local do que a global.

Este é o conteúdo introdutório para o estudo da matemática discreta, matéria presente no curso de Sistemas de Informação.

Também há um resumo manuscrito que fiz na época que estudei este assunto. Toque no botão a seguir para baixá-lo!

Resumo feito em 3 de novembro de 2024, para Fundamentos Matemáticos para Sistemas de Informação I (Matemática Discreta)