Otimização Combinatória | Dicionário | Índice remissivo

Apêndice E
Grafos não-dirigidos

Muitos problemas de otimização combinatória são formuladas sobre grafos. Este apêndice faz uma rápida revisão dos conceitos e da terminologia da teoria dos grafos não-dirigidos. Um grafo não-dirigido é um tipo especial de grafo dirigido. Assim, poderíamos nos contentar com o resumo sobre grafos dirigidos que faremos no apêndice F. Mas é mais prático tratar dos grafos não-dirigidos em separado.

E.1 Grafos e suas arestas

Um grafo não-dirigido (= undirected graph) é um par $(V,E)$ de conjuntos em que $V$ é um conjunto finito não vazio e $E$ é um conjunto de pares não-ordenados de elementos de $V$. Os elementos de $V$ são chamados nós e os elementos de $E$ são chamados arestas (= edges).  [As letras $V$ e $E$ são as iniciais de vertex e edge, respectivamente. (Quem sabe deveríamos escrever $N$ e $A$ em lugar de $V$ e $E$.) A palavra vértice será aplicada apenas a vértices de poliedros.]  Se $E$ é o conjunto de todos os pares não-ordenados de elementos de $V$, dizemos que o grafo $(V,E)$ é completo.

Uma aresta $\{v,w\}$ pode ser denotada simplesmente por $vw$ ou por $wv$. Os nós $v$ e $w$ são as pontas da aresta. Dizemos que uma tal aresta incide em $v$ e em $w$. Dizemos também que a aresta $vw$ liga $v$ e $w$. (É claro que não há arestas paralelas, ou seja, duas arestas distintas que ligam o mesmo par de nós.) Dizemos também que os nós $v$ e $w$ são vizinhos ou adjacentes. O grau (= degree) de um nó $v$ é o número de arestas que têm ponta $v$.

Se dermos um nome — como $G$, por exemplo — a um grafo, o conjunto de nós do grafo será denotado por $V(G)$ e o conjunto de arestas por $E(G)$. O número de nós de um grafo é denotado por $n$ e o número de arestas por $m$. Portanto, se $G$ é o grafo em discussão então $n:=|V(G)|$ e $m:=|E(G)|$.  É claro que $m\le \frac{1}{2}n(n-1)<\frac{1}{2}{n}^2$.

Um subgrafo de um grafo $G$ é qualquer grafo $G^{\prime }$ tal que $V(G^{\prime })\subseteq V(G)$ e $E(G^{\prime })\subseteq E(G)$. Se $V(G^{\prime })=V(G)$, dizemos que $G^{\prime }$ é um subgrafo gerador (= spanning subgraph) de $G$. Dado um subconjunto $V^{\prime }$ de $V(G)$, se $E^{\prime }$ é o conjunto de todas as arestas de $G$ que têm ambas as pontas em $V^{\prime }$, dizemos que o subgrafo $(V^{\prime },E^{\prime })$ é induzido por $V^{\prime }$. Esse grafo é denotado por $G[V^{\prime }]$. Dado um subconjunto $E^{\prime }$ de $E(G)$, se $V^{\prime }$ é o conjunto de todas as pontas de arestas de $E^{\prime }$, dizemos que o subgrafo $(V^{\prime },E^{\prime })$ é induzido por $E^{\prime }$.

Para qualquer nó $v$ de $G$, denotamos por $G-v$ o subgrafo induzido por $V(G)\setminus \{v\}$. Para qualquer aresta $e$, denotamos por $G-e$ o subgrafo que tem conjunto de nós $V(G)$ e conjunto de arestas $E(G)\setminus \{e\}$.

Para qualquer par $(v,w)$ de nós, denotamos por $G+vw$ o grafo que tem conjunto de nós $V(G)$ e conjunto de arestas $E(G)\cup \{vw\}$.

Um grafo $G$ é bipartido se existe uma bipartição, digamos $\{P,Q\}$, de $V(G)$ tal que toda aresta tem uma ponta em $P$ e outra em $Q$.  [A expressão $P$ é uma das partições está errada; diga $P$ é um dos blocos da partição.]  Se todo par $pq$ com $p\in P$ e $q\in Q$ é uma aresta, dizemos que o grafo é bipartido completo.

E.2 Caminhos e ciclos

Um caminho (= path) num grafo não-dirigido é qualquer sequência alternante $(v_0,e_1,v_1,e_2,\dots ,e_p,v_p)$ de nós e arestas tal que, para cada $k$, o nó $v_{k-1}$ é uma das pontas da aresta $e_k$ e $v_k$ é a outra ponta. O nó $v_0$ é a origem do caminho e $v_p$ é o término. Dizemos que o caminho vai de $v_0$ a $v_p$. O comprimento do caminho é $p$, ou seja, o número de termos do caminho que são arestas. O conjunto de nós de um caminho $P$ é denotado por $V(P)$ e o conjunto de arestas por $E(P)$.

Um caminho $P^{\prime }$ é subcaminho de um caminho $P$ se pode ser obtido pela remoção de termos de $P$. Por exemplo, $(u,a,v,b,w,e,z)$ é um subcaminho de $(u,a,v,b,w,c,x,d,v,b,w,e,z)$. Um caminho $P^{\prime }$ é segmento de um caminho $P$ se pode ser obtido pela remoção de termos do início e/ou do fim de $P$. Por exemplo, $(x,d,v,b,w,e,z)$ é um segmento de $(u,a,v,b,w,c,x,d,v,b,w,e,z)$.

Um caminho $(v_0,e_1,v_1,e_2,\dots ,e_p,v_p)$ é quase-simples (= edge-simple) se não tem arestas repetidas, isto é, se as arestas $e_1,e_2,\dots ,e_p$ são diferentes entre si. (Nada impede, entretanto, que o caminho tenha nós repetidos.)  Se $P$ é um caminho quase-simples então o comprimento de $P$ é igual a $|E(P)|$.

Um caminho é simples se não tem nós repetidos. (É claro que todo caminho simples é, em particular, quase-simples.)  Se $P$ é um caminho com origem $r$ e término $s$ então algum subcaminho de $P$ é um caminho simples de $r$ a $s$.

Todo caminho com uma dada origem $r$ e um dado término $s$ tem um subcaminho simples com origem $r$ e término $s$.

Dados caminhos $(v_0,e_1,\dots ,v_p)$ e $(w_0,f_1,\dots ,w_q)$, se o término do primeiro é igual à origem do segundo, então os dois caminhos podem ser concatenados. O resultado da concatenação é o caminho $(v_0,e_1,\dots ,v_p,f_1,\dots ,w_q)$. A concatenação de dois caminhos $P$ e $Q$ é denotada por $P\cdot Q$.

A distância de $r$ a $s$ é o mínimo dos comprimentos de todos os caminhos de $r$ a $s$.

Conexão. Um grafo não-dirigido é conexo se, para cada par $(r,s)$ de seus nós, existe um caminho de $r$ a $s$ (e portanto também um caminho de $s$ a $r$). Um grafo é desconexo se não for conexo.

Uma componente conexa de um grafo não-dirigido $G$ é um subgrafo não-dirigido conexo maximal de $G$.

Ciclos. Um ciclo (= cycle) é um caminho quase-simples $(v_0,e_1,v_1,\dots ,e_p,v_p)$ em que $v_p=v_0$ e $p\ge 3$.

Um ciclo é simples se não tem nós repetidos exceto o último (que coincide com o primeiro). Ciclos simples em grafos não-dirigidos também são conhecidos como circuitos (= circuits).  Todo ciclo tem um segmento que é um circuito. Em particular, todo ciclo de comprimento ímpar tem um segmento que é um circuito de comprimento ímpar.

E.3 Florestas e árvores

Uma floresta (= forest) é um grafo não-dirigido sem ciclos. Uma árvore (= tree) é uma floresta conexa. Uma folha de uma floresta é qualquer nó de grau $1$.

Para quaisquer dois nós $r$ e $s$ de uma árvore, existe um e um só caminho simples de $r$ a $s$. Para toda aresta $e$ de uma árvore $T$, o grafo não-dirigido $T-e$ é uma floresta com exatamente duas componentes conexas.

E.4 Cortes

Dado um grafo não-dirigido $(V,E)$ e um subconjunto $R$ de $V$, denotamos por $\bar{R}$ o conjunto $V\setminus R$. O conjunto de todas as arestas que têm uma ponta em $R$ e outra em $\bar{R}$ é denotado por $$\partial (R)\text{.}$$ É claro que $\partial (R)=\partial (\bar{R})$. É claro também que $\partial (\mathrm{\varnothing })=\partial (V)=\mathrm{\varnothing }$.

Se $v$ é um nó, usamos a abreviatura $\partial (v)$ para $\partial (\{v\})$. Um nó $v$ é isolado se $\partial (v)=\mathrm{\varnothing }$.  O número $|\partial (v)|$ é o grau de $v$. É claro que $|\partial (v)|\le n-1$. É claro também que $$\sum _{v\in V(G)}|\partial (v)|=m/2\text{.}$$

Um corte (= cut) em um grafo não-dirigido $(V,E)$ é o conjunto de todos os arestas que têm uma ponta em um conjunto de nós e a outra ponta fora do conjunto. Em outras palavras, um corte é qualquer conjunto da forma $\partial (R)$, com $R\subseteq V$.  O conjunto $R$ é uma margem do corte. Um corte é trivial se sua margem é $\mathrm{\varnothing }$ ou $V$. (Note que um grafo desconexo tem cortes vazios que não são triviais.)

E.5 Álgebra linear

A matriz de adjacências de um grafo não-dirigido tem linhas e colunas indexadas pelos nós. A componente da matriz na posição $(v,w)$ vale $1$ se $vw$ é uma aresta e vale $0$ em caso contrário. É claro que a matriz é simétrica.

A matriz de incidências do gafo $G$ tem linhas indexadas por $V(G)$ e colunas indexadas por $E(G)$. A coluna que corresponde a um aresta $vw$ tem um $1$ nas posições $v$ e $w$ e tem $0$ nas demais posições. Portanto, a linha $v$ da matriz tem um $1$ nas colunas correspondentes às arestas que têm ponta $v$ e tem $0$ nas demais colunas.

Esse lema pode ser informalmente resumido assim: num grafo bipartido, um conjunto de arestas linearmente independentes é o mesmo que uma floresta.  Em grafos não-dirigidos arbitrários, um lema análogo vale se as combinações lineares forem feitas em $\mathit{GF}(2)$, ou seja, se os coeficientes forem binários e a aritmética for binária ($0+0=0$, $0+1=1+0=1$, $1+1=1$, $0\cdot 0=0\cdot 1=0$, $1\cdot 0=0$ e $1\cdot 1=1$).