Diferenças

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

--- grafos:teoremahall [2023/03/08 10:46] – piva
+++ grafos:teoremahall [2023/03/15 12:07] (atual) – edição externa 127.0.0.1
@@ Linha 5: / Linha 5: @@
 Um [[.defgerador | subgrafo gerador]] [[.karegular | $k-$regular]] é chamado de [[.kfator | $k-$fator]]. Assim, um subgrafo $H \subseteq G$ é $1$-fator de $G$ se, e somente se, $E(H)$ é um [[.matching | emparelhamento]] de $V$. Surge então o problema de como caracterizar os grafos que possuem um $1$-fator, ou seja, um emparelhamento de todo o seu conjunto de vértices.  A busca de algumas condições necessárias e suficientes para a existêcia de um $1$-fator, é um dos principais temas na área do emparelhamento.
-Em nosso caso atual de um grafo bipartido, podemos também perguntar de forma mais geral quando $G$ contém um emparelhamento de $A$; isso definirá um $1$-fator de $G$ se $|A|=|B|$, uma condição que deve ser mantida de qualquer maneira se $G$ tiver um $1$-fator.
+Em nosso caso atual de um grafo bipartido, podemos também perguntar de forma mais ´geral quando $G$ contém um emparelhamento de $A$; isso definirá um $1$-fator de $G$ se $|A|=|B|$, uma condição que deve ser mantida de qualquer maneira se $G$ tiver um $1$-fator.
 Uma vez que os vértices de partes iguais em um grafo bipartido $G$ não são adjacentes, observa-se que um emparelhamento descreve uma função entre subconjuntos das partes de $G$. Mais precisamente, se $A$ e $B$ denotam as partes dos vértices de $G$, dado $M$ um emparelhamento, fixe $A'$ a coleção dos vértices de $A$ que são pontas de arestas de $M$. Assim, como duas arestas de um emparelhamento nunca possuem uma mesma extremidade, para cada $a\in A'$ existe um único $v_a\in B$ tal que $av_a \in M$. Pelo mesmo argumento, se $v_a = v_b$, então $a,b\in A'$ são iguais. Ou seja, a aplicação $a \mapsto v_a$ descreve uma função injetora entre os conjuntos $A'$ e $B$. Nesta página, estamos interessados em descobrir quando essa função pode estar definida em todo o conjunto $A$.
@@ Linha 63: / Linha 63: @@
 Para a prova a seguir, faremos uma indução no número de vértices da parte $A$:
 <WRAP round box 100%>
@@ Linha 101: / Linha 69: @@
 **$1.$** Suponha que, para todo subconjunto próprio não vazio $S\subset A$, a condição de casamento é satisfeita "com folga", isto é, que $|N(S)|\geq |S|+1$. Com isso, fixada $ab \in E$ é uma aresta qualquer, defina o grafo $G' = G[V\setminus \{a,b\}]$. Então, dado $S\subset A\setminus \{a\}$ um subconjunto qualquer, tem-se por hipótese que $|S|\leq |N(S)|-1$. Por sua vez, $N(S)\subset \{v\in B : uv \in E(G')\text{ para algum }u\in S \}\cup \{b\}$, de onde concluímos que
-$$|\{v\in B : uv \in E(G')\text{ para algum }u\in S \}| := |N_{G'}(S)| \geq |N(S)|-1 \geq |S|$$
+$$|\{v\in B : uv \in E(G')\text{ para algum }u\in S \}| := |N_{G'}(S)| \geq |N(S)|-1 \geq |S|,$$
 Ou seja, em $G'$ a condição de casamento é satisfeita, de modo que, por hipótese indutiva, existe $M$ um emparelhamento de $G'$ que cobre os vértices de $A\setminus \{a\}$. Como as arestas de $G'$ não contém o vértice $b$ como extremidade, $M\cup \{ab\}$ é também um emparelhamento de $G$. Como ele cobre todos elementos de $A$, finalizamos o processo indutivo para esse caso.
-**$2.$** Se o caso acima não ocorre, pela condição de casamento deve existir $A'\subset A$ um subconjunto próprio não vazio tal que $|N(A')| = |A'|$. Denotanto $B' = N(A')$, considere $G' = G[A'\cup B']$. Observamos que em $G'$ a condição de casamento também se verifica, pois, dado $S\subset A'$, tem-se que $|S| \leq |N(S)| \leq |\{v \in B : uv \in E(G')\text{ para algum }u\in S\}|$, visto que $N(S)\subset N(A') = B'$ e que $G'$ é o subgrafo induzido pelos vértices $A'$ e $B'$. Assim, como $A'$ é um subconjunto próprio de $A$, por hipótese indutiva existe $M'$ um emparelhamento de $G'$ que cobre os vértices do conjunto $A'$. Por outro lado, o subgrafo induzido $G^* = G[V\setminus (A'\cup B')]$ também satisfaz a condição de casamento. Para mostrarmos isso, fixe $S\subset A\setminus A'$ qualquer. Como $|A' \cup S|\leq |N(A' \cup S)|$ pela condição de casamento, $|A'| = |N(A')| = |B'|$ por hipótese e $N(A'\cup S) = B' \cup \{v \in B\setminus B' : uv \in E \text{ para algum }u\in S \} = B' \cup \{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}$ , devemos ter $|S|\leq |\{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}|$, verificando a condição de casamento em $G^*$. Ou seja, por hipótese indutiva $G^*$ também admite um emparelhamento $M^*$ que cobre os vértices de $A\setminus A'$. Como $G'$ e $G^*$ não possuem vértices em comum, $M'\cup M^*$ é um emparelhamento em $G$, que cobre os elementos de $A$. Isso finaliza o processo indutivo nesse caso.
+**$2.$** Se o caso acima não ocorre, pela condição de casamento deve existir $A'\subset A$ um subconjunto próprio não vazio tal que $|N(A')| = |A'|$. Denotanto $B' = N(A')$, considere $G' = G[A'\cup B']$. Observamos que em $G'$ a condição de casamento também se verifica, pois, dado $S\subset A'$, tem-se que $|S| \leq |N(S)| \leq |\{v \in B : uv \in E(G')\text{ para algum }u\in S\}|$, visto que $N(S)\subset N(A') = B'$ e que $G'$ é o subgrafo induzido pelos vértices $A'$ e $B'$. Assim, como $A'$ é um subconjunto próprio de $A$, por hipótese indutiva existe $M'$ um emparelhamento de $G'$ que cobre os vértices do conjunto $A'$.
+Por outro lado, o subgrafo induzido $G^* = G[V\setminus (A'\cup B')]$ também satisfaz a condição de casamento. Para mostrarmos isso, fixe $S\subset A\setminus A'$ qualquer. Como $|A' \cup S|\leq |N(A' \cup S)|$ pela condição de casamento, $|A'| = |N(A')| = |B'|$ por hipótese e $N(A'\cup S) = B' \cup \{v \in B\setminus B' : uv \in E \text{ para algum }u\in S \} = B' \cup \{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}$ , devemos ter $|S|\leq |\{v\in B\setminus B' : uv \in E(G^*) \text{ pra algum }u\in S\}|$, verificando a condição de casamento em $G^*$. Ou seja, por hipótese indutiva $G^*$ também admite um emparelhamento $M^*$ que cobre os vértices de $A\setminus A'$. Como $G'$ e $G^*$ não possuem vértices em comum, $M'\cup M^*$ é um emparelhamento em $G$, que cobre os elementos de $A$. Isso finaliza o processo indutivo nesse caso.
 <wrap right>$\square$</wrap>
@@ Linha 111: / Linha 81: @@
 ----
-Embora no Teorema de Hall uma das partes do grafo bipartido $G$ seja privilegiada para ser coberta por um emparelhamento, sob certas hipóteses ele pode ser aplicado para encontrar um emparelhamento que cobre todos os vértices:
+<WRAP round tip box 100%>
+=== Veja também: ===
-<WRAP round box 100%>
+  * [[.conseqHall | Consequências do Teorema de Hall]]
-**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>
-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]].
-</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:
-  * 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\}$.
-A figura a seguir ilustra a construção dos vértices e arestas de $H$ a partir de vértices e arestas de $G$, em que as setas nas arestas de $G$ indicam o sentido em que elas são utilizadas no circuito euleriano.
-{{ :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>