Conceitos iniciais

Definição 2.1   Um digrafo ${\cal{D}}$ é um par ordenado $({\cal{V}},{\cal{A}})$, onde ${\cal{V}}$ é um conjunto não vazio finito e ${\cal{A}}$ é um subconjunto de $\left\{(U,V):U,V\in {\cal{V}}\right\}$.

Os elementos de ${\cal{V}}$ chamam-se vértices de ${\cal{D}}$ e os elementos de ${\cal{A}}$ as arestas de ${\cal{D}}$.

Note-se que acima não está contemplado o caso dos multigrafos. Esta classe de objectos pode ser definida indexando cada aresta a um conjunto de índices. Ou seja, para $I\ne \emptyset$ conjunto de índices, o conjunto das arestas é um subconjunto do produto cartesiano $V\times V \times I$.

Iremos autorizar a existência de lacetes, ou loops, isto é, $(U,U)\in {\cal{A}}$, mas não iremos considerar multigrafos.

Para se representar graficamente um grafo (com um número finito de vértices e de arestas), tomamos pontos do plano, correspondendo ao vértices do digrafo, $V_1,\dots V_n$, e desenhamos um arco (dirigido) entre $V_i$ e $V_j$ se $(V_i,V_j)\in {\cal{A}}$.

Dada uma aresta $(U,V)\in {\cal{A}}$, o vértice $U$ diz-se extremidade inicial e o vértice $V$ extremidade final.

Dizemos que os vértices $U$ e $V$ são adjacentes, $U \leftrightarrow V$, se $(U,V)\in {\cal{A}}$ ou $(V,U) \in {\cal{A}}$. Em qualquer um destes casos, diz-se que o vértice $U$ é vizinho do vértice $V$. Esta aresta diz-se incidente em cada um desses vértices. O conjunto dos vizinhos de $U$ denota-se por $\Gamma(U)$. Duas arestas $\ell_1,\ell_2$ são adjacentes se existir $X\in {\cal{V}}$ tal que $\ell_1,\ell_2$ incidem em $X$.

Os antecessores [resp. sucessores] de um vértice $V$ são os elementos do conjunto $\Gamma^-(V)=\left\{U\in {\cal{V}}:(U,V)\in {\cal{A}}\right\}$ [resp. $\Gamma^+(V)=\left\{U\in {\cal{V}}:(V,U)\in {\cal{A}}\right\}$].

O grau (ou valÃ^ancia) de um vértice $V$, denotado por $deg(V)$ ou por $\partial(V)$, é o número de arestas próprias (ou seja, que não sejam lacetes) incidentes em $V$ adicionado ao dobro do número¹ de laços em $V$ . O grau interior de $V$, $\partial^- (V)$, é o número de arestas da forma $(*,V)$, e o grau exterior de $V$, $\partial^+(V)$, é o número de arestas da forma $(V,*)$. Ou seja, $\partial^-(V)=\char93 \Gamma^-(V)$ e $\partial^+(V)=\char93 \Gamma^+(V)$.

A título de exemplo, considere a representação gráfica do digrafo seguinte

$$\xymatrix{ U \ar@/_/[r] & \ar@/_/[l]V\ar@(ul,ur)\ar[r] & W}$$

Temos, então, ${\cal{V}}=\left\{U,V,W\right\},{\cal{A}}=\left\{(U,V),(V,U),(V,V),(V,W)\right\}$. Neste digrafo, $\partial^-(U)=\partial^+(U)=\partial^-(W)=1,\partial^+(W)=0,\partial^+(V)=\partial^-(V)=2$.

Um digrafo $({\cal{V}},{\cal{A}})$ é

1. um $n$-digrafo se $\char93 {\cal{V}}=n$
2. um $(p,q)$-digrafo se $\char93 {\cal{V}}=p,\char93 {\cal{A}}=q$
3. simples se $\forall_{V\in {\cal{V}}} (V,V)\notin {\cal{A}}$
4. reflexivo se $\forall_{ V\in {\cal{V}}} (V,V)\in {\cal{A}}$
5. completo se todas as possíveis arestas estão presentes (inclusivé os lacetes)
6. simétrico se $(U,V)\in {\cal{A}}\Rightarrow (V,U)\in {\cal{A}}$
7. transitivo se $(U,V)\in {\cal{A}},(V,W)\in {\cal{A}}\Rightarrow (U,W)\in {\cal{A}}$
8. de torneio se $\forall_{U,V\in {\cal{V}}}$ se tem $(U,V)\in {\cal{A}}$ xor $(V,U) \in {\cal{A}}$

Figura: Tente classificar cada um destes digrafos.

Note-se que, dado um digrafo simétrico, se $(U,V)\in {\cal{A}}$ então $\left\{(U,V),(V,U)\right\} \subseteq {\cal{A}}$. Podemos, portanto, identificar este par de arestas com $\left\{U,V\right\}$. Esta aresta é representada simplesmente por um segmento de recta que une os dois vértices em que incide.

Figura: Digrafo simétrico e correspondente grafo

Esta identificação leva-nos à definição de grafo não dirigido, ou simplesmente grafo.

Definição 2.2   Um grafo (não dirigido) $G$ é um par ordenado $({\cal{V}},{\cal{A}})$, onde ${\cal{V}}$ é um conjunto não vazio finito e ${\cal{A}}$ é um subconjunto de $\left\{\left\{U,V\right\}:U,V\in {\cal{V}}\right\}$.