Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:teoremamader [2023/02/08 12:02] – piva
+++ grafos:teoremamader [2023/02/19 14:04] (atual) – edição externa 127.0.0.1
@@ Linha 6: / Linha 6: @@
 {{ :grafos:1conexo.png?400 |}}
-O grafo desenhado acima é obtido da seguinte maneira: dados dois [[.defcompleto | grafos completos]] de $n$ vértices, adicione um novo vértice adjacente a todos esses. Como a remoção do novo vértice torna esse grafo desconexo, ele é $1-$conexo, mesmo com seu grau mínimo sendo $n$. Uma construção similar é feita abaixo, em que uma aresta é adicionada com extremidades em duas cópias de um $K_n$. Esse é um grafo $1-$aresta-conexo, portanto, mesmo seu grau mínimo sendo $n-1$.
+O grafo desenhado acima é obtido da seguinte maneira: dados dois [[.defcompleto | grafos completos]] de $n$ vértices, adicione um novo vértice adjacente a todos esses. Como a remoção do novo vértice torna esse grafo desconexo, ele é $1-$conexo, mesmo com seu grau mínimo sendo $n$. Vale ressaltar aqui que tal grafo não serioa $2$-conexo, ou seja, sua [[.connectivity| conectividade]] é $1$.
+Uma construção similar é feita abaixo, em que uma aresta é adicionada com extremidades em duas cópias de um $K_n$. Esse é um grafo $1-$aresta-conexo, portanto, mesmo seu grau mínimo sendo $n-1$. Assim, como o ultimo exemplo, vale ressaltar que este grafo não seria $2$-aresta-conexo.
 {{ :grafos:1arestaconexo.png?340 |}}
@@ Linha 26: / Linha 28: @@
 <WRAP round box 100%>
-=== Demonstração 1 ===
+//**Demonstração:**//
-Pelo [[.numtotaldearestas | Lema do Aperto de Mão]], sabemos que $\gamma := \varepsilon(G) = \frac{d(G)}{2}$ é maior ou igual a $2k$. Pela definição de [[.grauMedio| grau médio]], inclusive, deve haver algum vértice de $G$ com grau maior ou igual a $4k$: caso contrário, a média dos graus de $G$ seria no máximo $4k-1$. Em particular, como $k > 0$, há pelo menos $2k$ vértices em $G$. Além disso,
+Pelo [[.numTotaldeArestas|Lema do Aperto de Mão]], sabemos que $\gamma := \varepsilon (G) = \frac {d_{med}(G)}{2}$ é maior ou igual a $2k$; onde $\varepsilon(G)$ é a [[.arestasMedia|quantidade média de arestas por vértices de G]] e $d_{med}(G)$ é o [[.grauMedio| grau médio de $G$]]. Pela definição de grau médio, inclusive, deve haver algum vértice de $G$ com grau maior ou igual a $4k$; caso contrário, a média dos graus de $G$ seria no máximo $4k-1$. Em particular,como $k>0$, há pelo menos $2k$ vértices em $G$.Além disso,
 $$\gamma(|G|-k) = \varepsilon(G)(|G|-k) =\frac{\|G\|}{|G|}(|G|-k) = \|G\|-\frac{k}{|G|}< \|G\|$$
-Em outras palavras, a família $\mathcal{G}$ de subgrafos $G'\subset G$ que satisfazem $|G'|\geq 2k$ e $\|G'\|> \gamma(|G'|-k)$ é não vazia, pois $G\in\mathcal{G}$. Note inclusive que, se $G'\in \mathcal{G}$, então $|G'|> 2k$. Afinal, se tivéssemos $|G'| =  2k$, o subgrafo $G'$ possuiria mais arestas que um grafo completo com $|G'|$ vértices (pois $\|G'\|> \gamma(2k-k) = \gamma k \geq 2k^2 > \binom{|G'|}{2}$), o que é um absurdo.
+Consideremos, então, todos os [[.subgrafos| subgrafos]] $G' \subseteq G$, tal que:
+$$|G'| \geq 2k.(*)$$
+e
+$$||G'|| > \gamma(|G'|-k).(*)$$
-Com isso, considere $H\in \mathcal{G}$ um grafo com o menor número de vértices possível. Suponha por um momento que existe um vértice $v\in V(H)$ de grau no máximo $\gamma$ em $H$ (isto é, $v$ possui no maximo $\gamma$ vizinhos em $H$). Pela observação feita acima, $|H\setminus v| = |H|-1 > 2k-1 \geq 2k$. Além disso, $\|H\setminus v\|\geq \|H\| - \gamma > \gamma(|H|-k)-\gamma = \gamma((|H|-1)-k) = \gamma(|H\setminus v| - k)$. Ou seja, $H\setminus v \in \mathcal{G}$, contradizendo a minimalidade da quantidade de vértices de $H$ como elemento de $\mathcal{G}$. Provamos portanto que $\delta(H) > \gamma$. Em particular, temos $|H|> \gamma$ e disso concluímos que:
+Tais grafos $G'$ existem, haja vista que o próprio grafo $G$ configura um deles. Notemos inclusive que nenhum grafo como em $(*)$ possui ordem exatemnete $2k$, pois isso implicaria  $||G’|| > \gamma k \geq 2k^2 > \binom{|G'|}{2}$. Em outras palavras, se tivéssemos $|G'|=2k$, o subgrafo $G'$ possuiria mais arestas que um [[.defCompleto| grafo completo]] com $|G'|$ vértices, o que é um absurdo. Portanto, temos que $|G'| > 2k$.
-$$\varepsilon(H) = \frac{\|H\|}{|H|} > \frac{\gamma(|H|-k)}{|H|} = \gamma - \frac{\gamma k}{|H|} > \gamma - k = \varepsilon(G)-k$$
+Com isso em mente, considere um grafo $H \subseteq G$ que satisfaça $(*)$ e que seja o grafo com o menor número de vértices possíveis, isto é, o de menor ordem dentre todos os outros grafos $G' \subseteq G$.
-$$\Downarrow$$
-$$ \varepsilon(H) > \varepsilon(G) - k$$
-Finalizando a demonstração, mostraremos que $H$ é também $(k+1)-$conexo. Por um momento, suponha que isso não ocorre e seja $S\subset V(H)$ um [[.separar | separador]] de $H$ com $|S|\leq k$. Seja $V_1$ o conjunto dos vértices de uma das [[.defcompcon | componentes conexas]] de $H\setminus S$ e considere $V_2 = H\setminus (S\cup V_1)$ a coleção dos demais vértices de $H\setminus S$. Com isso, defina os subgrafos $H_1 = H[V_1 \cup S]$ e $H_2 = H[V_2 \cup S]$, de modo que $V(H_1)\cap V(H_2) = S$. Dado $v\in V_1$, a definição de componente conexa nos garante que $v$ não possui vizinhos em $V_2$. Ou seja, todos os seus vizinhos de $H$ se encontram em $H_1$. Como já provamos, porém, o grau mínimo de $H$ é maior que $\gamma$, disso decorrendo que $|H_1|\geq \gamma \geq 2k$. Por um argumento simétrico, $|H_2|\geq \gamma \geq 2k$.
+Suponhamos por um momento que existe um vértice $v \in V(H)$ de grau máximo $\gamma$ em $H$, isto é, $v$ possui no máximo $\gamma$ [[.vizinhosDeV| vizinhos]] em $H$. Segundo esta observação, temos:
-Portanto, pela escolha de $H$ como elemento de menor ordem de $\mathcal{G}$, tem-se que $\|H_1\| \leq \gamma(|H_1|-k)$ e $\|H_2\| \leq \gamma(|H_2|-k)|$. Porém, $A(H) \subset A(H_1) \cup A(H_2)$, pois $H_i$ é definido como o subgrafo de $H$ induzido por $V_i$ e $S$, e, para cada $i=1,2$, os vértices de $V_i$ possuem apenas vizinhos entre si e entre $S$. Logo,
+$$|H \setminus v| = |H|-1 > 2k -1 \geq 2k$$
-\[\|H\| \leq \|H_1\| + \|H_2\| \leq \gamma(|H_1|-k)+\gamma(|H_2|-k) = \gamma(|H_1|+|H_2|-2k) = \gamma(|H|+|S|-2k) = \gamma(|H|+k-2k)\leq \gamma(|H|-k),\] contradizendo o fato de que $H\in \mathcal{G}$. Portanto, $H$ deve ser $(k+1)-$conexo.
-<wrap right>$\square$</wrap>
-</WRAP>
-\\
-----
-<WRAP round box 100%>
-=== Demonstração 2: ===
-Pelo lema do Aperto de Mão, sabemos que $$\gamma := \varepsilon (G) = $\gamma := \varepsilon(G) = \frac{d(G)}{2}$ é maior ou igual a $2k$, e consideremos os subgrafos $G’ \subseteq G$, tal que:
-$$|G’| \geq 2k$$
 e
-$$||G’|| > \gamma (|G’| - k).(*)$$
+$$||H \setminus v || \geq ||H|| - \gamma > \gamma(|H|-k) - \gamma = \gamma((|H-1)-k) = \gamma(|H \setminus v| -k)$$
-Tais grafos $G'$ existem, hava vista que o próprio grafo $G$ configura um deles; seja $H$ o de menor ordem.
+Ou seja, $H \setminus v$ ainda satisfazeria $(*)$, contradizendo a minimalidade de $H$. Portanto, a minimalidade de $H$ implica que $\delta(H) > \gamma$. Em particular, temos $|H| \geq \gamma$. E disso concluimos que:
-Nenhum grafo $G’$ como em $(*)$ possui ordem exatamente $2k$, pois isso implicaria que $||G’|| > \gamma k \geq 2k^2 > \binom{|G'|}{2}$. A minimalidade de $H$, portanto, implica que $\delta (H) > \gamma$. Caso contrário, poderíamos excluir um vértice de grau no máximo $\gamma$ e obter um grafo $G' \subseteq H$ ainda satisfazendo $(*)$. Em particular, temos $|H| \geq \gamma$. Dividindo a inequação $||H|| > \gamma |H| - \gamma k$ de $(*)$ por $|H|$, teremos $\varepsilon (H) > \gamma - k$, como desejado.
+$$\varepsilon(H) = \frac{||H||}{|H|} > \frac{\gamma(|H|-k)}{|H|} = \gamma - \frac{\gamma k}{|H|} = \varepsilon(G) - k$$
+$$\Downarrow$$
+$$\varepsilon(H) > \varepsilon(G) -k$$
-Resta mostrar então que $H$ é $(k+1)$-conexo. Sonhamos que não seja, então  $H$ tem uma separação adequada $\{U_1 , U_2\}$ de ordem no máximo $k$; coloquemos $H[U_i] =: H_i$. Já que qualquer vértice $v \in U_1 \setminus U_2$ respeita a relação: $d(v) \geq \delta (H) > \gamma$ vizinhos de $H$ em $H_1$, temos $|H_1| \geq \gamma \geq 2k$. Similarmente,  $|H_2| \geq 2k$.
+Como desejado.
+----
-Como pela minimalidade de $H$ nem $H_1$ nem $H_2$ satisfaz $(*)$, ainda temos:
+Para finalizar a demonstração, resta mostrar que $H$ é $(k-1)-$conexo. Suponhamos que isso não aconteça e seja $S \subset V(H)$ um [[.separar | separador]] de $H$ com $|S| \leq k$.
+Seja $V_1$ o conjunto dos vértices de uma das [[.defCompCon|componentes conexas]] de $H \setminus S$ e considere $V_2 = H \setminus(S \cup V_1)$ a coleção dos demais vértices de $H \setminus S$. Com isso, defina os subgrafos $H_1 = H[V_1 \cup S]$ e $H_2 = H[V_2 \cup S]$, de modo que $V(H_1) \cap V(H_2) = S$. Dado $v \in V_1$, a definição de componente conexa nos garante que $v$ não possui vizinhos em $V_2$. Ou seja, todos os seus vizinhos de $H$ se encontram em $H_1$. Como já provamos, porém, o grau mínimo de $H$ é maior que $\gamma$, disso decorre que $|H_1| \geq \gamma \geq 2k$. Por um argumento simétrico, temos que $|H_2| \geq \gamma \geq 2k$.
-$$||H_i|| \leq \gamma (|H_i| -k)$$
+Portanto, pela minimalidade de $H$, tem-se que $||H_1|| \leq \gamma(|H_1| -k)$ e $||H_2|| \leq \gamma(|H_2| - k)$, logo, nem $H_1$ nem $H_2$ satisfaz $(*)$. Porém, $A(H) \subset A(H_1) \cup A(H_2)$, pois $H_i$ é definido como o subgrafo de $H$ induzido por $V_i$ e $S$, e, para cada $i = 1,2$ , os vértices de $V_i$ possuem apenas vizinhos entre si e entre $S$. Logo,
-para $i = 1,2$.  Mas então:
+$$||H_i|| \leq \gamma(|h_i|-k)$$
+Mas então:
 $$||H|| \leq ||H_1|| + ||H_2||$$
 $$\Downarrow$$
-$$||H|| \leq \gamma (|H_1| + |H_2| - 2k)$$
+$$||H|| \leq \gamma(|H_1| - k) + \gamma(|H_2|-k)$$
+$$\Downarrow$$
+$$||H|| \leq \gamma(|H_1|+|H_2| -2k)$$
-Como $|H_1 \cap H_2| \leq k$.
+Como $|H_1 \cap H_2| \leq k$. E ainda temos que:
-$$||H|| \leq \gamma (|H_1| + |H_2| - 2k)$$
+$$||H|| \leq \gamma(|H_1|+|H_2| -2k)$$
 $$\Downarrow$$
-$$||H|| \leq \gamma (|H| -k)$$
+$$||H|| \leq \gamma(|H|+|S|-2k)$$
+$$\Downarrow$$
+$$||H|| \leq \gamma(|H|+k-2k)$$
+$$\Downarrow$$
+$$||H|| \leq \gamma(|H|-k)$$
+o que contradiz o fato de $H$ respeitar a relação $(*)$. Portanto, $H$ deve ser $(k+1)-$conexo.
-o que contradiz $(*)$ para $H$.
 <wrap right>$\square$</wrap>