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.
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 $\conj{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 \leq \frac{1}{2}n(n-1) \lt \frac{1}{2}n^2$.
Um subgrafo de um grafo $G$ é qualquer grafo $G'$ tal que $V(G')\subseteq V(G)$ e $E(G')\subseteq E(G)$. Se $V(G')=V(G)$, dizemos que $G'$ é um subgrafo gerador (= spanning subgraph) de $G$. Dado um subconjunto $V'$ de $V(G)$, se $E'$ é o conjunto de todas as arestas de $G$ que têm ambas as pontas em $V'$, dizemos que o subgrafo $(V',E')$ é induzido por $V'$. Esse grafo é denotado por $G[V']$. Dado um subconjunto $E'$ de $E(G)$, se $V'$ é o conjunto de todas as pontas de arestas de $E'$, dizemos que o subgrafo $(V',E')$ é induzido por $E'$.
Para qualquer nó $v$ de $G$, denotamos por $G-v$ o subgrafo induzido por $V(G)\setm\conj{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)\setm\conj{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\conj{vw}$.
Um grafo $G$ é bipartido
se existe uma bipartição,
digamos $\conj{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.
Um caminho (= path) num grafo não-dirigido é qualquer sequência alternante $\seq{v_0,e_1, v_1,e_2,\ldots, 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'$ é 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'$ é 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 $\seq{v_0,e_1, v_1,e_2,\ldots, e_p,v_p}$ é quase-simples (= edge-simple) se não tem arestas repetidas, isto é, se as arestas $e_1, e_2,\ldots,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 $\seq{v_0,e_1,\ldots,v_p}$ e $\seq{w_0, f_1,\ldots, 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 $\seq{v_0,e_1,\ldots,v_p, f_1,\ldots, 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 $\seq{v_0,e_1,v_1,\ldots, e_p,v_p}$ em que $v_p=v_0$ e $p \geq 3$.
Lema E.1 (folclore) Se todos os nós de um grafo não-dirigido têm grau maior que $1$ então o grafo tem um ciclo. ■
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.
Lema E.2 (folclore) Um grafo não-dirigido é bipartido se e somente se não tem circuitos de comprimento ímpar. ■
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.
Lema E.3 Toda floresta com uma ou mais arestas tem pelo menos duas folhas. ■
Dado um grafo não-dirigido $(V,E)$ e um subconjunto $R$ de $V$, denotamos por $\compl{R}$ o conjunto $V\setm R$. O conjunto de todas as arestas que têm uma ponta em $R$ e outra em $\compl{R}$ é denotado por \[ \cut(R)\,\text{.} \] É claro que $\cut(R) = \cut(\compl{R})$. É claro também que $\cut(\emptyset) = \cut(V) = \emptyset$.
Se $v$ é um nó, usamos a abreviatura $\cut(v)$ para $\cut(\conj{v})$. Um nó $v$ é isolado se $\cut(v) = \emptyset$. O número $|\cut(v)|$ é o grau de $v$. É claro que $|\cut(v)| \leq n-1$. É claro também que \[\textstyle \sum_{v\in V(G)} |\cut(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 $\cut(R)$, com $R\subseteq V$. O conjunto $R$ é uma margem do corte. Um corte é trivial se sua margem é $\emptyset$ ou $V$. (Note que um grafo desconexo tem cortes vazios que não são triviais.)
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.
Exemplo E.1:
O grafo não-dirigido que tem nós $u \ v \ w \ z$ e arestas
$uw \ vw \ zu \ uz \ zw$
tem a seguinte matriz de incidências
(com $-$
representando $0$
):
Lema E.4 (circuitos e dependência linear) Seja $A$ a matriz de incidências de um grafo não-dirigido $(V,E)$. Se o conjunto das colunas de $A$ é linearmente dependente então $G$ tem um circuito. ■
Lema E.5 (circuitos e dependência linear em grafos bipartidos) Seja $A$ a matriz de incidências de um grafo não-dirigido bipartido $(V,E)$. Se $G$ tem um circuito então o conjunto das colunas de $A$ é linearmente dependente. ■
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$).