Uma relação minimax envolvendo decomposições em orelhas e pesos conservativos

Mario Leston Rey (leston@ime.usp.br)

IME-USP

Sexta-feira, 26 de março de 1999, 15:00

Sala 139, Bloco B, IME-USP

Resumo: Seja G=(V,E) um grafo. Uma decomposição em orelhas de G é uma seqüência G₀, G₁,..., G_t de subgrafos de G onde G₀ consiste de um único vértice e G_i é obtido de G_i-1 adicionando-se um caminho P_i internamente disjunto nos vértices de G_i-1. Uma orelha é ímpar se seu comprimento é ímpar. Uma função peso nas arestas w em {-1,+1} é conservativa se w(C) >= 0 para todo circuito C em G.

Neste seminário provaremos o seguinte teorema devido a András Frank: O número máximo de orelhas ímpares numa decomposição em orelhas de um grafo 2-aresta conexo é igual ao peso mínimo de w(E) sobre todos os pesos {-1,+1} conservativos w de G.