Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:conexidad [2023/01/24 16:24] – edição externa 127.0.0.1 | grafos:conexidad [2023/09/22 09:21] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | ===== Conexidade ===== | + | ===== O Grafo Conexo |
| - | ==== O Grafo Conexo ==== | + | |
| - | <WRAP round box 60%> | + | <WRAP round box 80%> |
| === Definição === | === Definição === | ||
| - | Um grafo $G$ é dito [[.defConexo|conexo]] se, para todo par de vértices distintos $u,v \in V(G)$ distintos, existir um [[.defCaminho|caminho]] entre eles. Um grafo que não é conexo é dito desconexo. | + | //Um grafo $G$ é dito conexo |
| </ | </ | ||
| Linha 15: | Linha 14: | ||
| {{: | {{: | ||
| - | Mas como determinar se um dado grafo $G$ qualquer, é conexo ou não? Podemos usar o seguinte Teorema: | + | \\ |
| + | |||
| + | Mas como determinar se um dado grafo $G$ qualquer, é conexo ou não? | ||
| <WRAP round box 90%> | <WRAP round box 90%> | ||
| === Teorema === | === Teorema === | ||
| - | Um grafo $G(V, A)$ é desconexo se, e somente se, seu conjunto de vértices $V$ puder ser particionado em dois conjuntos disjuntos e não-vazios, | + | //Um grafo $G=(V, A)$ é desconexo se, e somente se, seu conjunto de vértices $V$ puder ser particionado em dois conjuntos disjuntos e não-vazios, |
| </ | </ | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| == Demonstração == | == Demonstração == | ||
| - | $[⇒]$ Suponhamos que $G$ seja desconexo e mostremos que existe uma partição de $V$, $V_1$ e $V_2$, tal que não existe uma aresta com uma extremidade em $V_1$ e outra extremidade em $V_2$. | + | $[\Rightarrow]$ Suponhamos que $G$ seja desconexo e mostremos que existe uma partição de $V$, $V_1$ e $V_2$, tal que não existe uma aresta com uma extremidade em $V_1$ e outra extremidade em $V_2$. |
| Seja então $G$ um grafo desconexo. Precisamos encontrar uma partição de $V$ que satisfaça a propriedade acima. Considere um vértice $v ∈ V$ qualquer. Forme o conjunto $V_1$ com todos os vértices de $V$ que estejam ligados a $v$ por um caminho. | Seja então $G$ um grafo desconexo. Precisamos encontrar uma partição de $V$ que satisfaça a propriedade acima. Considere um vértice $v ∈ V$ qualquer. Forme o conjunto $V_1$ com todos os vértices de $V$ que estejam ligados a $v$ por um caminho. | ||
| Linha 30: | Linha 31: | ||
| Como $G$ é desconexo, $V_1$ não contém todos os vértices de $G$. Assim os vértices restantes formam um conjunto não-vazio $V_2$, e não existe nenhuma aresta de $G$ com uma extremidade em $V_1$ e outra em $V_2$. Portanto $V_1$ e $V_2$ formam a partição desejada. | Como $G$ é desconexo, $V_1$ não contém todos os vértices de $G$. Assim os vértices restantes formam um conjunto não-vazio $V_2$, e não existe nenhuma aresta de $G$ com uma extremidade em $V_1$ e outra em $V_2$. Portanto $V_1$ e $V_2$ formam a partição desejada. | ||
| - | $[⇐]$ Suponhamos que exista uma partição de $V$, $V_1$ e $V_2$, tal que não existe uma aresta com uma extremidade em $V_1$ e outra extremidade em $V_2$ e mostremos que $G$ é desconexo. | + | $[\Leftarrow]$ Suponhamos que exista uma partição de $V$, $V_1$ e $V_2$, tal que não existe uma aresta com uma extremidade em $V_1$ e outra extremidade em $V_2$ e mostremos que $G$ é desconexo. |
| Considere dois vértices arbitrários $v,w ∈ V$ tais que $v ∈ V_1$ e $w ∈ V_2$. Não pode existir nenhum caminho entre $v$ e $w$, pois se existisse, haveria uma aresta com uma extremidade em $V_1$ e outra em $V_2$. Portanto se uma tal partição existe o grafo é desconexo. | Considere dois vértices arbitrários $v,w ∈ V$ tais que $v ∈ V_1$ e $w ∈ V_2$. Não pode existir nenhum caminho entre $v$ e $w$, pois se existisse, haveria uma aresta com uma extremidade em $V_1$ e outra em $V_2$. Portanto se uma tal partição existe o grafo é desconexo. | ||
| Linha 37: | Linha 38: | ||
| </ | </ | ||
| - | ==== Componente Conexa ==== | + | ===== Componente Conexa |
| - | <WRAP round box 60%> | + | <WRAP round box 80%> |
| === Definição === | === Definição === | ||
| - | As **componentes conexas** de um grafo $G$ são seus pedaços que são isoladamente [[.defConexo|conexos]]. Assim sendo, as componentes conexas de $G$ são [[.subgrafos| subgrafos]] de $G$ que são conexos. | + | //As **componentes conexas** de um grafo $G$ são seus pedaços que são isoladamente [[.defConexo|conexos]]. Assim sendo, as componentes conexas de $G$ são [[.subgrafos| subgrafos]] de $G$ que são conexos.// |
| </ | </ | ||
| Linha 48: | Linha 49: | ||
| {{ : | {{ : | ||
| + | ---- | ||
| <WRAP round info 100%> | <WRAP round info 100%> | ||
| === Referências === | === Referências === | ||
| * Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo.[[https:// | * Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo.[[https:// | ||
| </ | </ | ||