GRAFOS

Grafos

Modelos de

GRAFO - esquema constituído por conjuntos finitos de pontos e por linhas que ligam os pontos.

A = {AB, BA, BD, DD, BE, CD, CE}

Arestas ou arcos - linhas

V = { A, B, C, D, E, F}

Vértices ou nós - pontos

Grafos

Vértice isolado - não tem nenhuma ligação com outro vértice

Vértices adjacentes - unidos por uma aresta

Grafos

Lacetes - arestas que ligam um vértice com ele próprio

Arestas paralelas - ligam os mesmos dois vértices

Arestas adjacentes - têm um vértice em comum

Grafos

Grafos

Grau ou valência de um vérticeNúmero de arestas que começam, ou terminam, nesse vértice.

Grafos

Qual o grau de cada um dos vértices?

Grafos

Ex.

Comprimento - 7Ordem - 6

Ordem de um grafo - n.º de vértices que o constituiem

Comprimento de um grafo - n.º de arestas que o constituiem

Grafos

Grafo Conexo - qualquer vértice está ligado por uma aresta ou por uma sequência de arestas a qualquer um dos outros vértices

(Contrário - Multigrafo)

Grafo Completo - grafo simples em que quaiquer dois dos seus vértices são adjacentes

Grafo Simples - não têm arestas paralelas, nem lacetes

Grafo Regular - os vértices têm o mesmo grau

Grafos

Grafos

Trajeto ou Trilho - passeio sem repetição de arestas

Passeio - sequência de vértices em que cada dois vértices estão ligados por uma aresta, podendo haver repetição

Percursos

Grafos

Circuito ou Ciclo - caminho que começa e termina no mesmo vértice (o único que se pode repetir)

Caminho - trajeto em que os vértices são todos distintos

Percursos

Grafos