Grafos: definições, nomenclaturas e notações

Neste texto, irei dar algumas noções elementares sobre grafos baseadas no livro Graph Theory [1].

Um grafo $G$ é um par ordenado $G = (V,E)$, onde $V$ é um conjunto qualquer e $E$ é uma coleção de pares de elementos de $V$, i.e., $E = \{\; \{x,y\} \; | \; x,y \in V, x\neq y\}$. Os elementos de $V$ são chamados de vértices do grafo e os elementos de $E$ são chamados de arestas. Uma aresta $e$, formalmente, é um par $e = \{x,y\}$, onde $x,y$ são vértices do grafo, mas por comodidade iremos representar a aresta $e$ apenas por $xy$, de modo que não haverá confusão ao identificarmos $e=xy=yx$.

Segundo a nossa definição de grafo, não há possibilidade de duas arestas distintas conectarem o mesmo par de vértice. Também não há chance alguma de existir uma aresta que conecte um vértice $x$ a ele mesmo (arestas deste tipo recebem o nome de laços ou loops). Assim, segundo a definição de alguns livros, o nosso grafo é um grafo simples. Mas como este é principal tipo de grafo que nos interessa por enquanto, não iremos nos preocupar em dizer que os nossos grafos são simples. Existem outros tipos de grafos tão interessante quanto os simples: grafos orientados, múltiplos, com fluxos, labelados, entre outros (ver [1]). Outra coisa, não esteremos, por enquanto, interessados em grafo cujo o conjunto dos vértices é infinito. Logo, assumiremos desde já que $|V| < \infty$. Consequentemente, o conjunto das arestas é finito também.

É muito comum e conveniente representar um grafo $G$ por um desenho sobre um plano onde os vértices são representados por pontos no plano e arestas que conectam dois vértices $x$ e $y$ são representados por linhas (retas ou curvilíneas) que contêm os pontos que representam os vértices $x$ e $y$ como extremidades. Claramente, um grafo pode ser desenhado de inúmeras maneiras distintas, logo não devemos nos apegar ao desenho do grafo, mas utilizá-lo para visualizar rapidamente algumas afirmações. Muitas vezes iremos verificar algo através de um desenho, mas isso deve ser feito de modo que fique claro que esta verificação é independente da maneira que desenhamos.

Dado um grafo $G=(V,E)$, dois vértices $x,y,\in V$ são ditos adjacentes se $xy$ é uma aresta de $G$. Uma aresta $e \in E$ é dita incidente no vértice $x$ se $x$ pertence a $e$ (lembre-se que uma aresta é um conjunto de dois vértices) e o vértice $x$, nesse caso, também é dito incidente em $e$.

Denotamos por $N(x)$ o conjunto de todos os vértices $y$ adjacentes a $v$, i.e., $N(x) = \{y\in V\;:\; xy\in E\}$. O grau de $v$ (em $G$) é denotado por $d(v)$ e dado por $d(v):=|N(v)|$. O grau mínimo do grafo $G$ (denotamos por $\delta(G)$) é dado por $\delta(G) = \min_{v\in V} d(v)$; e o grau máximo de $G$ (denotamos por $\Delta(G)$) é dado por $\Delta(G) = \max_{v\in V} d(V)$. Outro parâmetro relevante é o grau médio de $G$ (denotamos por $d(G)$) dado por $d(G) = \frac{1}{|V|}\sum_{v\in V} d(v)$.

Podemos definir uma noção de subgrafos em um grafo $G$. Um grafo $G'=(V',E')$ é um subgrafo de $G=(V,E)$ (denotamos por $G' \subseteq G$), se tivermos que $V'\subseteq V$ e que $E'\subseteq E$. Dizemos que $G'$ é um subgrafo induzido de $G$ se tivermos que $V'\subseteq V$ e que $E'$ é o conjunto das arestas $e=xy\in E$ tais que $x$ e $y$ são vértices de $V'$.

Assim como toda estrutura matemática, existe em grafos uma noção de isomorfismo, i.e., uma maneira de verificar que dois grafos $G_1$ e $G_2$ são, num certo senso, idênticos. Dizemos que os grafos $G_1=(V_1,E_1)$ e $G_2 = (V_2,E_2)$ são isomorfos (e denotamos por $G_1 \approx G_2$) quando existe uma bijeção $\phi : V_1 \rightarrow V_2$ tal que dois vértices $x,y \in V_1$ são adjacentes se, e somente se, $\phi(x)$ e $\phi(y)$ forem adjacentes em $G_2$. Em outras palavras, a bijeção $\phi$ preserva adjacências.

Alguns grafos são tão comuns que recebem uma notação própria para representá-los. O primeiro destes grafos é o que chamamos de grafo $n$-completo (esse $n$ é um número natural). Um grafo é completo quando todo par de vértices é conectado. Denotamos por $K_n$ ($n$-completo) um grafo que possui $n$ vértices e é completo. O leitor poderá verificar sem muita dificuldade que o número de arestas de um $K_n$ é $\binom{n}{2}$. Quando dizemos que um grafo $G$ é um $K_n$, queremos dizer que $G$ é $n$-completo. Um subgrafo que é $n$-completo é chamado de $n$-clique do grafo que o contém. Abaixo, temos um $K_6$, como um exemplo de grafo completo.

Outra classe de grafos importantes é a classe dos caminhos. Um caminho de tamanho $n$ (denotamos por $P_n$) é um grafo que contém $n$ vértices $v_1,\ldots,v_n$ e $n-1$ arestas $v_1v_2,v_2v_3,\ldots,v_{n-1}v_n$. Muitas vezes iremos nos referir ao um subgrafo como caminho, quando este de fato for um caminho. Abaixo, um exemplo de $P_6$.

Temos também a classe dos ciclos. Um ciclo de tamanho $n$ (denotamos por $C_n$) é um grafo que contém $n$ vértices $v_1,\ldots,v_n$ e $n$ arestas $v_1v_2,v_2v_3,\ldots,v_{n-1}v_n,v_nv_1$. Muitas vezes iremos nos referir ao um subgrafo como ciclo, quando este de fato for um ciclo. Alguns autores brasileiros reservam a palavra "circuito" para o que chamamos de ciclo, mas que nos textos americanos são chamados "cycles". Mas futuramente pretendo falar sobre outra classe de grafos que recebe o nome "circuito" (em inglês, "circuit"). Abaixo, temos um $C_6$.

Para que este post não fique só em definições, vamos provar uma pequena proposição muito útil (e que já usamos no primeiro post).

Proposição. Para todo grafo $G=(V,E)$, vale que $$\sum_{v\in V} d(v) = 2|E|.$$

Demonstração.  Façamos uma contagem dupla dos pares $(v,e)\in V\times E$  tais que $v$ é incidente em $e$. Um vértice $v$ qualquer é incidente com $d(v)$ arestas, logo o número de pares $(v,e)$ com $e$ incidente em $v$ é $$\sum_{v\in V} d(v).$$ Por outro lado, uma aresta $e$ qualquer é incidente com dois vértices, logo o número de pares $(v,e)$ com $v$ incidente em $e$ é $2|E|$. Isto acaba a demonstração.

$\square$

Referências:

[1] Diestel, Graph Theory. 3nd edition.