===== Grafos Bipartidos: Definições iniciais =====

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 [[grafos:definicaografos#mas_afinal_o_que_e_um_grafo | 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.

<WRAP round box 100%>
=== 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**//.
</WRAP>

{{:grafos:pentagraph_partite.png?200 |}}

\\
\\
\\ 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.

\\
\\
\\
----

<WRAP round box 100%>
=== Definição ===
//Um grafo $r$-partido é dito **completo** quando todos pares de vértices de classes distintas são [[grafos:definicaografos#adjacencia |adjacentes]]. A união de todo os grafos $r$-partidos completos, para todo $r$, constitui o conjunto dos **grafos completos multipartidos**//.
</WRAP>

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

{{ :grafos:both_hexagraph_partite.png?600 |}}

<WRAP ROUND BOX 100%>
=== 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$.//

</WRAP>

----

<WRAP round box 100%>
=== 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.//
</WRAP>

----

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

<WRAP round box 100%>
=== Proposição ===
//Um grafo é bipartido se, e somente se, não contém nenhum ciclo ímpar.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**// 

$(\Rightarrow)$ Seja $G = (V, E)$ um grafo bipartido com classes $V_1$ e $V_2$. Posto que é bipartido, toda [[.defCompCon|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 [[.teoeuler | 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 [[grafos:defarvore|á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 [[grafos:defraiz|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.

<wrap right>$\square$</wrap>
</WRAP>
----


<WRAP round tip 100$>
=== Nota ===
//É interessante notar que, pela equivalência acima, podemos concluir que toda árvore é um grafo bipartido.//
</WRAP>