Seja $G$ um grafo com a seguinte propriedade: existem $H_1$ e $H_2$ subgrafos disjuntos de $G$ que são a ele isomorfos. Fixe $S\subset V(G)$ finito qualquer. Mostraremos então que existe $H$ um subgrafo de $G$ a ele isomorfo tal que $V(H)\cap S = \emptyset$. Isso será feito algoritmicamente da seguinte forma:

  • Considere $H_0$ como um dos subgrafos de $G$ que é a ele isomorfo. Se $V(H_0) \cap S = \emptyset$, acabamos.
  • Suponha que definimos $H_0,H_1,\dots,H_n$ subgrafos de $G$ que são a ele isomorfos e tais que $H_i$ é subgrafo de $H_{i+1}$ para todo $1 \leq i \leq n-1$. Por hipótese, sabemos que existem $K$ e $K'$ subgrafos disjuntos de $H_n$ que são a ele isomorfos (e, portanto, isomorfos a $G$). Se algum deles não intersecta $S$, finalize o algoritmo. Se não, como $V(K)\cap V(K')=\emptyset$, tem-se que $|V(K)\cap S| < |V(H_n) \cap S|$. Considere então $H_{n+1} = K$.

Com essa recursão, observamos que, se $H_n$ está definido para algum $n \in \mathbb{N}$, então $|V(H_0)\cap S|> |V(H_1)\cap S|> |V(H_2)\cap S| > \dots > |V(H_n) \cap S|$. Como o conjunto $S$ é finito, contudo, o algoritmo deve eventualmente ser finalizado, encontrando o subgrafo desejado.

Em particular, se $G$ é conexo, ele deve conter um raio. Caso contrário, $G$ teria um rank (digamos, $\alpha$) e um núcleo $\mathrm{K}(G)$ não vazio que atestaria isso. Entretanto, em alguma componente conexa de $G\setminus \mathrm{K}(G)$, pelo que acabamos de provar, haveria um subgrafo isomorfo a $G$. Esse subgrafo, porém, estaria contido em uma componente conexa de $G\setminus \mathrm{K}(G)$, que possui rank menor que $\alpha$. Isso mostaria que $\mathrm{rk}(G) < \alpha$, o que é um absurdo

  • grafos/raioemgemeos.txt
  • Última modificação: 2022/07/03 20:08
  • por 127.0.0.1