Otimização em Grafos: Problemas e Modelos

Problema do Carteiro Chinês

Este problema surge porque o grafo construído para representar o percurso nem sempre é um grafo euleriano. Portanto, nem sempre é possível computar diretamente um ciclo euleriano (um caminho que percorre todas as arestas exatamente uma vez e retorna ao início).

O critério para um grafo ser euleriano é que todos os seus vértices tenham grau par. No contexto do problema do carteiro, os vértices representam cruzamentos e as arestas representam ruas. Se nem todos os cruzamentos tiverem um número par de ruas conectadas a eles (ou seja, se existirem vértices de grau ímpar), o grafo não será euleriano.

Uma estratégia para transformar o problema em euleriano é modificar o grafo. Isso envolve identificar todos os vértices de grau ímpar e adicionar novas "arestas" (que representam a repetição de trechos de ruas existentes) até que todos os vértices no novo grafo possuam grau par. É importante notar que não se trata de construir novas ruas físicas; as "novas arestas" no modelo são, na verdade, trajetos que utilizam ruas já existentes. O objetivo é complementar o grafo para que ele se torne euleriano e um ciclo euleriano possa ser encontrado.

Essa necessidade de modificação ocorre porque não é possível garantir que todos os vértices originalmente tenham grau par. Uma abordagem comum é:

• Identificar os vértices de grau ímpar.
• Se houver apenas dois, duplicam-se as arestas que formam o caminho mais curto entre eles.
• Se houver mais de dois vértices de grau ímpar, utiliza-se o conceito de emparelhamento perfeito de custo mínimo nesses vértices. Um algoritmo é usado para encontrar os caminhos mais curtos entre os pares de vértices de grau ímpar que foram emparelhados, e as arestas desses caminhos são duplicadas no grafo original para torná-lo euleriano.

Alocação de Férias de Funcionários: Modelo Anual

Modelagem do problema utilizando grafos para alocação anual de férias:

• G(V,A): Representa o grafo do problema.
• M = {m | m é um mês do ano}
• F = {f | f é um funcionário da empresa}
• V = F ∪ M ∪ {s, t} (onde s é o nó fonte e t o nó sumidouro, representando o início e o fim do fluxo)
• A: Conjunto de arestas, incluindo:
  • Arestas do nó fonte s para cada funcionário f ∈ F, com capacidade usualmente 1 (ou o número de períodos de férias que um funcionário pode tirar).
  • Arestas de um funcionário f para um mês m, (f, m), se o funcionário f deseja tirar férias no mês m. Capacidade 1.
  • Arestas de cada mês m ∈ M para o nó sumidouro t, com capacidade igual ao número máximo de funcionários que podem tirar férias naquele mês (o texto original menciona "peso 2", interpretado aqui como capacidade 2).

Solução Proposta: Fluxo Máximo

Com base no modelo acima, podemos usar o conceito de fluxo máximo para determinar a alocação de férias. As capacidades das arestas são definidas da seguinte forma:

• Cada aresta saindo do nó fonte para um funcionário tem capacidade 1 (assumindo que cada funcionário tira um período de férias).
• Cada aresta de um funcionário para um mês de interesse tem capacidade 1.
• Cria-se um vértice fonte (s) e um vértice sumidouro (t).
• Cada mês do conjunto M é ligado ao vértice sumidouro t por uma aresta com capacidade igual ao limite de funcionários em férias para aquele mês (no exemplo original, "peso 2", significando que até 2 funcionários podem tirar férias em um dado mês).

O valor do fluxo máximo de s para t indicará o número máximo de solicitações de férias que podem ser atendidas respeitando as restrições.

Alocação de Férias de Funcionários: Modelo Quinzenal

Modelagem do problema utilizando quinzenas:

• G(V,A): Representa o grafo do problema.
• Q = {Janeiro₁, Janeiro₂, ..., Dezembro₂} (Conjunto de todas as quinzenas do ano)
• F = {f | f é um funcionário da empresa}
• V = F ∪ Q ∪ {s, t} (onde s é o nó fonte e t o nó sumidouro)
• A: Conjunto de arestas, incluindo:
  • Arestas do nó fonte s para cada funcionário f ∈ F, com capacidade 1.
  • Arestas de um funcionário f para uma quinzena q ∈ Q, (f, q), se f tem interesse em tirar férias na quinzena q. Capacidade 1.
  • Arestas de cada quinzena q ∈ Q para o nó sumidouro t. A capacidade dessas arestas varia:
    • Capacidade 20 para quinzenas dos meses de verão.
    • Capacidade 10 para as demais quinzenas do ano.

Solução Proposta: Fluxo Máximo

Com base neste modelo, podemos usar o conceito de fluxo máximo:

• Atribui-se capacidade 1 para cada aresta que parte do nó fonte para os funcionários.
• Atribui-se capacidade 1 para cada aresta de um funcionário para uma quinzena de interesse.
• É criado um vértice fonte (s) e um vértice sumidouro (t).
• Todas as quinzenas (elementos de Q) são conectadas ao vértice sumidouro t.
• A capacidade das arestas das quinzenas para o sumidouro é de 20 para as quinzenas dos meses de verão e 10 para as demais quinzenas do ano.

Grafo Hamiltoniano: Definição

Um grafo G é dito hamiltoniano se existe um ciclo em G que visita todos os seus vértices exatamente uma vez, retornando ao vértice inicial para fechar o ciclo. Ou seja, cada vértice aparece apenas uma vez no percurso do ciclo, com exceção do vértice inicial que também é o final.

Algoritmos Relacionados

A seguir, menções a algoritmos e suas características (detalhes adicionais seriam necessários para uma descrição completa):

• Função Maior Primeiro (possivelmente uma variante de algoritmo guloso):
  • Complexidade computacional mencionada: O(n*m). Esta complexidade pode variar dependendo da implementação específica e do problema ao qual se aplica, onde n e m geralmente representam o número de vértices e arestas, ou outras dimensões do problema.
• Coloração Aproximada de Grafos:
  • Refere-se a algoritmos que buscam uma coloração de vértices de um grafo usando um número de cores próximo ao número cromático (o mínimo de cores possível), especialmente útil para grafos onde encontrar a coloração exata é um problema NP-difícil.