Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:defbipartite [2023/02/23 10:01] – edição externa 127.0.0.1 | grafos:defbipartite [2023/03/01 14:09] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| ===== Grafos Bipartidos: Definições iniciais ===== | ===== 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: | + | 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: |
| Não é difícil perceber que a ideia de um //**grafo bipartido**// | Não é difícil perceber que a ideia de um //**grafo bipartido**// | ||
| Linha 27: | Linha 27: | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição === | === 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**// | + | //Um grafo $r$-partido é dito **completo** quando todos pares de vértices de classes distintas são [[grafos: |
| </ | </ | ||
| Linha 59: | Linha 59: | ||
| // | // | ||
| - | $(\Rightarrow)$ Seja $G = (V, A)$ 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, | + | $(\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, |
| - | $(\Leftarrow)$ Seja $G = (V, A)$ 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: | + | $(\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: |
| 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: | 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: | ||