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.

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Introdução à teoria de grafos: Arestas, vértices, caminhos e circuitos

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

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Introdução à teoria de grafos: Arestas, vértices, caminhos e circuitos

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.