Caminhos e conexidade

Um caminho⁴ num grafo $G$ é uma sucessão de vértices e arestas

com $v_i\in V_G$, tais que . Ou seja, . Num digrafo, as arestas são tais que $x_i=(v_{i-1},v_i)$, ou seja, a extremidade inicial de $x_i$ é $v_{i-1}$ e a final é $v_i$.

Visto não considerarmos multigrafos, esse caminho é denotado por $( v_0,v_1,v_2, \dots, v_n)$, ou mais simplesmente

e dizemos que existe um caminho . Neste caso, $v_n$ é alcançável de $v_0$. Um caminho diz-se trivial se só tiver um vértice, sem lacete.

Definições análogas podem ser dadas para digrafos.

Um caminho é

• fechado se , e aberto caso contrário;
• simples⁵ se $x_i\ne x_j$, para $i\ne j$;
• elementar⁶ se $v_i\ne v_j$, para $i\ne j$, excepto possivelmente o inicial e o final.

Note-se com um caminho elementar é simples, mas que o contrário é falso.

Um ciclo⁷ é um caminho fechado elementar não trivial. Um circuito⁸ é um caminho fechado simples não trivial.

Recuperamos um grafo que apresentámos atrás:

$$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] & \\ y \ar@{-}[d] \ar@{-}[rrd] && v\ar@{-}[d]\ar@{-}[lld]\\ x \ar@{-}[rr] && w}$$

Um caminho é, por exemplo, . Repare que este caminho repete um vértice mas não repete nenhuma aresta. Portanto, é um caminho simples que não é elementar. Já $xvux$ é um ciclo e $xvuxywx$ é um circuito.

Um grafo que é um ciclo com $n$ vértices denota-se por , e um grafo que é um caminho elementar com $n$ vértices denota-se por $P_n$. é usualmente denominado triângulo.

	$\xymatrix{ \bullet \ar@{-}[d] \ar@{-}[r] & \bullet\\ \bullet \ar@{-}[ru]}$	$\xymatrix{ \bullet \ar@{-}[d] \ar@{-}[r] & \bullet\\ \bullet \ar@{-}[r] & \bullet\ar@{-}[u]}$
		$C_4$

$P_2$	$P_3$

Um grafo é conexo se, para quaisquer vértices $v_i,v_j$ distintos, existe um caminho $v_i - v_j$. Portanto, um grafo é conexo se quaisquer dois vértices forem alcançáveis um do outro.

Dado um grafo ${\cal{G}}$, podemos definir a seguinte relação em ${\cal{V}}_{\cal{G}}$, que é de equivalência:

$$v_i \rho v_j$$    se existe um caminho $$v_i - v_j.$$

As componentes conexas (ou simplesmente componentes) são os subgrafos induzidos pelas classes de equivalência. Ou seja, uma componente conexa é um subgrafo maximal conexo de $G$.

O comprimento $\ell (\gamma)$ de um caminho $\gamma$ é o número de arestas desse caminho. Denota-se por $\Gamma_{i,j}^k$ o conjunto de todos os caminhos de comprimento $k$ do vértice $V_i$ para o vértice $V_j$, e por $\Gamma_{uv}$ o conjunto de todos os caminhos . Se $\gamma=(v_0,v_1,\dots,v_n)$ contiver um caminho fechado $\omega=(v_k,\dots,v_k)$, uma redução $\phi$ do caminho $\gamma$, $\gamma-\omega$, é o caminho obtido de $\gamma$ a que se retirou todas as arestas e vértices de $\omega$ à excepção de $v_k$. De forma recíproca, a concatenação de dois caminhos $\gamma=(v_0,v_1,\dots, v_k),\omega=(v_k,v_{k+1},\dots,v_n)$ é o caminho $\gamma \circ \omega=(v_0,v_1,\dots, v_k,v_k,v_{k+1},\dots,v_n)$.

Proposição 5.1   Todo o caminho não fechado $\gamma$ contém um caminho elementar.

Se $\gamma$ é caminho elementar, então não há nada a provar. Suponhamos então que $\gamma$ não é um caminho elementar. Ou seja, existe um vértice $v_k$ repetido em $\gamma$,

$$\gamma=v_0v_1\cdots v_{i-1}v_k v_{i+1}\cdots v_{j-1}v_k v_{j+1}\cdots v_N.$$

Sejam $\omega=v_k v_{i+1}\cdots v_{j-1}v_k$ e $\gamma '=\gamma - \omega$. Se $\gamma$ é um camminho elementar, então a prova está concluída; caso contrário, repete-se o processo até se obter um caminho elementar.

A distância $d(u,v)$ entre os vértices $u$ e $v$ distintos é o comprimento do menor caminho elementar que os une; caso não exista um tal caminho, $d(u,v)=\infty$. Assume-se que $d(u,u)=0$. Note-se que:

1. $d(u,v)\ge 0$ e $d(u,v)=0 \Leftrightarrow u=v$;
2. $d(u,v)=d(v,u)$;
3. $d(u,w)\le d(u,v)+d(v,w)$.

Uma geodésica entre $u$ e $v$ é um caminho elementar minimal . O diâmetro $d(G)$ de um grafo conexo $G$ é o comprimento da maior geodésica.

Proposição 5.2   Um $n$-grafo ${\cal{G}}$, com $n\ge 2$, é bipartido se e só se não tiver ciclos de comprimento ímpar.

Suponhamos que no grafo bipartido ${\cal{G}}$ (sendo $\{V_1,V_2\}$ a partição do conjunto dos vértices de ${\cal{G}}$ na definição de grafo bipartido) existe um ciclo $\gamma=v_0\cdots v_nv_0$ tal que $\ell (\gamma)$ é ímpar, ou seja, que tem um número ímpar de arestas. Ou seja, o ciclo tem um número ímpar de vértices, já que é um caminho fechado e nenhum vértice surge repetido. Então $v_0, v_n \in V_1$ ou em alternativa $v_0,v_n \in V_2$. Se $v_n \in V_1$ e como $\{v_n,v_0 \}$ é aresta de $\gamma$, segue que $v_0 \in V_2$ e portanto $v_0 \in V_1 \cap V_2 = \emptyset$. O caso $v_n \in V_2$ é análogo.

Suponhamos agora que ${\cal{G}}$ é um $n$-grafo, com $n\ge 2$, sem ciclos de comprimento ímpar. Sem perda de generalidade, assume-se com ${\cal{G}}$ é conexo. Fixemos $u \in V_{\cal{G}}$ e definamos os conjuntos $V_1=\{v\in V_{\cal{G}}: d(u,v)$    é par$\}$ e $V_2=\{v\in V_{\cal{G}}: d(u,v)$    é Ãmpar$\}$. Como é óbvio, $\{V_1,V_2\}$ é uma partição de $V_{\cal{G}}$. Resta-nos mostrar que vértices no mesmo elemento da partição não são vizinhos. Por absurdo, vamos supor que existe $e=\{w,v\}$ com $w,v\in V_1$ (o caso de ambos pertencerem a $V_2$ é análogo). Sendo o grafo conexo, então e $u-w$. Sejam $\gamma_v,\gamma_w$ as geodésicas entre $u$ e $v$ e entre $u$ e $w$, respectivamente. Então existe o vértice $P$, comum aos dois caminhos e que torna a secção $u\cdots P$ de comprimento máximo. Ou seja, $P$ é o último vértice comum às duas geodésicas, e portanto as secções $u\cdots P$ de $\gamma_1$ e $u\cdots P$ de $\gamma_2$ têm o mesmo comprimento. Como $w,v\in V_1$ então tem igual paridade o comprimento das secções $P\cdots v$ e $P\cdots w$. Se forem pares, então a concatenação dos caminhos $\gamma_1,e,\gamma_2$ define um ciclo de comprimento ímpar. O mesmo se conclui se os comprimentos forem ímpares, o que contradiz a hipótese do grafo não ter ciclos ímpares.

O grafo seguinte não contém ciclos de comprimento ímpar

$$\xymatrix{ & \bullet \ar@{-}[r]\ar@{-}[rdd] & \bullet \ar@{-}[rd]... ...-}[ru]\ar@{-}[rd] & & & \bullet\ar@{-}[ld]\\ & \bullet\ar@{-}[r] & \bullet & }$$

pelo que é bipartido. Como exercício, descreva os ciclos e encontre a partição do conjunto dos vértices.

Proposição 5.3   Todo o circuito contém um ciclo.

Seja $\omega$ um circuito num grafo ${\cal{G}}$. Se $\omega$ é ciclo então não há nada a provar. Se não é, então existem dois vértices $v_0,v_k$ repetidos. Ou seja, existe uma secção $\phi$ do circuito $\omega$ que é um caminho fechado. Como $\omega$ não tem arestas repetidas, então $\phi$ é um circuito. Se $\phi$ é ciclo, então a prova está terminada. Se não, então repete-se o processo até se obter um ciclo.

Vejamos agora como se pode mostrar o não isomorfismo de grafos à custa da noção de conexidade que temos estudado nesta secção.

Teorema 5.4   Supondo ${\cal{G}}\cong_\varphi {\cal{H}}$,

1. se $\gamma=v_0v_1\cdots v_k$ é um caminho de comprimento $r$ de ${\cal{G}}$ então $\varphi(\gamma)=\varphi(v_0)\varphi(v_1)\cdots \varphi(v_k)$ é um caminho de comprimento $r$ de ${\cal{H}}$.
2. a imagem por $\varphi$ de um caminho simples [resp. caminho elementar, ciclo] é um caminho simples [resp. caminho elementar, ciclo] com o mesmo comprimento.
3. ${\cal{G}}$ e ${\cal{H}}$ têm o mesmo número de componentes conexas.

Exercício.

Como aplicação do resultado anterior, os grafos seguintes não são isomorfos:

$\xymatrix{ & \bullet \ar@{-}[r]\ar@{-}[rdd] & \bullet \ar@{-}[rd] &\\ \bullet... ...-}[ru]\ar@{-}[rd] & & & \bullet\ar@{-}[ld]\\ & \bullet\ar@{-}[r] & \bullet & }$	$\xymatrix{ & \bullet \ar@{-}[r]\ar@{-}[dd] & \bullet \ar@{-}[rd] &\\ \bullet\... ...-}[ru]\ar@{-}[rd] & & & \bullet\ar@{-}[ld]\\ & \bullet\ar@{-}[r] & \bullet & }$
${\cal{G}}$	${\cal{H}}$

De facto, ${\cal{H}}$ contém um ciclo o que não sucede com ${\cal{G}}$.

No resultado seguinte, faz-se uso da noção de matriz de adjacência definida atrás para se estudar não só a alcançabilidade mas também o comprimento dos caminhos possíveis entre dois vértices.

Proposição 5.5   Seja $A$ a matriz de adjacência do grafo ${\cal{G}}$, para uma ordenação fixa previamente dos vértices. A entrada $A_{[u,v]}^r$ indica o número de caminhos de comprimento $r$.

Um grafo simples diz-se acÃclico se não tiver ciclos.

Uma árvore⁹ é um grafo acíclico conexo.

Um grafo acíclico chama-se floresta¹⁰. Logo, as componentes conexas de uma floresta são árvores.

Lema 5.6   Numa árvore com pelo menos uma aresta existem pelo menos dois vértices com grau 1.

Seja $N$ o diâmetro do grafo e seja $\gamma=v_0v_1v_2\cdots v_N$ uma geodésica cujo comprimento é $N$, e suponhamos que $v_0$ tem grau maior que 1. Então $v_0$ é vizinho não só de $v_1$ mas também de outro vértice $w$. Se $w$ é vértice de $\gamma$ então $\gamma$ teria um ciclo. Se $w$ não é vértice de $\gamma$ então $\gamma'=wv_0\circ\gamma$ seria um caminho elementar de comprimento $N+1$, o que contraria a noção de diâmetro. O mesmo raciocícnio se aplica a $v_N$.

Teorema 5.7   Para ${\cal{G}}$ um grafo $(p,q)$, as afirmações seguintes são equivalentes:

1. ${\cal{G}}$ é uma árvore;
2. Todos os vértices de $G$ são ligados por um único caminho elementar;
3. $G$ é conexo e $p=q+1$;
4. $G$ é acíclico e $p=q+1$.

$(1) \Leftrightarrow (2)$. Se ${\cal{G}}$ é uma árvore, então é um grafo acíclo conexo. Existe um caminho $v_i - v_j$, e esse caminho contém um caminho elementar. A concatenação de dois caminhos elementares distintos daria origem a um ciclo, o que mostra a unicidade. Reciprocamente, a existência de um caminho elementar garante a conexidade do grafo. A unicidade impede a existência de ciclos (verifique a razão).

$(1) \Rightarrow (3)$. A conexidade é imediata. Considere a propriedade $P(n):$ uma árvore ${\cal{G}}$ com $n$ vértices tem $n-1$ arestas, onde $n\ge 2$. $P(2)$ é válida. Mostre-se que $P(n)$ é suficiente para $P(n+1)$. Seja ${\cal{G}}$ uma árvore com $n+1$ vértices, e seja $v_{n+1}$ um vértice escolhido de tal forma que $deg(v_{n+1})=1$. Seja ainda ${\cal{G}}'={\cal{G}}-v_{n+1}$. Temos que ${\cal{G}}'$ tem $n$ vértices, e que é uma árvore (verifique!), e portanto tem $n-1$ arestas. Logo ${\cal{G}}$ tem $n$ arestas.

$(1)\Rightarrow (4)$ é análogo.

$(4)\Rightarrow (3)$. Se ${\cal{G}}$ é acíclico, então é uma floretsa com $k$ componetes conexas ${\cal{G}}_1,{\cal{G}}_2,\dots,{\cal{G}}_k$ que são árvores. Logo, aplicando $(1) \Rightarrow (3)$ a cada uma destas componentes, obtemos $p-k$ arestas em ${\cal{G}}$, pelo que, e sabendo que ${\cal{G}}$ tem $q$ arestas e $p-1=q$, se conclui que $k=1$, ou seja ${\cal{G}}$ é conexo.

$(4)\Rightarrow (2)$. Suponha que (4) é válida, mas que (2) é falsa. Ou seja, ou que existem dois caminhos elemenatares entre dois vértices, ou que não existe caminho elementar algum. O primeiro caso implica a existência de um ciclo, o segundo a não conexidade do grafo.

Finalmente, dizemos que uma aresta de ${\cal{G}}$ é uma ponte se a eliminação dessa aresta aumenta o número de componentes do grafo. â imediato verificar-se que todas as arestas de uma árvore são pontes. De facto, se ${\cal{G}}$ é uma árvore e $v,w$ são vértices tais que $\{v,w\}$ não é ponte, então existe $\gamma$ caminho $v-w$ que não contenha a aresta $\{v,w\}$. Ora a inclusão da aresta $\{v,w\}$ cria um caminho fechado, e portanto a existência de um ciclo.