grafos:defbipartite

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:defbipartite [2023/02/19 13:56] – pivagrafos: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: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. 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.
Linha 25: 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:definicaografos#adjacencia |adjacentes]]. A união de todo os grafos $r$-partidos completos, para todo $r$, constitui o conjunto dos **grafos completos multipartidos**//.
 </WRAP> </WRAP>
  
Linha 57: Linha 59:
 //**Demonstração:**//  //**Demonstração:**// 
  
-$(\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, 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.+$(\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, 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:defarvore|árvore]] ou um ciclo par.+$(\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. 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.
Linha 72: Linha 74:
 <WRAP round tip 100$> <WRAP round tip 100$>
 === Nota === === Nota ===
-É interessante notar que, pela equivalência acima, podemos concluir que toda árvore é um grafo bipartido.+//É interessante notar que, pela equivalência acima, podemos concluir que toda árvore é um grafo bipartido.//
 </WRAP> </WRAP>
  • grafos/defbipartite.1676825793.txt.gz
  • Última modificação: 2023/02/19 13:56
  • por piva