Diferenças

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

--- grafos:conseqhall [2023/03/08 13:20] – piva
+++ grafos:conseqhall [2023/03/08 13:33] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 1: @@
 ===== Consequências do Teorema de Hall =====
-Embora no Teorema de Hall uma das partes do grafo bipartido $G$ seja privilegiada para ser coberta por um [[.matching | emparelhamento]], sob certas hipóteses ele pode ser aplicado para encontrar um emparelhamento que cobre todos os vértices:
+Embora no Teorema de Hall uma das partes do [[.defbipartite | grafo bipartido]] $G$ seja privilegiada para ser coberta por um [[.matching | emparelhamento]], sob certas hipóteses ele pode ser aplicado para encontrar um emparelhamento que cobre todos os vértices:
 <WRAP round box 100%>
-**Corolário:** Seja $G = (V,E)$ um grafo bipartido [[.karegular | $k-$regular]]. Então, $G$ admite um emparelhamento $M$ tal que todo $v\in V$ é ponta de uma aresta de $M$.
+=== Corolário ===
+//Seja $G = (V,E)$ um grafo bipartido [[.karegular | $k-$regular]]. Então, $G$ admite um emparelhamento $M$ tal que todo $v\in V$ é ponta de uma aresta de $M$.//
 </WRAP>
-__//Demonstração://__ Sejam $A$ e $B$ as partes do grafo $G$. Uma vez que todo vértice de $A$ tem grau $k$ e toda aresta de $G$ incide em um elemento de $A$, concluímos que $G$ tem $k|A|$ arestas. Pelo mesmo argumento, $G$ possui $k|B|$ arestas. Isto é, $|A| = |B|$. Assim, um emparelhamento que cobre todos os vértices de $A$ deve cobrir também todos os vértices de $B$, pois a aplicação que descrevemos no primeiro parágrafo é injetora. Pelo Teorema de Hall, então, basta provarmos que a condição de casamento é satisfeita a respeito da parte $A$. De fato, dado $S\subset A$, temos que o número de arestas que incide em $S$ é $k |S|$. Por definição, todas essas arestas incidem em $N(S)$. Nesse conjunto, por sua vez, incidem $k|N(S)|$ arestas. Logo, $k|S|\leq k|N(S)|$, de onde obtemos que $|S|\leq |N(S)|$ e concluímos que a condição de casamento se verifica. <wrap right>$\square$</wrap>
+<WRAP round box 100%>
+**//Demonstração://** Sejam $A$ e $B$ as partes do grafo $G$. Uma vez que todo vértice de $A$ tem grau $k$ e toda aresta de $G$ incide em um elemento de $A$, concluímos que $G$ tem $k|A|$ arestas. Pelo mesmo argumento, $G$ possui $k|B|$ arestas. Isto é, $|A| = |B|$. Assim, um emparelhamento que cobre todos os vértices de $A$ deve cobrir também todos os vértices de $B$, pois a aplicação que descrevemos no primeiro parágrafo é injetora.
+Pelo [[.teoremahall |Teorema de Hall]], então, basta provarmos que a [[.condicaocasamento | condição de casamento]] é satisfeita a respeito da parte $A$. De fato, dado $S\subset A$, temos que o número de arestas que incide em $S$ é $k |S|$. Por definição, todas essas arestas incidem em $N(S)$. Nesse conjunto, por sua vez, incidem $k|N(S)|$ arestas. Logo, $k|S|\leq k|N(S)|$, de onde obtemos que $|S|\leq |N(S)|$ e concluímos que a condição de casamento se verifica.
+<wrap right>$\square$</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:
 <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>
-__//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\}$.
   * O conjunto de arestas de $H$ é dado por $\{v_i^+v_{i+1}^- : 1 \leq i \leq n-1\}$.
@@ Linha 20: / Linha 33: @@
 {{ :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>