grafos:defbipartite [WikiMat]

Nesta seção, como nas próximas, usaremos a notação $G=(V,E)$ para representar um grafo por motivos práticos, tópico discutido anteriormente.

Não é difícil perceber que a ideia de um grafo bipartido sugere que o grafo foi particionado, partido duas vezes, bem como sugere a existência de outros tipos de grafos “partidos”. Comecemos, então, por essa definição.

Definição

Seja $r \geq 2$ um inteiro. Um grafo $G$ é chamado de $r$-partido, se seus vértices podem ser divididos em $r$ classes. A condição para essa divisão é que cada aresta tenha suas extremidades em classes diferentes.

Quando temos um grafo $2$-partido, o chamamos de bipartido.

Ao lado vemos um exemplo de grafo $3$-partido. As regiões destacadas representam cada uma das classes. Pela forma como são definidos os conceitos, vale notar que:

todas as classes devem ser disjuntas entre si;
vértices adjacentes nunca estão numa mesma classe.

Definição

Um grafo $r$-partido é dito completo quando todos pares de vértices de classes distintas são adjacentes. A união de todo os grafos $r$-partidos completos, para todo $r$, constitui o conjunto dos grafos completos multipartidos.

Abaixo temos exemplos de grafos $r$-partidos completos: o primeiro bipartido e o segundo $3$-partido.

Notações

O grafo completo $r$-partido $\overline{K^{n_1}} * … * \overline{K^{n_r}}$ é denotado por $K_{n_1, …, n_r}$. No caso em que temos $n_1 = … = n_r =: s$, podemos escrever $K^r_s$. Essa notação representa o grafo $r$-partido em que toda classe possui exatamente $s$ vértices. Ou seja, os grafos do exemplo acima são, respectivamente, $K_{3, 3} = K^2_3$ e $K_{2, 2, 2} = K^3_2$.

Definição

Grafos bipartidos da forma $K_{1, n}$ são chamados de estrelas, e o vértice que integra a classe unitária é denominado centro da estrela.

Claramente, um grafo bipartido não pode conter um ciclo ímpar, um ciclo de comprimento ímpar. De fato, os grafos bipartidos são caracterizados por esta propriedade:

Proposição

Um grafo é bipartido se, e somente se, não contém nenhum ciclo ímpar.

Demonstração:

$(\Rightarrow)$ Seja $G = (V, E)$ um grafo bipartido com classes $V_1$ e $V_2$. Posto que é bipartido, toda componente sua também o é (a menos do caso de uma componente trivial). Suponhamos que uma de suas componentes seja um ciclo ímpar; que é bipartido por hipótese. Para que seja um ciclo, deve terminar no mesmo vértice em que começou. Digamos, sem perda de generalidade, que o ciclo se inicia num vértice de $V_1$. De acordo com o Teorema de Euler, o ciclo deve também findar no mesmo vértice, isto é, num vértice de $V_1$. Para que isso ocorra, o ciclo devia ter tamanho par. O que é uma contradição contradição.

$(\Leftarrow)$ Seja $G = (V, E)$ um grafo sem ciclos ímpares. Ou seja, qualquer ciclo que $G$ possui é de tamanho par. Tomemos um vértice qualquer $v_0$. Agora pegamos uma das componentes $C$ que contém $v_0$. Sabemos, por hipótese, que $C$ é uma árvore ou um ciclo par.

Para o caso em que a componente é uma árvore, podemos usar a ordem $\leq_C$ da árvore para separar os vértices em dois grupos: colocamos a raiz em $V_1$ então seus adjacentes em $V_2$; os próximos na ordem são então colocados em $V_1$ e assim sucessivamente. Concluímos que $G$ é bipartido.

No caso em que $C$ é um ciclo par podemos fazer algo semelhante. Adicionamos $v_0$ a $V_1$. Então, atribuamos o próximo vértice no ciclo a $V_2$. Podemos fazer isso até retornar a $v_0$, que, pela paridade do ciclo, será atribuído corretamente a $V_1$. Seguindo, portanto, que $G$ é bipartido.

$\square$