Aqui você vê as diferenças entre duas revisões dessa página.
| Próxima revisão | Revisão anterior |
| grafos:koniginfinity [2022/06/22 14:47] – criada felipe | grafos:koniginfinity [2022/06/22 20:46] (atual) – edição externa 127.0.0.1 |
|---|
| ====== Lema da Infinitude de König ====== | ====== Lema da Infinitude de König ====== |
| |
| | === Sejam $V_0, V_1, ...$ uma sequência infinita de conjuntos disjuntos (não vazios) e $G$ um grafo definido sobre a união dos termos dessa sequência. Se todo vértice $v \in V_n$ com $n \geq 1$ possui um vizinho $f(v) \in V_{n-1}$, então $G$ contém um raio $v_0 v_1 ...$ com $v_n \in V_n$ para todo $n \in \mathbb N$. === |
| |
| | {{ :grafos:konig.png?500 |}} |
| | |
| | ----- |
| | |
| | //Demonstração:// Seja $\mathcal P$ o conjunto de todos os caminhos finitos da forma $v f(v) f\big(f(v)\big) ...$ com extremidade em $V_0$. Como $V_0$ é finito e $\mathcal P$ infinto, podemos afirmar que infinitos caminhos em $\mathcal P$ possuem o mesmo vértice $v_0 \in V_0$ como extremidade. Desses caminhos, infinitos coincidem também em seu penúltimo elemento, $v_1 \in V_1$ --- pois temos, novamente, um conjunto finito. Note que podemos repetir esse processo sucessivamente; apesar do número de caminhos ser cada vez menor, continua sendo infinito depois de qualquer número finito de passos. Desse modo, $v_n$ está definido para qualquer $n \in \mathbb N$. Por hipótese, cada um dos $v_n \in V_n$ é vizinho de um $v_{n-1} \in V_{n-1}$. Assim, $v_0 v_1 ...$ é, de fato, um raio. |