grafos:raylessideiaseprops [WikiMat]

==== 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.

<WRAP round box>
=== 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)\)

</WRAP>

Agora a partir de tal classe podemos definir a Classe de Schmidt´s, um caso específico e interessante:

<WRAP round box>
=== 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\)
</WRAP>

Tal classe é também reconhecida como a classe dos grafos sem raio (Rayless Graphs), tal visualização pode ser vista da seguinte forma:

<WRAP info>
=== Proposição 1 ===
\(A\) é a classe dos grafos sem raio <wrap help>[[provaprop1rayless|Demonstração]]</wrap>
</WRAP>

<WRAP info>
=== Proposição 2 ===
Se \(G \in A\) e \(H \subset G\) então \(H \in A\) e \(\circ(H) \leq \circ(G)\) <wrap help>[[provaprop2rayless|Demonstração]]</wrap>
</WRAP>

<WRAP info>
=== 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\) <wrap help>[[provaprop3rayless|Demonstração]]</wrap>

</WRAP>

A partir dessa proposição conseguimos alguns corolário interessantes e imediatos:

<WRAP info>
=== 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\) <wrap help>[[cororayless1|Ideia]]</wrap>

Se \(G\) é grafo em raio e \(F \subset G\) é finito, então \(\circ(G \setminus F) = \circ(G)\) <wrap help>[[cororayless2|Ideia]]</wrap>

Se \(G\) é grafo em raio e \(F \subset G\) é finito, tome \(\{G_i\}_i\) as distintas componentes de \(G \setminus F\), temos então <wrap help>[[cororayless3|Ideia]]</wrap>:

$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.$

</WRAP>

<WRAP round box>
=== 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)\)

</WRAP>

<WRAP info>
=== 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 é <wrap help>[[raylesslema1.1|Demonstração]]</wrap>

b)Se \(\mathcal{C}\) é ordem determinante, então ele pode ser decomposto em enumeráveis e disjuntos subconjuntos ordem determinantes <wrap help>[[raylesslema1.2|Demonstração]]</wrap>
</WRAP>

<WRAP info>
=== 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 <wrap help>[[raylesslema2|Demonstração]]</wrap>
</WRAP>

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.

<WRAP round box>
=== Definição ===
O Kernel \(K(G)\) de um grafo sem raio é o único redutor minimal de \(G\)

</WRAP>

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.

<WRAP info>
=== 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)\) <wrap help>[[raylessprop4|Demonstração]]</wrap>

</WRAP>

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.

<WRAP round box>
=== 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)\)

</WRAP>

<WRAP info>
=== Proposição 5 ===
Se \(S\) é um Subkernel de \(G\), então \(K(G_s) = S\) <wrap help>[[raylessprop5|Demonstração]]</wrap>

</WRAP>

<WRAP info>
=== Proposição 6 ===
Se \(G\) é um garfo sem raio, então \(K(G)\) é a união dos Subkernels de \(G\) <wrap help>[[raylessprop6|Demonstração]]</wrap>

</WRAP>

<WRAP info>
=== 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\)<wrap help>[[raylesslema3|Demonstração]]</wrap>

</WRAP>

<WRAP info>
=== 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\) <wrap help>[[raylesscorolario4|Demonstração]]</wrap>


</WRAP>