CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Emparelhamentos em Grafos Bipartidos:

Definições fundamentais

Definição: Um emparelhamento $M\subseteq E(G)$ é um subconjunto de arestas de um grafo $G$, tal que quaisquer duas arestas de $M$ são não-adjacentes.

Definição: Um emparelhamento $M$ de $G$ é maximal se não existe $M'\subseteq E(G)$ tal que $M\subset M'$ e $M'$ é um emparelhamento de $G$. Além disso, $M$ é máximo se não existe emparelhamento $M'$ tal que $|M'|>|M|$.

Além disso, o tamanho ou cardinalidade de um emparelhamento máximo de $G$ é denotado por $\alpha '(G)$.

Definição: Seja $M$ um emparelhamento de $G$. Dizemos que um vértice $v$ é M-saturado se $v$ é extremidade de alguma aresta de $M$. caso contrário, dizemos que $v$ é M-insaturado.

Definição: Seja $M$ um emparelhamento de $G$. Se, $\forall v\in V(G)$, $v$ é $M$-saturado, então $M$ é um emparelhamento perfeito.

Definição: Seja $M$ um emparelhamento de $G$. Um caminho $P$ de $G$ é M-alternado se $P$ possui arestas sequenciais $e_{1},e_{2},...,e_{k}$ que alternam em pertencer e não pertencer a $M$.

Além disso, um caminho é M-aumentante se suas extremidades são M-insaturadas e $P$ é M-alternado.

Definição: Seja $G$ um grafo qualquer e $S\subseteq V(G)$. A vizinhança de $S$ em $G$ é o conjunto de todos os vértices vizinhos dos vértices de $S$, e denotamos por $N(S)$, isto é: $N(S)=\cup _{\forall v\in S}N(v)$.

Teoremas relacionados

Teorema de Berge: Seja $G$ um grafo e $M$ um emparelhamento de $G$. Então $M$ é máximo se e somente se $G$ não admite caminhos M-aumentantes.

Prova (volta): Seja $G$ e $M$, tal que $G$ não possui qualquer caminho M-aumentante. Suponha por absurdo que $M$ não é máximo.

Seja $M*$ um emparelhamento máximo de $G$, ou seja, $|M|<|M*|$. Seja $H=G[M\Delta M*]$ (diferença simétrica entre $M$ e $M*$ em $G$).

Podemos ver que todo vértice $v\in V(H)$ possui grau no máximo 2, pois cada vértice pode estar em no máximo uma aresta de $M$ e no máximo uma aresta de $M*$. Dessa forma, $H$ é formado apenas por ciclos e caminhos disjuntos.

Também podemos ver que todo ciclo de $H$ é par e, para cada tal ciclo, temos o mesmo número de arestas de $M$ e de $M*$. Portanto, como $|M*|>|M|$, então deve existir um caminho $P$ com mais arestas de $M*$ que de $M$. Além disso, $P$ possui um número ímpar de arestas. Sejam ${e_{1},e_{2},...,e_{2kH}}$ as arestas de $P$. Temos que as arestas $e_{i}$, com $i$ ímpar pertencem a $M*$ e as arestas $e_{i}$ com $i$ par, pertencem a $M$.

Além disso, suas extremidades são M-insaturadas, caso contrário o caminho $P$ seria maior. Logo, $P$ é M-aumentante. Absurdo, e portanto, $M$ é emparelhamento máximo de $G$.

Prova (ida): Seja $M$ um emparelhamento máximo de $G$. Vamos mostrar que não possui caminhos M-aumentantes. Por absurdo, seja $P$ um caminho M-aumentante de $G$. Logo, $P$ possui um número ímpar de arestas e suas extremidades são M-insaturadas. Seja ${e_{1},e_{2},e_{3},...,e_{2k+1}}$ as arestas de $P$. Logo, as arestas $e_{i}$ de índice ímpar não pertencem a $M$ e as de índice par pertencem a $M$. Isto é, $P$ possui $(k+1)$ arestas que não estão em $M$ e $k$ arestas que estão em $M$. Portanto, podemos remover as $k$ arestas de $M\cap P$ e incluir as $(k+1)$ arestas de $(E(G)-M)\cap P$ a $M$, obtendo um emparelhamento de tamanho maior que $M$. Isso contradiz o fato de que $M$ é máximo. Absurdo.

---

Teorema de Holl: Seja $G$ um grafo bipartido com bipartição $(A,B)$. Então $G$ possui um emparelhamento que sature todo o conjunto $A$ se e somente se, $\forall S\subseteq A,|S|\leq |N(S)|$, onde $N(S)=\cup _{\forall v\in S}N(v)$.

Prova (ida): Seja $G$ bipartido com bipartição $(A,B)$ e tal que todo o conjunto $A$ é $M$-saturado. Seja $A=\{a_{1},a_{2},a_{3},...,a_{k_{1}}\}$ e $B=\{b_{1},b_{2},b_{3},...,b_{k_{2}}\}$. Como $M$ satura todo o conjunto $A$, temos que $a_{i}b_{j}\in M$, $\forall a_{i}\in A$ e algum $b_{j}\in B$. Logo, $\forall S\subseteq A$, temos que existe um vizinho em $B$ para cada elemento de $S$. Ou seja $|N(S)|\geq |S|$.

Prova (volta): Seja $G$ um grafo bipartido com bipartição $(A,B)$. Seja $A$ tal que, $\forall S\subseteq A,|S|\leq |N(S)|$. Suponha por absurdo que $G$ não admite emparelhamento $M$ que satura todo $A$.

Seja $M*$ um emparelhamento máximo de $G$. Seja $u\in A$ um vértice $M*$-insaturado. Sejam $S$ e $T$ os conjuntos de vértices que podem ser alcançados por $u$ através de caminhos $M*$-alternados em $G$, tal que $S\subseteq A$ e $T\subseteq B$.

Temos que $u\in S$, pois o caminho de $u$ a $u$ que usa 0 arestas é $M*$-alternado.

Podemos ver que todo vértice de $T$ é $M*$-saturado com algum vértice de $S$, caso contrário, existiria um caminho $M*$-aumentante de  a ele, o que contradiz o fato de ser máximo. Como todo vértice de $T$ é $M*$-saturado, temos que $|T|<|S|$, pois $u\in S$ é $M*$-insaturado. Podemos ver que $N(S)=T$, caso contrário, existiria um vértice $s'\in S$ e $b\in B-T$, tal que $s'b\in E(G)-M*$. Logo, existiria um caminho $M*$-alternado de $u$ a $s'$ que, juntamente com $s'b$ formaria um caminho $M*$-aumentante, uma contradição. Portanto, $|N(S)|=|T|<|S|$, o que contradiz a hipótese. Absurdo.

---

Corolário do Teorema de Holl: Se $G$ é um grafo $k$-regular bipartido, então $G$ tem  um emparelhamento perfeito.

Prova: Seja $G$ $k$-regular bipartido com bipartição $(A,B)$. Como $G$ é $k$-regular, então $k*|A|=k*|B|=|E(G)|$, e portanto, como $k>0$, $|A|=|B|$. Seja $S\subseteq A$ e sejam $E_{1}$ e $E_{2}$ os conjuntos de arestas incidentes em vértices de $S$ e em vértices de $N(S)$, respectivamente. Por definição de $N(S)$, $E_{1}\subseteq E_{2}$ e portanto:

$$k*|N(S)|=|E_{2}|\geq |E_{1}|=k|S|$$

Segue que $|N(S)|\geq |S|$ e assim, pelo teorema de Holl, sabemos que $G$ tem um emparelhamento que satura todo vértice em $A$. Como $|A|=|B|$, $M$ é emparelhamento perfeito.