Decomposição em Árvores
Esta técnica “reduz” de certa forma um grafo infinito em uma árvore infinita, é um pouco confuso a forma que se é feito, então vamos pensar assim:
- Primeiramente tome o conjunto de vértices do nosso grafo \(G\)
- Agora iremos criar o que chamamos de Sacos (Bags) \(V_t\), conjunto de vértices de \(G\), atenção, pois os sacos não necessariamente são disjuntas
- Agora iremos “contrair cada saco” em um vértice que chamaremos como o índice do saco, tais novos vértices serão os vértices da nossa Árvore e serão ligados seguindo as seguintes definições
Definição 1
A decomposição em árvores de uma grafo \(G\) é uma dupla \(T,V_t\) onde \(T\) é uma árvore e \(V_t \subset V(G)\), um saco, satisfazendo:
\(\text{a}_1\)) \(\bigcup V_t = V(G)\)
\(\text{b}_1\)) Para toda aresta \(e \in G\) existe \(t \in T\) tal que os vértices conectados a \(e\) estão em \(V_t\)
\(\text{c}_1\)) Se \(b \in aTc\), \(b\) pertence ao caminho que liga \(a\) e \(c\) na árvore \(T\), então \(V_a \cap V_c \subset V_b\)
Definição 1.5
Considere \(G\) grafo, \(\sigma\) ordinal e \(\mathcal{F} = (G_\lambda)_{\lambda < \sigma}\) uma família de subgrafos induzidos de \(G\):
\(\text{a}_{1.5}\)) \(\bigcup G_\lambda = G\)
\(\text{b}_{1.5}\)) Para todo \(\tau\) tal que \(0 < \tau < \sigma\) existe um menor \(\tau^- < \tau \) tal que \(S_{\tau} = (\bigcup_{\lambda < \tau} G_\lambda) \cap G_\tau\) esta contido em \(G_{\tau^-}\)
\(\text{c}_{1.5}\)) Não exite \(G_\lambda\) contido em \(G_\sigma\) para \(\lambda \neq \sigma\)
Podemos notar que se cada \(G_\lambda\) é conexo, então \(G\) é conexo apenas se para todo \(\lambda\) temos que \(S_\lambda \neq \emptyset\)
Definição 2
Com as mesmas suposições anteriores podemos substituir os três itens pelos seguintes:
\(\text{a}_2\)) Para cada vértice \(v \in G\), a árvore \(T_v = \{t \in T : v \in V_t\}\) é subárvore não vazia de \(T\)
\(\text{b}_2\)) Se existe aresta entre \(x,y\) então \(T_x \cap T_y \neq \emptyset\)
Proposição 1
A definição 1 e a Definição 2 são equivalentes Demonstração
Proposição 2
A definição 1 e a Definição 1.5 são equivalentes Demonstração