Otimização Combinatória | Dicionário | Índice remissivo

Capítulo 9
Emparelhamentos perfeitos de custo mínimo

Agora que sabemos calcular um emparelhamento perfeito (veja o capítulo 7) num grafo não-dirigido, podemos empreender o próximo passo: calcular um emparelhamento perfeito de custo mínimo. Este capítulo resolve o problema em grafos bipartidos e faz um esboço da solução no caso geral.

As técnicas desenvolvidas para resolver o problema estão na origem da chamada combinatória poliédrica, que se tornou ferramenta essencial no estudo de muitos problemas de otimização combinatória.

Todos os grafos neste capítulo são não-dirigidos. Por isso, diremos simplesmente grafo, deixando subentendido o adjetivo não-dirigido. Para conferir as definições de outros termos técnicos, consulte o índice remissivo e os apêndices.

9.1 O problema

Seja $G$ um grafo e $c$ uma função que atribui custos às arestas de $G$. (O custo de uma aresta pode ser positivo, negativo, ou nulo.)  Para qualquer conjunto $M$ de arestas, denotaremos por $c(M)$ a soma $\sum_{e\in M} c_e$.

Usaremos as abreviaturas ep e ep mínimo para as expressões emparelhamento perfeito e emparelhamento perfeito de custo mínimo respectivamente. (É razoável omitir a expressão de custo pois mínimo não poderia estar se referindo à cardinalidade do emparelhamento.)

9.2 Um programa linear para ep mínimo

Para projetar um algoritmo para o problema 9.A, é importante representar o problema por meio de um programa linear. Se $x$ é o vetor característico de um ep num grafo $G$ então $x(\cut(v))=1$ para cada nó $v$ de $G$. Portanto, o problema do ep mínimo pode ser representado pelo seguinte programa linear: encontrar um vetor real $(x_e : e\in E)$ que

\begin{equation}\label{lp:bipartite-min-cost-pm} \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)$. É claro que toda solução viável inteira (e portanto binária) do pl representa um ep. Portanto, uma solução ótima $x$ do pl representa uma solução do problema 9.A desde que $x$ seja inteiro. Entretanto, muitas soluções ótimas do pl não são inteiras.  [Se trocarmos a restrição $x_e\geq 0$ por $x_e \in \conj{0,1}$ — ou, alternativamente, por $x_e\in \Zplus$ — o programa \eqref{lp:bipartite-min-cost-pm} representará corretamente o problema 9.A, mas deixará de ser linear.]

(Compare \eqref{lp:bipartite-min-cost-pm} com o pl $(1)$ do capítulo 4, que trata de fluxo viável de custo mínimo em grafos dirigidos. Lá, toda solução não-inteira do pl é solução do problema do fluxo.)

Programa dual. O dual do programa linear \eqref{lp:bipartite-min-cost-pm} consiste em encontrar um vetor real $(y_v : v\in V)$ que

\begin{equation}\label{lp:dual:bipartite-min-cost-pm} \begin{split} \text{maximize} \quad y\,1 & \\ \text{sujeito a} \quad y_v+y_w & \ \leq \ c_{vw} \quad \text{para cada $vw$ em $E$.} \end{split} \end{equation}

A expressão $y\,1$ denota a soma $\sum_{v\in V} y_v$. Diremos que um vetor $y$ que satisfaz as restrições \eqref{lp:dual:bipartite-min-cost-pm} é um potencial viável.  [Não confunda com o conceito de potencial viável associado ao problema do caminho de custo mínimo na seção 1.2. Ao contrário daquele, este potencial deixa de ser viável se somarmos um mesmo número a cada componente $y_v$.]  É fácil encontrar um potencial viável: se $c_e \geq \alpha$ para toda aresta $e$ então o potencial que atribui $\alpha/2$ a cada nó é viável.

Dado um potencial $y$, o custo reduzido de uma aresta $vw$ é o número $c_{vw}-y_v-y_w$. O vetor de custos reduzidos será denotado por $\cy$. Portanto, \[ \cy_{vw} := c_{vw} - y_v - y_w \] para cada aresta $vw$. Observe que $\cy\geq 0$ se e somente se o potencial $y$ é viável.

Como se sabe, uma solução viável $x$ do pl \eqref{lp:bipartite-min-cost-pm} é ótima se e somente se existe um potencial viável $y$ tal que $cx=y1$. E essa igualdade vale se e somente se as folgas de $x$ e $y$ são complementares, isto é, se e somente se \begin{equation}\label{eq:complementary-slackness-min-cost-pm-2} x_e = 0 \quad \text{ou} \quad \cy_e = 0 \end{equation} para todo $e$ em $E$.

Como veremos na próxima seção, o programa linear dual \eqref{lp:dual:bipartite-min-cost-pm} e o conceito de potencial viável têm um papel importante no projeto de um algoritmo para o problema 9.A, pelo menos quando o problema é restrito a grafos bipartidos.

9.3 Algoritmo para ep mínimo em grafo bipartido

Seja $(G,c)$ uma instância do problema 9.A e considere a correspondente instância do pl \eqref{lp:bipartite-min-cost-pm}. Seja $y$ um potencial viável e $\cy$ o correspondente custo reduzido. Dizemos que uma aresta $e$ de $G$ está justa se $\cy_e=0$. O conjunto das arestas justas será denotado por $\Eequ$ e às vezes denominado conjunto justo.

A seguinte observação é o ponto de partida do projeto de um algoritmo para o problema 9.A. Dado um potencial viavel $y$ e um ep $M$ em $G$, se \begin{equation}\label{eq:matching-subseteq-equality-set} M \subseteq \Eequ \end{equation} então as folgas de $y$ e do vetor característico de $M$ são complementares, ou seja, satisfazem \eqref{eq:complementary-slackness-min-cost-pm-2}, e portanto $M$ é um ep mínimo. Assim, para encontrar um ep mínimo em $(G,c)$, basta encontrar um potencial viável $y$ e um ep no subgrafo gerador justo $(V(G),\Eequ)$. Se $G$ for bipartido, um tal par $(y,M)$ existe. (Para uma prova não algorítmica desse fato, veja o teorema de Birkhoff no capítulo 10.)

Preliminares. A procura por um ep no grafo $(V(G),\Eequ)$ pode ser executada pelo algoritmo Emp­Bipartido­Perfeito da seção 7.4. Por isso, convém resumir alguns dos conceitos introduzidos na seção 7.3.

Suponha que $M$ é um emparelhamento num grafo $G$ e $T$ é uma árvore $M$-alternante com raiz $r$. Um nó $v$ de $T$ é branco se a distância de $r$ a $v$ em $T$ é ímpar, e preto se essa distância é par. A árvore $T$ é frustrada se toda aresta de $G$ com uma ponta preta tem a outra ponta branca. O lema 7.5 mostra que se $T$ é frustrada então $G$ não tem um ep.

Os nós de $G$ que não pertencem a $T$ têm cores: um nó $w$ é vermelho se estiver $M$-exposto e verde em caso contrário. Uma aresta é preto-vermelha se uma de suas pontas é preta e a outra é vermelha. Arestas preto-verde, preto-branca e preto-preta são definidas analogamente. Se $G$ é bipartido, não tem circuitos ímpares e portanto não tem arestas preto-pretas, como observamos na seção 7.3.

O algoritmo húngaro. O algoritmo que resolve a restrição do problema 9.A a grafos bipartidos foi proposto por H. Kuhn (1955) e J. Munkers (1957) e ficou conhecido como algoritmo húngaro. O algoritmo recebe um grafo bipartido $G$ e um vetor $c$ de custos e devolve um ep de custo mínimo ou informa que $G$ não tem ep algum.

O algoritmo é iterativo. Numa descrição grosseira e imprecisa, poderíamos dizer que cada iteração começa com um potencial viável $y$ e usa o algoritmo Emp­Bipartido­Perfeito para procurar um ep no grafo justo $\Gequ := (V(G),\Eequ)$. Se um tal ep for encontrado, o problema está resolvido graças a \eqref{eq:matching-subseteq-equality-set}. Senão, $y$ é ajustado e uma nova iteração começa com o novo potencial viável.

Numa descrição mais precisa, cada iteração começa com um potencial viável $y$ e um emparelhamento $M \subseteq \Eequ$. (Na primeira iteração, $y$ é um potencial viável arbitrário.) Se $M$ é perfeito, o problema está resolvido. Suponha agora que $M$ não é perfeito. Então um código análogo ao de Emp­Bipartido­Perfeito é usado para calcular uma árvore $M$-alternante $T$ em $\Gequ$. Se $T$ levar a um caminho aumentador, começamos uma nova iteração com um emparelhamento maior. Caso contrário, $T$ é frustrada em $\Gequ$. Nesse caso, a árvore frustrada é usada como guia para ajustar o potencial viável $y$.

O ajuste de $y$ é feito da seguinte maneira. Seja $F$ o conjunto das arestas preto-verdes de $G$ e $F'$ o conjunto das arestas preto-vermelhas de $G$. (É claro que $F\cup F'$ é disjunto de $\Eequ$.)  Se $F\cup F'$ é vazio então toda aresta de $G$ com uma ponta preta tem a outra branca, donde $T$ é frustrada em $G$, e assim $G$ não tem ep algum. Suponha agora que $F\cup F'$ não é vazio. Seja $\epsilon$ o menor custo reduzido dentre as arestas de $F\cup F'$, isto é, $\epsilon := \min\left(\cy_{vw} : vw\in F\cup F'\right)$. Um novo potencial é calculado da seguinte maneira: para cada nó $v$ de $T$,

1. adicione $\epsilon$ a $y_v$ se $v$ é preto e
2. subtraia $\epsilon$ de $y_v$ se $v$ é branco.

O novo potencial é viável (veja o exercício abaixo).  Uma nova iteração começa com esse novo potencial. O novo conjunto justo pode não ser um superconjunto do anterior. Ainda assim, o novo conjunto justo contém $M$ e $E(T)$. Ademais, o novo conjunto justo contém alguma aresta de $F\cup F'$, uma vez que $\epsilon > 0$. Uma nova iteração começa com o novo valor de $y$ e com o emparelhamento $M$ da iteração anterior.

Como se vê, o algoritmo avança ajustando o potencial viável $y$ e, ao mesmo tempo, o emparelhamento $M$. Esse tipo de algoritmo é conhecido como primal-dual e aparece frequentemente em otimização combinatória.

Exemplo 9.6 [CCPS fig.5.12]: A figura mostra um grafo $G$ com custos nas arestas. A primeira coluna da tabela define um potencial viável $y$. O conjunto de arestas justas é $\Eequ=\conj{ra, ab, rd, df, gh}$. O algoritmo húngaro começa com o emparelhamento $M:=\conj{ab,df,gh}$ representado pelas linhas grossas da figura.  A primeira iteração do algoritmo procura um ep no subgrafo justo $(V,\Eequ)$. Para isso, constrói a árvore $M$-alternante $T$ com raiz $r$ e arestas $ra$, $ab$, $rd$ e $df$ (linha sólidas da figura). Os nós $r$, $b$ e $f$ são pretos e os nós $a$ e $d$ são brancos. Os nós $g$ e $h$ são verdes e o nó $i$ é vermelho. Não há arestas preto-verdes nem preto-vermelhas no subgrafo justo. A árvore $T$ é frustrada no subgrafo justo e portanto o subgrafo não tem ep.

\[ \begin{array}[t]{l@{\quad}r} & y \\[0.5ex] r & +1 \\ a & +1 \\ b & +2 \\ d & +3 \\ f & +1 \\ g & +2 \\ h & +3 \\ i & +2 \end{array} \hspace{6ex} \begin{array}[t]{l@{\enspace}*{9}c} & ra & ab & rd & df & bg & fg & gh & fi & hi \\[0.5ex] \cy & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 2 & 1 \end{array} \]

Em $G$, o conjunto das arestas preto-verdes e preto-vermelhas é $F\cup F' :=\conj{bg, fg, fi}$. O menor custo reduzido nesse conjunto é $\epsilon:=1$. Um novo potencial é calculado somando $\epsilon$ ao potencial de cada nó preto e subtraindo $\epsilon$ do potencial de cada nó branco. Esse segundo potencial é viável. A aresta $fg$ fica justa e portanto pertence ao novo $\Eequ$.

\[ \begin{array}[t]{l@{\quad}r} & y \\[0.5ex] r & +2 \\ a & 0 \\ b & +3 \\ d & +2 \\ f & +2 \\ g & +2 \\ h & +3 \\ i & +2 \end{array} \hspace{6ex} \begin{array}[t]{l@{\enspace}*{9}c} & ra & ab & rd & df & bg & fg & gh & fi & hi \\[0.5ex] \cy & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{array} \]

Na segunda iteração, a árvore $T$ continua crescendo no novo subgrafo justo. As arestas $fg$ e $gh$ são acrescentadas a $T$. Essa árvore é frustrada (no subgrafo justo) e portanto o subgrafo não tem ep. Em $G$, o conjunto das arestas preto-verdes e preto-vermelhas é $F\cup F' :=\conj{fi, hi}$. O menor custo reduzido nesse conjunto é $\epsilon:=1$. Um novo potencial viável é calculado somando $\epsilon$ ao potencial de cada nó preto e subtraindo $\epsilon$ do potencial de cada nó branco. As arestas $fi$ e $hi$ tornam-se justas.

\[ \begin{array}[t]{l@{\quad}r} & y \\[0.5ex] r & +3 \\ a & -1 \\ b & +4 \\ d & +1 \\ f & +3 \\ g & +1 \\ h & +4 \\ i & +2 \end{array} \hspace{6ex} \begin{array}[t]{l@{\enspace}*{9}c} & ra & ab & rd & df & bg & fg & gh & fi & hi \\[0.5ex] \cy & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{array} \]

Na terceira iteração, a árvore $T$ continua crescendo no (novo) subgrafo justo. A aresta $hi$ é acrescentada a $T$. O caminho $(r,d,f,g,h,i)$ em $T$ é aumentador. Depois que esse caminho aumentador for processado teremos um ep no subgrafo justo $(V,\Eequ)$. Esse ep é mínimo em $G$.

Veja o rastreamento da execução do algoritmo. Cada linha da tabela descreve os valores das variáveis ao longo de uma iteração:

\[ \begin{array}{rrrrrrrrc*{5}{l@{\quad}}} %%% & & & y \ \\ y_r& y_a& y_b& y_d& y_f& y_g& y_h& y_i && \Eequ && M \subseteq \Eequ&& T && F\cup F' && \epsilon & \\[0.5ex] \hline\rule{0ex}{2.5ex} 1& 1& 2& 3& 1& 2& 3& 2 && ra\ ab\ rd\ df\ gh && ab\ df\ gh && rab\ \ rdf && bg\ fg\ fi && 1\\ 2& 0& 3& 2& 2& 2& 3 & 2 && \text{mais} \ fg && ab\ df\ gh && \text{mais} \ fgh\ \ hi && fi\ hi && 1\\ 3& -1& 4& 1& 3& 1& 4& 2 && \text{mais} \ fi\ hi && ab\ rd\ fg\ hi \end{array} \]

Segue o código do algoritmo húngaro:

Exceto pelas linhas 11 a 13 e 16 a 18, o código é essencialmente igual ao do algoritmo Emp­Bipartido­Perfeito da seção 7.4.

O processo iterativo externo, que ocupa as linhas 03 a 21, procura um ep no conjunto justo $\Eequ$. No início de cada iteração desse processo temos um potencial viável $y$ e um emparelhamento $M\subseteq \Eequ$.

O processo iterativo interno, que ocupa as linhas 06 a 21, recebe um emparelhamento imperfeito $M$ e procura um caminho $M$-aumentador no subgrafo justo. No início de cada iteração desse processo, temos não só um potencial viável $y$ e um emparelhamento imperfeito $M\subseteq \Eequ$, como também uma árvore $M$-alternante $T$ com $E(T)\subseteq \Eequ$. O algoritmo pode alterar $y$ durante a iteração, mas as propriedades $M\subseteq \Eequ$ e $E(T)\subseteq \Eequ$ são preservadas e pelo menos uma nova aresta torna-se justa.

Na linha 15, temos $\oc_1(G{-}A) > |A|$. A existência de um tal $A$ prova que $G$ não tem ep, conforme o lema 7.2.

Desempenho. No pior caso, o algoritmo Húngaro consome $\Oh(m n^2)$ unidades de tempo, sendo $m$ o número de arestas e $n$ o número de nós do grafo. O termo $m$ é consequência do processo iterativo externo, que acrescenta pelo menos uma aresta a $\Gequ$ a cada iteração. O termo $n^2$ representa o consumo de tempo do algoritmo Emp­Bipartido­Perfeito.

9.4 Um programa linear mais poderoso

O programa linear \eqref{lp:bipartite-min-cost-pm} representa mal o problema 9.A, a menos que o grafo seja bipartido. Tipicamente, o custo $c(M)$ de um ep mínimo $M$ é estritamente maior que o custo $cx$ de uma solução ótima $x$ do pl, e a correspodente solução $x$ não é inteira. Precisamos de um pl mais poderoso, com restrições lineares que cortem fora as soluções não-inteiras do pl \eqref{lp:bipartite-min-cost-pm}.  A ideia de acrescentar restrições lineares a um pl para eliminar soluções fracionárias indesejadas é muito efetiva e mostrou-se útil em muitos problemas de otimização combinatória.

Dizemos que um corte $\cut(S)$ num grafo $G$ tem margem ímpar se $|S|$ é ímpar. (A paridade de $|\cut(S)|$ é irrelevante.)  Denotaremos por  $\Fcal$  o conjunto de todos os subconjuntos $S$ de $V(G)$ tais que $|S|$ é ímpar. Se $S \in \Fcal$ e $x$ é o vetor característico de um ep então é claro que \begin{equation}\label{eq:blossom-inequality} x(\cut(S)) \geq 1\text{.} \end{equation} Portanto, podemos acrescentar essas desigualdades ao pl \eqref{lp:bipartite-min-cost-pm}. O resultado é o seguinte pl:

\begin{equation}\label{lp:min-cost-pm} \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}

As restrições $x(\cut(S))\geq 1$ são conhecidas como desigualdades florais (= blossom inequalities). O número de desigualdades florais é enorme pois o conjunto $\Fcal$ é enorme. É bem verdade que algumas dessas desigualdades são claramente redundates. Em primeiro lugar, se $|S|=1$ então a restrição $x(\cut(S))\geq 1$ está subentendida em $x(\cut(v))=1$. O mesmo acontece se $|\compl{S}|=1$, sendo $\compl{S} = V\setm S$. Em segundo lugar, se $|S|$ e $|\compl{S}|$ são ímpares então as restrições $x(\cut(S))\geq 1$ e $x(\cut(\compl{S}))\geq 1$ são idênticas e portanto uma pode ser eliminada. Mas a eliminação dessas redundâncias óbvias não leva a uma redução significativa do número de desigualdades florais. Em cada instância específica do pl \eqref{lp:min-cost-pm}, a grande maioria das desigualdades florais se revela redundante por razões que não são óbvias. A dificuldade está em saber quais desigualdades florais poderiam ser ignoradas.

Programa dual. O pl dual de \eqref{lp:min-cost-pm} tem uma variável $y_v$ para cada nó $v$ e uma variável $Y_S$ para cada $S$ em $\Fcal$ e consiste em encontrar um par $(y,Y)$ que \begin{equation}\label{lp:dual:min-cost-pm} \begin{split} \text{maximize} \quad \textstyle y1 + Y1 & \\[0.5ex] \text{sujeito a} \quad \textstyle y_v+y_w + \sum (Y_S : S\in \Fcal_{vw}) & \ \leq \ c_{vw} \quad \text{para cada $vw$ em $E$}\\ Y_S & \ \geq \ 0 \quad \text{para cada $S$ em $\Fcal$,} \end{split} \end{equation}

sendo $y1 = \sum_{v\in V} y_v\,$,  $Y1 = \sum_{S\in \Fcal} Y_S$  e  $\Fcal_{vw} := \conj{S \in \Fcal : \cut(S)\ni vw}$.

Dado um par $(y,Y)$, o custo reduzido de qualquer aresta $vw$ é o número $\cyY_{vw}$ definido assim: \[\textstyle \cyY_{vw} := c_{vw} - y_v - y_w - \sum (Y_S : S\in \Fcal_{vw})\text{.} \] Portanto, $(y,Y)$ é viável em \eqref{lp:dual:min-cost-pm} se e somente se $\cyY_e\geq 0$ para cada $e$ em $E$ e $Y_S\geq 0$ para cada $S$ em $\Fcal$.

Folgas complementares. Para qualquer solução viável $x$ do pl \eqref{lp:min-cost-pm} e qualquer solução viável $(y,Y)$ do pl \eqref{lp:dual:min-cost-pm}, temos $cx=y1+Y1$ se e somente se valem as seguintes folgas complementares: para cada $e$ em $E$, \[ x_e = 0 \quad \text{ou} \quad \cyY_e = 0 \] e, para cada $S$ em $\Fcal$, \[ x(S) = 1 \quad \text{ou} \quad Y_S = 0\text{.} \] Dada uma solução viável $(y,Y)$ do pl dual \eqref{lp:dual:min-cost-pm}, as condições de folgas complementares têm a seguinte consequência: se $M$ é um ep tal que

$M \subseteq \EequY$  e  $|M\cap S| = 1$ para cada $S$ em $\Fcal$ tal que $Y_S > 0$

então $M$ é um ep mínimo.

Laminaridade. Em geral, numa solução ótima $(y,Y)$ de \eqref{lp:dual:min-cost-pm}, a maior parte das componentes de $Y$ é nula. Ademais, os conjuntos $S$ para os quais $Y_S>0$ formam uma coleção laminar (veja a seção A.5 do apêndice A) e portanto há menos que $2|V|$ deles.

Exemplo 9.8 [CCPS fig.5.13]: Para a instância do problema 9.A descrita a seguir, uma solução ótima do pl \eqref{lp:bipartite-min-cost-pm} não define um ep.

\[ \begin{array}[t]{l@{\quad}cccccc} & a & b & c & d & e & f \\[0.5ex] a & - & 1 & 1 & - & - & 1 \\ b & 1 & - & 1 & - & 1 & - \\ c & 1 & 1 & - & 1 & - & - \\ d & - & - & 1 & - & 1 & 1 \\ e & - & 1 & - & 1 & - & 1 \\ f & 1 & - & - & 1 & 1 & - \end{array} \]

Considere então os pl's \eqref{lp:min-cost-pm} e \eqref{lp:dual:min-cost-pm}. Uma solução viável $x$ do pl \eqref{lp:min-cost-pm} e uma solução viável $(y,Y)$ do pl dual \eqref{lp:dual:min-cost-pm} estão indicadas abaixo, juntamente com o custo reduzido $\cyY$. O vetor dual $Y$ tem uma única componente não nula: $Y_S>0$ apenas quando $S = \conj{a,b,c}$. (São nulas, por exemplo, as componentes de $Y$ que correspondem aos conjuntos $\conj{a,d,f}$, $\conj{a,c,f}$ e $\conj{a,c,d}$.)

\[ \begin{array}[t]{r@{\quad}*{9}{c}} & ab & bc & ca & de & ef & fd & be & cd & af \\[0.5ex] c & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ x & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ \cyY & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 0 & 0 \end{array} \hspace{4ex} \begin{array}[t]{r@{\quad}*{1}{r}} & y \\[0.5ex] a & 1 \\ b & 0 \\ c & 2 \\ d & 1 \\ e & 2 \\ f & 3 \end{array} \hspace{4ex} \begin{array}[t]{r@{\ }*{1}{r}} & Y \\[0.2ex] abc & 5 \end{array} \]

Com um pouco de paciência, verificamos que os valores $\cyY$ na tabela estão corretos e são não-negativos. Tomando $M:=\conj{e : x_e=1}$, constatamos que $M$ é um ep e $M \subseteq \EequY$. Além disso, $|M\cap \cut(S)| = 1$. Portanto, $x$ e $(y,Y)$ têm folgas complementares. Logo, $M$ é um ep mínimo. Por curiosidade, verificamos ainda que $cx = 14 = y1 + Y1$. Veja outro potencial $(y,Y)$ que tem folgas complementares com as de $x$:

\[ \begin{array}[t]{r@{\quad}*{9}{c}} & ab & bc & ca & de & ef & fd & be & cd & af \\[0.5ex] c & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ x & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ \cyY & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1 \end{array} \qquad \begin{array}[t]{r@{\quad}*{1}{l}} & y \\[0.5ex] a & 1 \\ b & 0 \\ c & 2 \\ d & 2.5 \\ e & 1.5 \\ f & 3.5 \end{array} \qquad \begin{array}[t]{r@{\enspace}*{1}{l}} & Y \\[0.2ex] abc & 3.5 \end{array} \]

9.5 Algoritmo para ep mínimo em grafo arbitrário

Em 1965, J. Edmonds usou os pl's \eqref{lp:min-cost-pm} e \eqref{lp:dual:min-cost-pm} como ponto de partida para obter um algoritmo que resolve o problema 9.A do ep mínimo. O algoritmo de Edmonds é conhecido como algoritmo das flores para ep mínimo (= blossom algorithm for minimum perfect matching).  O ponto de partida é o algoritmo Emp­Perfeito da seção 7.6. As flores produzidas por Emp­Perfeito correspondem, grosso modo, aos conjuntos ímpares $S$ que têm $Y_S\neq 0$.

A discussão do algoritmo foge ao escopo destas notas. Vou me limitar a exibir o código, sem maiores explicações.

Esse algoritmo pode ser implementado de modo a consumir $\Oh(n^2m)$ unidades de tempo.