Poliedro dos emparelhamentos perfeitos para grafos

Todos os grafos neste capítulo são não-dirigidos. Por isso, diremos apenas grafo, deixando subentendido o adjetivo não-dirigido. Usaremos a abreviatura ep para a expressão emparelhamento perfeito. (Consulte o índice remissivo e os apêndices para conferir as definições de termos técnicos.)

10.1 O poliedro dos ep's fracionários

Considere o pl $(1)$ do capitulo 9, que é uma representação grosseira do problema do ep mínimo (problema 9.A) num grafo $G$. O pl consiste em encontrar um vetor real $(x_e : e\in E)$ que \begin{equation}\label{lp:bipartite-min-cost-pm-bis} \begin{split} \text{minimize} \quad cx & \\ \text{sob as restrições} \quad x(\cut(v)) & \ = \ 1 \quad \text{para cada $v$ em $V$}\\ x_e & \ \geq \ 0 \quad \text{para cada $e$ em $E$,} \end{split} \end{equation}

sendo $V:=V(G)$ e $E:=E(G)$. O conjunto de todas as soluções viáveis do pl é conhecido como poliedro dos ep's fracionários (= fractional perfect matching polyhedron) de $G$ e denotado por $\FPM(G)$.

É óbvio que o vetor característico de todo ep de $G$ está em $\FPM(G)$. Mas o poliedro representa mal o conjunto de ep's de $G$. Em primeiro lugar, $\FPM(G)$ pode não ser vazio mesmo que $G$ não tenha ep algum, como no caso de um grafo completo com 3 nós, por exemplo. Em segundo lugar, se $G$ tem um ep, o vetor característico $x$ de um ep mínimo pode não minimizar $cx$ em $\FPM(G)$.

Exemplo 10.1: A figura define um grafo $G$ com custos $c$ nas arestas. A tabela mostra vetores $x$ e $x'$ do poliedro $\FPM(G)$. Também mostra uma solução viável $y$ do dual do pl \eqref{lp:bipartite-min-cost-pm-bis} (veja a seção 9.2 do capítulo 9).

\[ \begin{array}[t]{r@{\quad}*{9}r} & ab & bc & ca & de & ef & fd & be \\[0.5ex] c & 10 & 10 & 10 & 10 & 10 & 10 & 20 \\ x & 0.5 & 0.5 & 0.5 & 0.5 & 0.5 & 0.5 & 0 \\ x' & 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{array} \hspace{6ex} \begin{array}[t]{r@{\quad}*{1}{r}} & y \\[0.5ex] a & 5 \\ b & 5 \\ c & 5 \\ d & 5 \\ e & 5 \\ f & 5 \end{array} \]

O vetor $x$ é solução ótima do pl \eqref{lp:bipartite-min-cost-pm-bis} (note que as folgas de $x$ e $y$ são complementares) mas não representa um ep. O vetor $x'$ representa um ep mínimo em $G$ mas não é solução ótima do pl (observe que $cx' > cx$).

Grafos bipartidos

O poliedro $\FPM(G)$ representa muito bem o conjunto dos ep's de $G$ se $G$ é bipartido. Com efeito, nesse caso, (a) $\FPM(G)$ é vazio se e somente se $G$ não tem ep's e (b) os vértices (veja a seção B.2 do apêndice B) de $\FPM(G)$ são os ep's de $G$. É o que mostraremos a seguir.

O poliedro $\FPM(G)$ é limitado, pois $0\leq x \leq 1$ para cada $x$ no poliedro. Segue daí, que $\FPM(G)$ tem vértices, a menos que seja vazio (veja a seção B.3). Os vértices são caracterizados pelo seguinte lema:

Esboço da prova: Adote as abreviaturas $V:=V(G)$ e $E:=E(G)$. Seja $x$ um vetor binário de $\FPM(G)$ e $\d$ um vetor em $\R^{E}$ tal que $x+\d$ e $x-\d$ estão $\FPM(G)$. Para toda aresta $e$ tal que $x_e=0$ temos necessariamente $\d_e=0$. Analogamente, temos $\d_e=0$ para toda aresta $e$ tal que $x_e=1$. Portanto, $d=0$. Isso mostra que $x$ é um vértice.

Agora suponha que um vetor $x$ de $\FPM(G)$ não é binário. Seja $E'$ o conjunto das arestas $e$ tais que $0 \lt x_e \lt 1$. Nenhum nó de $G$ tem grau $1$ no subgrafo $(V,E')$. Portanto (veja o lema E.1 no apêndice E), o subgrafo $(V,E')$ tem um circuito, digamos $C=(v_0,e_1,v_1,e_2,\ldots,e_k,v_0)$. Como $G$ é bipartido, $k$ é par. Seja $\epsilon$ um número positivo tal que $x_{e_i} + \epsilon \leq 1$ para cada $i$ ímpar e e $x_{e_i} - \epsilon \geq 0$ para cada $i$ par. Seja $\d$ o vetor indexado por $E$ tal que $\d_{e_i}:=+\epsilon$ para cada $i$ ímpar, $\d_{e_i}:=-\epsilon$ para cada $i$ par, e $\d_{e}:=0$ para toda aresta $e$ que não pertence a $C$. Então $\d$ não é nulo e tanto $x+ \d$ quanto $x-\d$ pertencem a $\FPM(G)$. A existência de um tal $\d$ mostra que $x$ não é vértice. ■

Prova: Suponha que o pl \eqref{lp:bipartite-min-cost-pm-bis} é viável, ou seja, que o poliedro $\FPM(G)$ não é vazio. Como o poliedro é limitado, o corolário C.3 no apêndice C garante que, qualquer que seja $c$, alguma solução ótima $x$ do pl é vértice do poliedro. Pelo lema 10.1, $x$ é binário. ■

Podemos resumir assim o estudo do poliedro $\FPM(G)$: se $G$ é um grafo bipartido então $\FPM(G)$ é o casco convexo dos ep's de $G$ (veja o teorema D.3 do apêndice D). Em particular, $\FPM(G)$ é um politopo.

Exercícios 10.1

★ Complete os detalhes da prova do lema 10.1.
★ Teorema de Birkhoff versus fluxo de custo mínimo. Prove o teorema de Birkhoff (teorema 10.2) a partir do teorema fluxo viável de custo mínimo (teorema 4.4 na seção 4.4).
★ Mostre que o enunciado do teorema de Birkhoff (teorema 10.2) também vale para alguns grafos não bipartidos. Isto é, exiba um grafo não bipartido tal que, para todo vetor $c$ com valores em $\R$, o valor ótimo do pl \eqref{lp:bipartite-min-cost-pm-bis} é igual ao custo de um ep mínimo. [CCPS 5.23]
★ Seja $G$ um grafo bipartido que não satisfaz as condições de Tutte (teorema 7.3, capítulo 7). Mostre que o correspondente pl \eqref{lp:bipartite-min-cost-pm-bis} não tem solução viável.

10.2 Vértices meio-binários

Como vimos acima, os vértices do poliedro $\FPM(G)$ não são, em geral, binários. Curiosamente, os vértices são quase binários, como mostraremos a seguir.

Diremos que um vetor $x$ é meio-binário (= half-integer) se $x_e \in \conj{0, 0.5, 1}$ para todo $e$ em $E(G)$. Para qualquer vetor $x$ e qualquer número real $\lambda$, seja $E_{\lambda}(x)$ o conjunto $\conj{e\in E(G) : x_e=\lambda}$.

Prova do se: Seja $x$ um vetor meio-binário em $\FPM(G)$ tal que cada componente conexa do grafo induzido $G[\Ehalf(x)]$ é um circuito ímpar. Para mostrar que $x$ é um vértice de $\FPM(G)$, seja $\d$ um vetor em $\R^E$ tal que $x+\d$ e $x-\d$ estão ambos em $\FPM(G)$. É fácil verificar que $\d_e=0$ para toda aresta $e$ em $E_0(x)$ e toda aresta $e$ em $E_1(x)$. A análise das arestas em $\Ehalf(x)$ é mais delicada. Seja $(v_0,e_1,v_1,\ldots,e_k,v_0)$ um circuito ímpar cujas arestas estão todas em $\Ehalf(x)$. Suponha que $\d_{e_1}>0$. Como $x(\cut(v_1))=1$ e $x$ é meio-binário, temos necessariamente $\d_{e_{2}} = -\d_{e_1}$. Se continuarmos esse raciocício ao longo do circuito, veremos que $\d_{e_1} \lt 0$, uma vez que $k$ é ímpar. Essa contradição mostra que $\d_e=0$ para todo $e$ em $\Ehalf(x)$. Concluímos assim que $\d=0$. Isso mostra que $x$ é um vértice de $\FPM(G)$.

Prova do somente se: Construa um grafo $G'$ da seguinte maneira. Para cada nó $v$ de $G$, o grafo $G'$ tem dois nós, $v'$ e $v''$. Para cada aresta $e=vw$ de $G$, o grafo $G'$ tem duas arestas: $e':=v'w''$ e $e'':=v''w'$. É claro que $G'$ é bipartido.

Seja $\xbar$ um vértice de $\FPM(G)$. Conforme o corolário C.4 do apêndice C, existe um vetor de custos $c$ tal que $\xbar$ é a única solução ótima do programa linear $\max \conj{cx : x\in \FPM(G)}$. Seja $c'$ o vetor definido por $c'_{e'}:=c'_{e''}:=c_e$ para cada aresta $e$ de $G$. Todos os vértices de $\FPM(G')$ são binários de acordo com o lema 10.1. Conforme o corolário C.3, existe um vértice $x'^*$ de $\FPM(G')$ que maximiza $c'x'$ para $x'$ em $\FPM(G')$. Seja $x^*$ o vetor de $\FPM(G)$ definido por $x^*_e := \frac{1}{2}(x'^*_{e'}+x'^*_{e''})$ para cada aresta $e$ de $G$. É claro que $x^*$ é meio-binário. Ademais, $x^*$ maximiza $cx$ para $x$ em $\FPM(G)$. Logo, $\xbar=x^*$ e portanto $\xbar$ é meio-binário.

A prova tem um último passo. Se $x$ é um vetor meio-binário em $\FPM(G)$ então é claro que as componentes de $G[\Ehalf(x)]$ são circuitos. Se $x$ é vértice, o mesmo argumento usado na prova do lema 10.1 mostra que não podemos ter circuitos pares. ■

Exercícios 10.2

Mostre que o poliedro $\FPM(G)$ não é vazio se e somente se existe um conjunto de arestas e circuitos ímpares em $G$ tal que todo nó de $G$ pertence a exatamente um dos circuitos ou a exatamente uma das arestas, mas não ambos. [CCPS 5.22]
Um conjunto emparelhável (= matchable set) em um grafo $G$ é o conjunto dos nós saturados por algum emparelhamento de $G$. Seja $S$ o conjunto de vetores característicos de conjuntos emparelháveis de um grafo bipartido $G:=(V,E)$ com bipartição $(P,Q)$. Considere as condições
\[ \begin{array}{rcl@{\quad}l} x(C) - x(N(C)) & \leq & 0 & \mb{para todo $C\subseteq P$} \\ x(P) - x(Q) & = & 0 & \\ x_v & \geq & 0 & \mb{para todo $v\in V$} \\ x_v & \leq & 1 & \mb{para todo $v\in V$,} \end{array} \]

onde $N(C)$ é o conjunto de todos os nós em $Q$ que são vizinhos de nós em $C$. Prove que se $x\in \convex(S)$ então $x$ safisfaz essas condições. [CCPS 6.5]
Dado um grafo $G:=(V,E)$ e um vetor $y$ em $\R^E$, considere as seguintes condições:
\[ \begin{array}{rcl@{\quad}l} y(\cut(v)) & = & x_v & \mb{para todo $v\in V$} \\ y_e & \geq & 0 & \mb{para todo $e\in E$.} \end{array} \]

No exercício anterior, prove que $x\in \convex(S)$ se e somente se $x\leq 1$ e existe $y$ que satisfaz as condições acima. [CCPS 6.6]

10.3 O poliedro dos ep's

Considere agora o pl $(7)$ do capitulo 8, que representa o problema 9.A do ep mínimo num grafo $G$. O pl consiste em encontrar um vetor real $(x_e : e\in E)$ que \begin{equation}\label{lp:min-cost-pm-bis} \begin{split} \text{minimize} \quad cx & \\ \text{sujeito a} \quad x(\cut(v)) & \ = \ 1 \quad \text{para cada $v$ em $V$}\\ x(\cut(S)) & \ \geq \ 1 \quad \text{para cada $S$ em $\Fcal$}\\ x_e & \ \geq \ 0 \quad \text{para cada $e$ em $E$,} \end{split} \end{equation}

sendo $V:=V(G)$, $E:=E(G)$ e $\Fcal$ o conjunto de todos os subconjuntos ímpares de $V$ (portanto $\Fcal$ pode ser enorme). O conjunto de todas as soluções viáveis desse pl é conhecido como poliedro dos ep's (= perfect matching polyhedron) de $G$ e denotado por $\PM(G)$. Esse poliedro é limitado pois é subconjunto do poliedro limitado $\FPM(G)$ discutido nas seções anteriores.

Exemplo 10.2: Seja $G$ grafo definido abaixo por sua matriz de adjacências. Cada linha da tabela à direita representa um vetor de $\PM(G)$. As três primeiras linhas representam os três únicos ep's de $G$.

\[ \begin{array}[t]{l@{\quad}cccccc} & a & b & c & d & e & f \\[0.5ex] a & - & - & - & 1 & 1 & - \\ b & - & - & - & 1 & 1 & 1 \\ c & - & - & - & - & 1 & 1 \\ d & 1 & 1 & - & - & - & - \\ e & 1 & 1 & 1 & - & - & - \\ f & - & 1 & 1 & - & - & - \end{array} \hspace{6ex} \begin{array}[t]{l@{\quad}*{7}{l}} & ad & ae & bd & be & bf & ce & cf \\[0.5ex] & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ & 0.3 & 0.7 & 0.7 & 0.2 & 0.1 & 0.1 & 0.9 \\ & 0.15 & 0.85 & 0.85 & 0.1 & 0.05 & 0.05 & 0.95 \\ & 0.12 & 0.88 & 0.88 & 0.12 & 0.0 & 0.0 & 1.0 \end{array} \]

O poliedro $\PM(G)$ representa muito bem o conjunto dos ep's de $G$. Em primeiro lugar, $\PM(G)$ é vazio se e somente se $G$ não tem ep's. Em segundo lugar, os vértices de $\PM(G)$ são os ep's de $G$. Essas afirmações decorrem do seguinte teorema de J. Edmonds:

A prova do teorema não é fácil e será omitida. O teorema justifica o algoritmo Blossom mencionado na seção 9.5.

Podemos resumir assim o estudo do poliedro dos ep's: para qualquer grafo $G$, o poliedro $\PM(G)$ é o casco convexo dos ep's de $G$ (veja o teorema D.3 do apêndice D). Em particular, $\PM(G)$ é um politopo.