| Seja G=(V,E) um grafo, d um inteiro positivo fixo, w uma matriz de ordem |E|xd contendo d números naturais associados a cada aresta de G. Um ciclo C é dito d-ímpar se as d somas dos valores correspondentes nas arestas de C são ímpares. Esta definição de ciclo ímpar generaliza a definição sobre a cardinalidade, onde d=1 e w(e,1)=1. A identificação de ciclos ímpares é importante no estudo de politopos associados a conjuntos independentes.
Um conjunto independente em um grafo é um subconjunto de vértices não adjacentes dois a dois. Matematicamente, um conjunto independente pode ser descrito por um vetor inteiro x satisfazendo 0 <= x(u) <= 1 para todo u em V e x(u) + x(w) <= 1 para todo uw em E. Na definição de um multiconjunto estável, o lado direito das inequações é generalizado para: 0 <= x(u) <= a(u) para todo u em V e x(u) + x(w) <= b(u,w) para todo uw em E, onde a e b são vetores inteiros. Ou seja, o vetor x agora é um vetor de multiplicidade dos vértices. Algumas facetas para o politopo associado a essa formulação são definidas por desigualdades de ciclo: para todo ciclo C tal que |C| e b(C) são ímpares, a soma de x(v), com v em C, é menor que (b(C)-1)/2), onde b(C) é a soma de b(u,v), para uv em C.
Identificar se um ponto x satisfaz ou não todas essas desigualdades é equivalente a encontrar um ciclo 2-ímpar de peso mínimo, onde o peso associado a uma aresta uv é 1-x(u)-x(v).
Cheng e Vries (2004) propuseram um algoritmo para encontrar um ciclo d-ímpar de peso mínimo em um grafo G. No algoritmo é criado um novo grafo H baseado em G. Para cada vértice de G são criadas 2^d cópias de H. O mesmo é feito para as arestas. As arestas em H são criadas de tal modo que encontrar um ciclo d-ímpar passando por um vértice v em G é equivalente a encontrar um caminho mínimo entre duas cópias de v em H. Este algoritmo para d=2 foi implementado e foram obtidos resultados computacionais.
Agradeço o apoio do CNPq.
|