grafos:teoremahall

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:teoremahall [2023/03/10 12:08] – edição externa 127.0.0.1grafos: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. 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$. 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$: Para a prova a seguir, faremos uma indução no número de vértices da parte $A$:
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
  
 <WRAP round box 100%> <WRAP round box 100%>
  • grafos/teoremahall.1678460923.txt.gz
  • Última modificação: 2023/03/10 12:08
  • por 127.0.0.1