CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Grafos

Definições fundamentais

Definição: Um grafo não-orientado é um par $G=(V,E)$, onde $V$ é um conjunto não vazio de elementos, chamados vértices e $E$ é um conjunto de pares de elementos de $V$, chamados de arestas.

Exemplos:

• $V=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\}$
• $E=\{(v_{1},v_{3}),(v_{2},v_{4}),(v_{1},v_{5}),(v_{2},v_{6}),(v_{4},v_{5}),(v_{3},v_{3}),(v_{4},v_{2})\}$

Definição: Todo grafo $G=(V,E)$ admite uma representação no plano (um desenho), orientada como segue:

• Para cada vértice $v\in V$, adicionamos um ponto ao plano.
• Para cada aresta $e=(u,v)\in E$, adicionamos um segmento entre os pontos correspondentes a $u$ e $v$ no plano.

Definição: Dada uma aresta $e=(u,v)\in E$, podemos dizer que:

• $u$ e $v$ são as extremidades ou extremos de $e$.
• $u$ e $v$ são adjacentes, vizinhos ou "se veem" através de $e$.
• $e$ é incidente em $u$ e em $v$.

Definição: Duas arestas $e_{1}$ e $e_{2}$ são chamadas de arestas múltiplas ou paralelas se ambas possuem as mesmas extremidades. Além disso, uma aresta cujas extremidades são iguais, é chamada de laço.

Se $G=(V,E)$ é um grafo sem arestas múltiplas ou laços, então $G$ é dito um grafo simples.

Vizinhança, grau e distância

Definição: Seja $v\in V(G)$ um vértice de $G$. Definimos um conjunto de vizinhos de $G$ como a vizinhança de $v$, denotada por $N(v)$.

Definição: Dado um vértice $v\in V(G)$, definimos o grau de $v$ como o número de arestas que incidem a $v$ em $G$. Além disso, cada aresta múltipla incide exatamente uma vez em $v$ e cada laço incide exatamente duas vezes em sua extremidade. Denotamos o grau de $v$ em $G$ por $d(v)$.

Definição: Dados dois vértices $u$ e $v$ em $G$, a distância entre $u$ e $v$ em $G$ é o comprimento mínimo de qualquer caminho entre $u$ e $v$ em $G$ ou o comprimento do caminho mínimo entre $u$ e $v$ em $G$. O conceito formal de caminho será apresentado em outra seção, mas o leitor pode interpretar a distância como o número mínimo de arestas que precisam ser percorridas para ir de $u$ até $v$ em $G$.

Além disso, denotamos a distância entre $u$ e $v$ por $dist(u,v)$.

Definição: Dado um grafo $G=(V,E)$ e uma sequência $\Pi =<v_{1},v_{2},...,v_{n}>$ dos vértices de $G$, definimos a sequência de graus de $G$ sobre $\Pi$ como a ordem $<d(v_{1}),d(v_{2}),...,d(v_{n})$. Vale ainda ressaltar as seguintes observações:

• A distância de um vértice a ele próprio é 0, isto é, $dist(v,v)=0$, para todo vértice $v\in V(G)$. Além disso, se não existem caminhos entre $u$ e $v$ em $G$, então $dist(u,v)=\infty$.
• O grau mínimo e o grau máximo de um grafo $G$ são os valores mínimo e máximo de graus dentre os graus de vértices em $G$, e denotamos, respectivamente, por $\delta (G)$ e $\Delta (G)$.