| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:defunfriendlypartition [2022/06/22 11:56] – leofm10 | grafos:defunfriendlypartition [2022/06/22 14:57] (atual) – edição externa 127.0.0.1 |
|---|
| Uma bipartição do conjunto de vértices de um grafo é dita uma //**unfriendly partition**// se cada vértice possui um número de vértices vizinhos da classe oposta a sua maior ou igual que o número de vértices vizinhos de sua própria classe. | **Definição:** Uma bipartição do conjunto de vértices de um grafo é dita uma //**unfriendly partition**// se cada vértice possui um número de vértices vizinhos da classe oposta a sua maior ou igual que o número de vértices vizinhos de sua própria classe. |
| |
| **Proposição:** Todo grafo finito possui uma //unfriendly partition//. | **Proposição:** Todo grafo finito possui uma //unfriendly partition//. |
| |
| //Demonstração//: De fato, basta tomar a partição que maximiza o número de arestas entre as classes. Desta forma, suponha que exista uma vértice que possui mais vizinhos de sua mesma classe que da classe oposta, trocando a classe do vértice obtemos uma partição com ainda mais arestas entre as classes. Contradição! | //Demonstração//: De fato, basta tomar a partição que maximiza o número de arestas entre as classes. Desta forma, suponha que exista uma vértice que possui mais vizinhos de sua mesma classe que da classe oposta, trocando a classe do vértice obtemos uma partição com ainda mais arestas entre as classes. Contradição! $\blacksquare$ |
| |
| **Proposição:** Todo grafo enumerável localmente finito possui uma //unfriendly partition//. | **Proposição:** Todo grafo enumerável localmente finito possui uma //unfriendly partition//. |
| Temos $\mathcal{V}_n\ne\varnothing$ pela proposição anterior. | Temos $\mathcal{V}_n\ne\varnothing$ pela proposição anterior. |
| |
| Para todo $n\ge1$, todo $(U_n,V_n)\in\mathcal{V}_n$ (de $V_n$) induz uma partição $(U_{n-1},V_{n-1})\in\mathcal{V}_{n-1}$ (de $V_{n-1}$). Então pelo __Lema de König__ | Para todo $n\ge1$, todo $(U_n,W_n)\in\mathcal{V}_n$ (de $V_n$) induz uma partição $(U_{n-1},W_{n-1})\in\mathcal{V}_{n-1}$ (de $V_{n-1}$). Então, pelo [[.koniginfinity | Lema da Infinitude de König]] existe uma sequência infinita de partições onde cada $(U_n,W_n)\in\mathcal{V}_n$ é induzido pelo próximo elemento da sequência (um $(U_{n+1},W_{n+1})\in\mathcal{V}_{n+1}$). |
| | |
| | Então $(\underset{n\in\mathbb{N}}{\bigcup}U_n,\underset{n\in\mathbb{N}}{\bigcup}W_n)$ é uma //unfriendly partition// de $G$. $\blacksquare$ |
| | |
| | Sabemos então que todo grafo finito e todo grafo enumerável localmente finito possui //unfriendly partition//. |
| | |
| | Existe um contra-exemplo para grafo não enumerável, mas a resposta para um grafo enumerável qualquer ainda permanece em aberto. |