Classe de Grafos
Antes de falarmos sobre os grafos sem raios iremos definir uma classe de grafos que possui uma peculiaridade interessante, ao tomarmos um caso específico dela, obtemos justamente os grafos sem raio, tal identificação será mostrada, logo após sua identificação.
Definição (Classe de grafos)
Considerando \(\Gamma\) e \(\Sigma\) classes de grafos ambas fechadas com respeito a isomorfismos e \(\Gamma\) fechada com respeito a subgrafos, então dado \(\lambda\) ordinal podemos definir as classes \(A_{\Gamma,\Sigma}(\lambda)\) da seguinte forma :
- \(A_{\Gamma,\Sigma}(0) = \Gamma\)
- Se \(\lambda >0 \) e \(A_{\Gamma,\Sigma}(\mu)\) definido para \(\mu < \lambda\), então \(G \in A_{\Gamma,\Sigma}(\lambda)\) se tomado \(S \subset G\) tal que \(S \in \Sigma\), as componentes conexas \(C_i \in G\setminus S \in A_{\Gamma,\Sigma}(\mu)\) para algum \(\mu\)
- Denotamos \(A_{\Gamma,\Sigma} = \bigcup A_{\Gamma,\Sigma}(\lambda)\)
Agora a partir de tal classe podemos definir a Classe de Schmidt´s, um caso específico e interessante:
Definição
Dado \(A_{\Gamma,\Sigma}(0) = \Gamma\), definimos como Classe de Schmidt´s caso \(\Sigma = \Gamma = \Phi\), sendo \(\Phi\) a classe dos grafos finitos e denotamos \(A_{\Gamma,\Sigma} = A\), assim a definição fica da seguinte forma:
- \(A(0) = \Phi\)
- Se \(\lambda >0 \) e \(A(\mu)\) definido para \(\mu < \lambda\), então \(G \in A(\lambda)\) se tomado \(F \subset G\) finito, as componentes conexas \(C_i \in G\setminus F \in A(\mu)\) para algum \(\mu\)
- Denotamos \(A = \bigcup A(\lambda)\)
Para todo \(G \in A\), existe ao menos algum \(\lambda\) mínimo tal que \(G \in A(\lambda)\), tal \(\lambda\) é dito a ordem de \(G\) (\(\circ(G)\))
Se \(\circ(G)>0\) então existe \(F \subset V(G)\) finito tal que para toda componente \(C_i \in G \setminus F\) temos que \(\circ(C_i) < \circ(G)\), tal \(F\) é dito redutor ou conjunto de redução de \(G\)
Tal classe é também reconhecida como a classe dos grafos sem raio (Rayless Graphs), tal visualização pode ser vista da seguinte forma:
Proposição 1
\(A\) é a classe dos grafos sem raio Demonstração
Proposição 2
Se \(G \in A\) e \(H \subset G\) então \(H \in A\) e \(\circ(H) \leq \circ(G)\) Demonstração
Proposição 3
Para \(G\) grafo sem raio e um ordinal \(\lambda\) são equivalentes:
a)\(\circ(G)> \lambda\)
b)Se \(F\) é redutor de \(G\), então \(G \setminus F\) possui infinitas componentes conexas disjuntas de ordem \(\geq \lambda\)
c)Existem infinitos subgrafos conexos disjuntos de \(G\) com rodem \(\lambda\) Demonstração
A partir dessa proposição conseguimos alguns corolário interessantes e imediatos:
Corolários 1,2 e 3
Para um grafo sem raio \(G\), \(\circ(G)\) é o menor \(\lambda\) tal que não existem infinitos subgrafos conexos disjuntos de ordem \(\lambda\) Ideia
Se \(G\) é grafo em raio e \(F \subset G\) é finito, então \(\circ(G \setminus F) = \circ(G)\) Ideia
Se \(G\) é grafo em raio e \(F \subset G\) é finito, tome \(\{G_i\}_i\) as distintas componentes de \(G \setminus F\), temos então Ideia:
$o(G)=\left\{\begin{array}{lll}a) & \max _{i \in I} o\left(G_i\right), & \text{ Se o máximo existe e é atingido por apenas finitos } \\ b) & \sup _{i \in I} o\left(G_i\right), & \text{ Se } \circ(G) \text{ não possui máximo } \\ c) & \max _{i \in I} o\left(G_i\right)+1, & \text{ Se o máximo existe e é atingido por infinitos } i`s \end{array}\right.$
Definição
\(G\) grafo sem raio e \(F\) redutor de \(G\), a família \(\mathcal{C}\) de componentes de \(G \setminus F\) é dita ordem determinante se \(\circ(\cup \mathcal{C}) = \circ(G)\)
Lema 1
Seja \(G\) grafo sem raio, \(F\) redutor de \(G\) e \(\mathcal{C}\) e \(\mathcal{C}`\) conjuntos de componentes de \(G \setminus F\)
a)Se \(\mathcal{C}\cup\mathcal{C}`\) é ordem determinante, ao menos um deles também é Demonstração
b)Se \(\mathcal{C}\) é ordem determinante, então ele pode ser decomposto em enumeráveis e disjuntos subconjuntos ordem determinantes Demonstração
Lema 2
Sejam \(F, F`\) dois redutores de um grafo sem raio \(G\), assuma que \(x \in F \setminus F`\), então \(F \setminus x\) é redutor Demonstração
Agora que entendemos bem algumas propriedades do redutor uma pergunta talvez venha a sua mente, qual o mínimo para um conjunto se tornar um redutor?, a resposta para esta pergunta para tal pergunta é, ele deve conter o Kernel do grafo, iremos agora definir tal estrutura e ver suas propriedades.
Definição
O Kernel \(K(G)\) de um grafo sem raio é o único redutor minimal de \(G\)
Devido ao Lema 2 temos que realmente o Kernel deve ser único, pois podemos tomar \(F\) e \(F`\) os redutores do Lema 2 como disjuntos, supondo ambos como minimais, conseguiríamos que se \(x \in F \setminus F´\), então \(F \setminus x\) é redutor, o que iria contradizer a minimalidade de \(F\), dessa forma um deles não é redutor.
Proposição 4
Um conjunto finito de vértices em um grafo \(G\) sem raios é redutor em \(G\) se e somente se contém \(K(G)\) Demonstração
Para terminar nosso estudo inicial sobre grafos sem raio, iremos definir e mostrar algumas propriedades sobre o Subkernel, em geral esta parte será apenas algo adicional, ou seja, um conjunto de curiosidades, após isso será mostrado uma rápida aplicação.
Definição
Tome grafo sem raio \(G\) de Kernel \(K\), para \(S \subset K\), o conjunto das componentes \(C \in G \setminus K\) com vizinhos em \(S\) é denotado por \(\mathcal{C}_S\) e definimos
\[G_S = G[S \cup \bigcup \mathcal{C}_S]\]
chamamos \(S\) de Subkernel de \(G\) se \(\mathcal{C}_S\) é ordem determinante, ie, \(\circ(G) = \circ(G_S)\)
Proposição 5
Se \(S\) é um Subkernel de \(G\), então \(K(G_s) = S\) Demonstração
Proposição 6
Se \(G\) é um garfo sem raio, então \(K(G)\) é a união dos Subkernels de \(G\) Demonstração
Lema 3
Tome \(S\) conjunto finito de \(G\) grafo sem raio, seja então \(\mathcal{C}\) as componentes de \(G \setminus S\) tal que:
a)\(\circ(C) < \circ(G)\) para todo \(C \in \mathcal{C}\)
b)\(\circ(\bigcup \mathcal{C}) = \circ(G)\)
c)\(\mathcal{NC} = S\) para todo \(C \in \mathcal{C}\)
então \(S\) é Subkernel de \(G\)Demonstração
Corolário 4 (Aplicação)
Todo Grafo sem raio \(G\) possui \(F \subset G\) finito com \(\delta(F) \geq \delta(G)\), ie, \(\delta(G) = \min\{d(v): v \in V(G)\}\), onde \(d(v)\) é o grau de um vértice \(v\) Demonstração