Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE183 - Algoritmos e Estruturas de Dados 2
Profs. Resp: Graça Pimentel e Maria Cristina

Teoria dos Grafos

Grafo G (V,E)

V é um conjunto finito não-vazio.
E é um conjunto de pares não ordenados de elementos distintos de V.

V = {1, 2, 3, 4, 5}
E = {(1, 2), (1, 4), (2, 3), (2, 5), (4, 3), (5, 1)}

Elementos de V são vértices de G, e os de E são as arestas de G.

Cada aresta e pertencente a E será denotada pelo par de vértices e = (v,w) que a forma. Os vértices v e w são os extremos da aresta e sendo denominados adjacentes. A aresta e é dita incidente a ambos os vértices v e w.

Duas arestas são adjacentes quando possuem um extremo comum.

Notação:

n = |V|
m = |E|
quando |V| = 1, G é trivial

Representação Geométrica

Os vértices correspondem a pontos distintos do plano, em posições arbitrárias, enquanto que a aresta (v,w) é associada a uma linha arbitrária unindo os pontos v e w.

Laço
Uma aresta do tipo e = (v,v)

Arestas Múltiplas
Ocorre quando se permite a existência de mais de uma aresta entre o mesmo par de vértices.

Multigrafo
É um grafo cujo conjunto de arestas contém laços e/ou arestas múltiplas.

Grau de um vértice v pertencente a V

É o número de vértices adjacentes a v.

Vértice Isolado
v é isolado quando possui grau 0.

Caminho
Um caminho do vértice v1 ao vértice vk é uma sequência de vértices v1...vk tal que (vj,vj+1) pertence a E, 1<=j<=|k-1|; diz-se que v1 atinge a alcança vk.

Um caminho de k-vértices é formada por k-1 arestas (v1,v2), (v2,v3) ... (vk-1,vk), e o valor k-1 é o comprimento do caminho.

v1, v2, v4, v5 é um caminho
comprimento do caminho = 3

Caminho simples ou elementar
Quando todos os vértices do caminho forem distintos

Trajeto
Um caminho onde todas as arestas são distintas.

caminho simples que liga 1 a 7: 1, 2, 3, 7
trajeto: 2, 3, 7, 6, 2, 1, 5

Ciclo
É um caminho v1, v2 ... vk, vk+1, onde v1 = vk+1 e k>=3
Se o caminho for simples, o ciclo também é dito simples ou elementar

Grafo acíclico é um grafo que não possui ciclos.

Ciclos idênticos
Dois ciclos são considerados idênticos se um deles puder ser obtido a partir do outro através da "notação" de seus vértices.

v1, v2, v3, v4, v1 é idêntico a v3, v4, v1, v2, v3

Caminho Hamiltoniano
É um caminho que contém cada vértice do grafo exatamente uma vez.
Um ciclo v1, ..., vk, vk+1 é hamiltoniano quando o caminho v1, ..., vk o for.

Caminho ou Ciclo Euleriano
É um caminho que contém cada aresta do grafo exatamente uma vez.

caminho hamiltoniano 3, 4, 5, 2, 1, 6
caminho euleriano 3, 4, 5, 3, 2, 5, 6, 2, 1, 6

Se um grafo G possui um ciclo hamiltoniano ou euleriano G é dito hamiltoniano ou euleriano, respectivamente.

Convenção:
Sempre que possível, usaremos os termos caminho e ciclo com o sentido de caminho simples e ciclo simples.

Grafo Conexo

Um grafo G(V,E) é conexo quando existe um caminho "entre cada par" de vértices de G, caso contrário, G é desconexo.
Obrigatoriamente, a representação geométrica de G é descontígua, se G for desconexo.

Grafo Totalmente Desconexo
Quando não possui arestas.

Distância entre dois vértices
Denomina-se distância d(v,w) entre os vértices v e w de um grafo ao comprimento do menor caminho entre v e w.

Operações de inclusão/exclusão de arestas ou vértices
Seja G(V,E) um grafo,

1) Seja e pertencente a E uma aresta G-e representa o grafo obtido pela exclusão da aresta e do grafo G.

2) Seja v, w um par de vértices não adjacentes em G.
G+(v,w) representa o grafo obtido adicionando-se a aresta (v,w) a G.

3) Seja v pertencente a V um vértice G-v representa o grafo obtido pela exclusão do vértice v, e das arestas a ele incidentes.

Teoria dos Grafos

Componentes de um Grafo