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.

Grafos especiais

Definição: Um grafo simples é chamado de completo se existe uma aresta entre todos os pares de vértices. Denotamos o grafo completo com $n$ vértices por $K_{n}$.

Analogamente, o grafo $G$ com $m=0$ é um grafo vazio.

$K_{1}$ (possui apenas um vértice e nenhuma aresta) é um grafo simples e completo, uma vez que não quebra a propriedade.

Definição: Um grafo é chamado de regular ou k-regular se $d(v)=k$,  $\forall v\in V(G)$.

Obs.: Se $k=3$, dizemos que $G$ é cúbico.

Definição: Um grafo $G=(V,E)$ é chamado de bipartido se podemos particionar $V(G)$ em dois conjuntos $A$ e $B$ tal que toda aresta de $G$ possui uma extremidade em $A$ e a outra em $B$. Isso é equivalente ao problema de colorir vértices de um grafo com duas cores.

Definição: Um grafo $G$ é chamado multipartido ou k-partido, se podemos dividir o conjunto de vértices $V(G)$ em $k$ conjuntos disjuntos, tal que cada aresta possui extremidades em conjuntos distintos.

Definição: Um grafo $G$ é dito bipartido completo é um grafo bipartido com partes $A$ e $B$, tal que todo vértice de $A$ é adjacente a todo vértice de $B$. Além disso, denotamos o grafo bipartido completo, onde $|A|=k_{1}$ e $|B|=k_{2}$ por $K_{3,2}$. Analogamente, definimos o grafo multipartido completo, onde $G$  é particionado em conjuntos $A_{1},A_{2},...,A_{j}$, onde $|A_{1}|=k_{1},|A_{2}|=k_{2},...,|A_{j}|=k_{j}$. Definimos tal grafo como $K_{k_{1}},K_{k_{2}},...,K_{k_{j}}$.

Definição: Seja $G=(V,E)$ um grafo. O grafo complementar de G, denotado por G̅, é o grafo que possui o mesmo conjunto de vértices $V$, mas no qual dois vértices distintos estão ligados por uma aresta em G̅ se, e somente se, não estiverem ligados por uma aresta em $G$.

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)$.

Teoremas relacionados

Teorema 1: Para todo grafo $G=(V,E)$, sendo $|E|=m$ temos que: $\Sigma _{v\in V(G)}d(v)=2m$.

Prova: Para cada aresta $e=uv$ incidente a $v$ em $G$, temos que $e$ é a contada duas vezes no somatório: uma vez em $d(v)$ e outra vez em $d(u)$. Além disso, temos que se $e$ é um laço, então a mesma é contada duplamente em $d(v)$. Logo, todas as arestas são contadas exatamente duas vezes no somatório e o resultado vale.

---

Corolário: Para todo grafo $G=(V,E)$, temos que o número de vértices de grau ímpar de $G$ é par.

Prova: Sejam $V_{I}$ e $V_{P}$ os conjuntos de vértices de $G$ com graus ímpar e par, respectivamente. Podemos ver que: $V_{I}\cup V_{P}=V(G)$ e, além disso, $V_{I}\cap V_{P}=\varnothing$, isto é, $V_{I}$ e $V_{P}$ formam uma partição de $V(G)$. Assim, podemos escrever:

$\Sigma _{v\in V(G)}d(v)=\Sigma _{v\in V_{I}}d(v)+\Sigma _{v\in V_{P}}d(v)$

Sabemos, do teorema citado, que $\Sigma _{v\in V(G)}d(v)=2m$, isto é, é par. Além disso, pela equação acima, é possível deduzir que, como $\Sigma _{v\in V_{P}}d(v)$ é par, temos que $\Sigma _{v\in V_{I}}d(v)$ deve ser par, o que implica que o $|V_{I}|$ é par.