Introdução à teoria de grafos: Arestas, vértices, caminhos e circuitos

Grafos, vértices e arestas

Um grafo é determinado por um conjunto $$A$$​ de arestas cujos extremos pertencem a um conjunto $$V$$​ de vértices. Grafos são utilizados para simplificar esquemas, como mapas de metro ou de cidades.

A figura abaixo representa um grafo, em que $$\text{A}$$​, $$\text{B}$$​ e $$\text{C}$$​ são os seus vértices e $$\text{AB}$$​ e $$\text{BC}$$​ as suas arestas.

Desta forma, $$V=\{\text{A,\ B,\ C}\}$$ e $$A=\{\text{AB,\ BC} \}$$. As arestas $$\text{AB}$$​ e $$\text{BA}$$ têm o mesmo significado.

Caso se queira especificar apenas um sentido, a aresta é desenhada com uma seta e passa a ter-se o arco $$\text{(A,B)}$$, sendo $$\text{(A,B)}\not=\text{(B,A)}$$. Os grafos com arcos chamam-se digrafos, grafos orientados ou grafos dirigidos.

No grafo orientado abaixo, tens que $$V=\{\text{A,\ B,\ C}\}$$ e $$A=\{\text{(A,B),\ (B,C),\ (C,A)} \}$$.

​

Uma aresta que ligue um vértice a ele próprio chama-se laço ou lacete. Já um vértice sem ligação a nenhum outro chama-se vértice isolado. Se dois vértices estiverem ligados por mais do que uma aresta, estas denominam-se arestas paralelas.

Exemplo

No grafo abaixo, $$\text{CC}$$​ é um lacete, $$\text{DF}$$​ e $$\text{FD}$$​ são arestas paralelas e $$\text{G}$$​ é um vértice isolado.

Vértices e arestas adjacentes

Vértices são adjacentes se estiverem unidos por uma aresta. Por outro lado, duas arestas são adjacentes se tiverem um vértice em comum. Uma aresta que une dois vértices é incidente em cada um deles.

Exemplo

Na imagem acima, $$\text{A}$$​ e $$\text{B}$$​ são vértices adjacentes, mas $$\text{B}$$​ e $$\text{D}$$​ já não são. Da mesma forma, $$\text{CD}$$​ e $$\text{DE}$$​ são arestas adjacentes, mas $$\text{AB}$$​ e $$\text{CD}$$​ já não o são. $$\text{BC}$$​ é uma aresta incidente nos vértices $$\text{B}$$​ e $$\text{C}$$​.

Caminhos e circuitos

Dados dois vértices $$A$$ e $$B$$ de um grafo, um caminho de $$A$$​ para $$B$$ é uma sequência alternada de vértices e arestas adjacentes do grafo, que começa em $$A$$ e acaba em $$B$$.

Um circuito é um caminho que começa e acaba no mesmo vértice, pelo que o comprimento de um circuito é o número de arestas que o constitui.

Exemplo

Atentando no grafo abaixo, podes ir de $$\text{A}$$​ para $$\text{E}$$ pelo caminho $$\text{A}\ a_3\ \text{B}\ a_5\ \text{D}\ a_5\ \text{B}\ a_4\ \text{C}\ a_6\ \text{E}$$. Um circuito de comprimento $$5$$​ é $$\text{A}\ a_1\ \text{C}\ a_6\ \text{E}\ a_7\ \text{D}\ a_5\ \text{B}\ a_3\ \text{A}$$.

Um grafo sem arestas paralelas nem lacetes é um grafo simples. Nestes grafos, os caminhos ou circuitos podem ser indicados utilizando as letras dos vértices pela ordem que forem utilizados.

Exemplo

Neste grafo, um caminho de $$\text{H}$$​ para $$\text{J}$$​ pode ser $$\text{HKJ}$$​ e um circuito com início em $$\text{I}$$​ pode ser $$\text{IKJHKI}$$.

Subgrafo, grafo conexo e grafo bipartido

Um grafo 1 é chamado subgrafo do grafo 2 se todos os vértices (respetivamente, arestas) de 1 pertencerem ao conjunto de vértices (respetivamente, arestas) de 2.

Exemplo

O grafo 2 abaixo é subgrafo do grafo 1.

Grafo 1	Grafo 2

Um grafo é conexo quando qualquer vértice está ligado a outro por uma aresta ou sequência de arestas. Um grafo diz-se desconexo se não é conexo.

Exemplo

Vês abaixo que os grafo 3 é desconexo, mas que os grafos 1 e 2 são conexos.

Grafo 1	Grafo 2	Grafo 3

Um grafo $$G$$ (com $$2$$ ou mais vértices) é bipartido quando o podemos representar como união de dois subgrafos distintos $$G_1$$ e $$G_2$$, de forma a que, quando considerados individualmente, são ambos grafos de vértices isolados.

Por outras palavras, um grafo é bipartido se pudermos escrever o seu conjunto de vértices $$V$$ como união de dois conjuntos $$V_1$$​ e $$V_2$$ tais que todas as arestas de $$G$$ ligam vértices de $$V_1$$ a vértices de $$V_2$$.

Exemplo

No grafo abaixo, verificas que, com $$V=\{\text{A,\ B,\ C,\ E,\ F,\ G}\}$$, o grafo torna-se bipartido escolhendo $$V_1=\{\text{A,\ C,\ E,\ F,\ G}\}$$ e $$V_2=\{\text{B,\ D}\}$$.