Conceitos Fundamentais e Algoritmos em Teoria dos Grafos

Análise de Circuitos em Grafos

O Grafo a seguir possui Circuito Euleriano?

Resposta: Não. Para que haja um Ciclo Euleriano, todas as arestas devem ser visitadas uma única vez e todos os nós (vértices) devem possuir grau par.

Definições Essenciais em Teoria dos Grafos

Tipos de Ciclos e Caminhos

• Ciclo Euleriano: Um ciclo em que todas as arestas são visitadas uma única vez. Para existir, todos os vértices devem ter grau par.
• Ciclo Hamiltoniano: Um ciclo que passa por todos os vértices do grafo sem repetir nenhum nó, exceto a origem (Exemplo: Problema do Caixeiro Viajante).

Estruturas e Componentes de Grafos

• Subgrafo: É formado por um subconjunto do conjunto de nós e arestas de outro grafo.
  • Todo conjunto vazio é subconjunto de qualquer conjunto.
  • Todo conjunto é subconjunto de si mesmo.
• Vértices (Nós): São os pontos do grafo.
  • Qualquer vértice de grau zero é um vértice isolado.
  • Qualquer vértice de grau 1 é um vértice pendente.
• Arestas: São as linhas que fazem a ligação de ponto a ponto (vértices).
• Adjacência: Existe uma ligação (aresta) entre os nós.

Classificação de Grafos

• Grafo Conexo e Desconexo: Grafos podem ser conexos ou desconexos (possuem nós, ou conjuntos de nós e arestas isolados entre si).
• Dígrafo (Grafo Direcionado): As arestas determinam um sentido de percorrimento.
  • É importante definir o grau de um nó como: grau de entrada e grau de saída.
• Grafo Ponderado: Os nós ou arestas possuem valores (pesos) associados.
• Grafo Planar: É aquele que pode ser representado no plano de tal forma que suas arestas não se cruzem.
• Grafo Regular (k-regular): Todos os vértices têm o mesmo grau (k).

Aplicações e Algoritmos em Grafos

Aplicações Práticas de Grafos

Grafos são implementados em diversas áreas, incluindo:

• Jogos de Raciocínio
• Realidade Virtual
• Mapas e GPS
• Serviços de Entrega
• Web
• Circuitos Eletrônicos

Heurística

Heurística: Conjunto de regras programadas para se encontrar um resultado. O consumo de tempo e memória da máquina depende da complexidade das regras.

Observações Importantes

h4. Coloração de Mapas em Grafo Planar

Todo e qualquer grafo planar pode ser interpretado e preenchido usando apenas quatro cores, garantindo que áreas vizinhas não possuam coincidência de cor (Teorema das Quatro Cores).

h4. Algoritmos de Caminho Mínimo (Mapas Viários)

Em mapas viários, o algoritmo Dijkstra é geralmente mais eficiente do que Bellman-Ford e IDA (Busca em Profundidade Iterativa):

• Dijkstra: Passa somente em arestas com o menor peso positivo.
• Bellman-Ford: Trata também arestas com pesos negativos.
• IDA (Busca em Profundidade Iterativa): Visita todos os vértices utilizando um conjunto de regras.

h4. Criptografia Usando Circuito Hamiltoniano

Na criptografia, usando o circuito Hamiltoniano, o processo inicia recebendo as informações sobre quais pontos passar. Cada vértice visitado constitui um conjunto de regras armazenadas a serem comparadas com os dados de chegada. Realizam-se os cálculos e, se o resultado for verdadeiro, o processo passa para o próximo ponto orientado.

Estratégias de Busca em Grafos

h4. Busca em Largura (BFS)

Dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolher aquele menos recentemente alcançado na busca (FIFO - First In, First Out).

h4. Busca em Profundidade (DFS)

Dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolher aquele mais recentemente alcançado na busca (LIFO - Last In, First Out).