Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

===== O Grafo Conexo ===== <WRAP round box 80%> === Definição === //Um grafo $G$ é dito conexo se não for vazio e 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.// </WRAP> O grafo abaixo por exemplo é um **grafo conexo:** {{:grafos:graph_13_.png?300|}} E o pŕoximo, é um exemplo de **grafo desconexo:** {{:grafos:graph_14_.png?300|}} \\ Mas como determinar se um dado grafo $G$ qualquer, é conexo ou não? <WRAP round box 90%> === 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, $V_1$ e $V_2$, de forma que não exista uma aresta com uma extremidade em $V_1$ e outra extremidade em $V_2$.// </WRAP> <WRAP round box 100%> == Demonstração == $[\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. 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. $[\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. <wrap right>$\square$</wrap> </WRAP> ===== Componente Conexa ===== <WRAP round box 80%> === 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.// </WRAP> Na imagem abaixo, $4 \to 5 \to 6$ e $6 \to 8 \to 9$ são exemplos de componentes conexas. {{ :grafos:compcon.png }} ---- <WRAP round info 100%> === Referências === * Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo.[[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/grafosconexos.pdf|"Teoria dos Grafos: Grafos Conexos"]] .2002-2013. Acesso em 16/09/2022. </WRAP>