| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:conseqhall [2023/03/08 13:30] – edição externa 127.0.0.1 | grafos:conseqhall [2023/03/08 13:33] (atual) – edição externa 127.0.0.1 |
|---|
| <wrap right>$\square$</wrap> | <wrap right>$\square$</wrap> |
| </WRAP> | </WRAP> |
| | |
| | ---- |
| |
| Aplicando simultaneamente o Teorema de Hall e o [[.teoeuler | Teorema de Euler]], é possível descrever outros subgrafos geradores em uma certa família de grafos: | Aplicando simultaneamente o Teorema de Hall e o [[.teoeuler | Teorema de Euler]], é possível descrever outros subgrafos geradores em uma certa família de grafos: |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| **Corolário:** Todo grafo $k-$regular com $k>0$ par admite um [[.kfator | $2-$fator]]. | === Corolário === |
| | //Todo grafo $k-$regular com $k>0$ par admite um [[.kfator | $2-$fator]].// |
| </WRAP> | </WRAP> |
| __//Demonstração://__ Seja $G = (V,E)$ um grafo $k-$regular, em que $k>0$ é um número par. Pelo Teorema de Euler, $G$ admite um [[.defeuler | circuito euleriano]], cujos vértices serão sequencialmente denotados, com eventual repetição, por $(v_1,v_2,\dots,v_n)$. Considere então $H$ o grafo obtido a partir de $G$ da seguinte maneira: | |
| | <WRAP round box 100%> |
| | **//Demonstração://** Seja $G = (V,E)$ um grafo $k-$regular, em que $k>0$ é um número par. Pelo Teorema de Euler, $G$ admite um [[.defeuler | circuito euleriano]], cujos vértices serão sequencialmente denotados, com eventual repetição, por $(v_1,v_2,\dots,v_n)$. Considere então $H$ o grafo obtido a partir de $G$ da seguinte maneira: |
| * Para cada vértice $v\in V$, considere duas cópias $v^+$ e $v^-$. Com isso, os vértices de $H$ corresponderão ao conjunto $\{v^+,v^- : v \in V\}$. | * Para cada vértice $v\in V$, considere duas cópias $v^+$ e $v^-$. Com isso, os vértices de $H$ corresponderão ao conjunto $\{v^+,v^- : v \in V\}$. |
| * O conjunto de arestas de $H$ é dado por $\{v_i^+v_{i+1}^- : 1 \leq i \leq n-1\}$. | * O conjunto de arestas de $H$ é dado por $\{v_i^+v_{i+1}^- : 1 \leq i \leq n-1\}$. |
| {{ :grafos:doisfator.png?700 |}} | {{ :grafos:doisfator.png?700 |}} |
| |
| Por definição, $H$ é um grafo bipartido com partes $\{v^+ : v\in V\}$ e $\{v^- : v\in V\}$. Além disso, como a sequência $(v_1,v_2,\dots,v_n)$ descreve um circuito euleriano, a definição das arestas de $H$ nos garante que esse é um grafo $\frac{k}{2}-$regular. Logo, pelo Corolário acima, existe $M'$ um emparelhamento para $H$ que cobre todos os seus vértices. Ou seja, para cada $v\in V$, os vértices $v^+$ e $v^-$, além de serem extremidades de uma única aresta de $M'$ cada, são cobertos por arestas distintas desse emparelhamento. Logo, o conjunto de arestas $M = \{v_iv_{i+1} : i \text{ é tal que } v_i^+v_{i+1}^- \in M'\}$ é tal que $(V,M)$ é um $2-$fator de $G$. <wrap right>$\square$</wrap> | Por definição, $H$ é um grafo bipartido com partes $\{v^+ : v\in V\}$ e $\{v^- : v\in V\}$. Além disso, como a sequência $(v_1,v_2,\dots,v_n)$ descreve um circuito euleriano, a definição das arestas de $H$ nos garante que esse é um grafo $\frac{k}{2}-$regular. Logo, pelo Corolário acima, existe $M'$ um emparelhamento para $H$ que cobre todos os seus vértices. Ou seja, para cada $v\in V$, os vértices $v^+$ e $v^-$, além de serem extremidades de uma única aresta de $M'$ cada, são cobertos por arestas distintas desse emparelhamento. Logo, o conjunto de arestas $M = \{v_iv_{i+1} : i \text{ é tal que } v_i^+v_{i+1}^- \in M'\}$ é tal que $(V,M)$ é um $2-$fator de $G$. |
| | |
| | <wrap right>$\square$</wrap> |
| | </WRAP> |