03-Nocoes Basicas de Grafos (completo)

Prévia do material em texto

25-10-2021
H. Rosa, ISCTEM: AED2-2021 1
Noções Básicas de Gráfos
INSTITUTO SUPERIOR DE CIÊNCIAS E TECNOLOGIA DE MOÇAMBIQUE
Licenciatura em Engenharia Informática
Algoritmos e Estruturas de Dados II – AED2
Docente: Henrique Rosa
Edição: 2021
Noções Básicas de Gráfos
Objectivos da Aula:
• Conceitos Básicos
• Grafos Orientados e Não Orientados
• Caminhos de Gráfos
• Ordem de Grafos e Graú de vértices
• Cíclo ou Circuito
• Conectividade
• Sub-gráfos
• Representação de Grafos
25-10-2021
H. Rosa, ISCTEM: AED2-2021 2
MOTIVAÇÃO
• Criar aplicações para analizar conjunto de 
ligações entre pares de objectos.
• Questões:
– Existe um caminho para ir de um objecto para outro 
seguindo as conexões?
– Qual a menor distância entre um objecto e outro?
– Quantos outros objectos podem ser alcançados a 
partir de um determinado objecto?
• Solução:
– Existe um Tipo Abstrato de Dados chamado <GRAFO> 
usado para modelar tais situações.
03 - Noções Básicas de Grafos 3
CONCEITOS BÁSICOS (1)
• Grafo: conjunto de vértices e arestas.
• Vértice: objecto simples que pode ter nome e 
outros atributos.
• Aresta: conexão entre dois vértices.
• Notação: G = (V,A)
– G: grafo
– V: conjunto de vertices/nós
– A: conjuntos de arestas/arcos
03 - Noções Básicas de Grafos 4
25-10-2021
H. Rosa, ISCTEM: AED2-2021 3
CONCEITOS BÁSICOS (2)
• Grafo Genérico - com arcos paralelos ou lacetes.
V = {1, 2, 3}
A = {(1; 1); (1; 2); (2; 1); (2; 3); (2; 3)}
• Grafo Simples - com arcos sem lacetes.
V = {1, 2, 3}
A = {(1; 2); (2; 1); (2; 3)}
03 - Noções Básicas de Grafos 5
Grafo Orientado
• Grafo orientado (ou Digraph)
– Os arcos têm sentido
V = {1, 2, 3}
A = {(1,2), (2,1), (2,3)}
03 - Noções Básicas de Grafos 6
25-10-2021
H. Rosa, ISCTEM: AED2-2021 4
Grafo Não Orientado
• Grafo não orientado (ou Undigraph)
– Os arcos não têm sentido único
V = {1, 2, 3}
A = {(1,2), (2,3)}
03 - Noções Básicas de Grafos 7
Grafo Etiquetado ou Pesado
• Grafo etiquetado ou pesado
– Os vertices, os arcos ou ambos têm uma etiqueta, 
um peso ou um custo.
03 - Noções Básicas de Grafos 8
25-10-2021
H. Rosa, ISCTEM: AED2-2021 5
CAMINHO
• Uma sequência não vazia de vértices v1, v2, .., vn (com n ≥ 1), tal 
que, para qualquer i = 1,2,..., n−1: (vi, vi+1) ∈ A.
• Comprimento do caminho: número de arcos do caminho.
• Comprimento pesado (num grafo pesado) do caminho: a soma dos 
pesos dos arcos do caminho.
• Caminho simples: se todos os vértices são diferentes, excepto, 
posivelmente, o primeiro e o último.
• Exs: 
– Caminho: 2,1,2,3
– Comprimento: 3
– Comprimento pesado: 55
03 - Noções Básicas de Grafos 9
CICLO OU CIRCUITO
• Num Grafo Orientado:
– Um caminho de comprimento positivo onde o primeiro e o último 
vértices são iguais.
• Num Grafo não Orientado:
– Um caminho de comprimento positivo, onde o primeiro e o 
último vértices são iguais, que não passa 2 vezes pelo mesmo 
arco.
• Um Grafo Cíclico é um grafo com ciclos, o contrário é Grafo 
Acíclico.
• Ex: 
– Ciclo: 2, 3, 4, 2
– Não é ciclo: 1, 2, 1
03 - Noções Básicas de Grafos 10
25-10-2021
H. Rosa, ISCTEM: AED2-2021 6
CONECTIVIDADE
• Grafo Fortemente Conexo:
– Grafo orientado tal que: (∀v,w ∈ V) existe um 
caminho de v para w.
• Grafo Fracamente Conexo:
– Grafo orientado tal que, ignorando o sentido 
dos arcos: (∀v,w ∈ V) existe um caminho de v 
para w e existem pelo menos dois vértices não 
mutuamente alcançáveis.
• Grafo Conexo:
– Grafo não orientado, tal que: (∀v,w ∈ V) existe 
um caminho de v para w. O contrário é 
Desconexo. 03 - Noções Básicas de Grafos 11
• Sub-grafo de (V, A):
– um grafo (V’, A’) tal que V’ ∈ V e A’ ∈ A.
• Sub-grafo de Cobertura de (V, A):
– um sub-grafo (V’, A’) de (V, A), com V’ = V.
• Todos os vértices de (V, A) estão representados em (V’, A’).
• Àrvore (livre): 
– um grafo não orientado, conexo e acíclico.
• Arvore de Cobertura de (V, A):
– Um sub-grafo de cobertura de (V, A) que é árvore.
SUB-GRAFOS E ÁRVORES
Sub-grafo
Árvore de cobertura
03 - Noções Básicas de Grafos
Grafo
12
25-10-2021
H. Rosa, ISCTEM: AED2-2021 7
Continua a ...
03 - Noções Básicas de Grafos 13
Ordem e Gráus
• Ordem de um Grafo
– A ordem de um grafo G é dada pela cardinalidade do 
conjunto de vértices, ou seja, pelo número de vértices de G.
• Grau de um Vértice
– O grau de um vértice é dado pelo número de arestas que 
lhe são incidentes.
– No caso do grafo ser orientado, a noção de grau é 
especializada em:
• Grau de emissão: o grau de emissão de um vértice v corresponde 
ao número de arestas que partem de v.
• Grau de recepção: o grau de recepção de um vértice v corresponde 
ao número de arestas que chegam a v.
03 - Noções Básicas de Grafos 14
25-10-2021
H. Rosa, ISCTEM: AED2-2021 8
Trabalho para Investigação
• O que é um circuito de Euler? Qual a principal 
característica?
• O que é circuito de Hamilton? Qual a principal 
característica?
03 - Noções Básicas de Grafos 15
REPRESENTAÇÃO DE GRAFOS
• 1. MATRIZ DE ADJACÊNCIAS
• 2. LISTA DE ADJACÊNCIAS
• 3. MATRIZ DE INCIDÊNCIAS (intercessão entre 
um vértice e as arestas que o ligam)
• ETC.
03 - Noções Básicas de Grafos 16
25-10-2021
H. Rosa, ISCTEM: AED2-2021 9
Pesquisar:
Arco (v1; v2) - O(1) Sucessores v - O(|V |)
Etiqueta de Arco - O(1) Antecessores v - O(|V |)
Inserir:
Arco (v1; v2) - O(1)
Remover: 
Arco (v1; v2) - O(1)
1. MATRIZ DE ADJACÊNCIAS
v0 v1 v2 v3 v4
V0 0 1 0 0 1
V1 0 0 1 0 0
V2 0 0 0 1 1
V3 1 0 0 0 0
V4 0 0 0 1 0
03 - Noções Básicas de Grafos 17
2. Listas Ligadas de Adjacências
de Sucessores
Pesquisar:
Arco (v1; v2) - O(|Suc(v1)|) Sucessores v - O(|Suc(v)|)
Antecessores v - O(|A |)
Inserir:
Arco (v1; v2) - O(|Suc(v1)|)
Remover: 
Arco (v1; v2) - O(|Suc(v1)|)
03 - Noções Básicas de Grafos 18
25-10-2021
H. Rosa, ISCTEM: AED2-2021 10
Listas Ligadas de Adjacências
de Sucessores e de Antecessores (1)
03 - Noções Básicas de Grafos 19
Listas Ligadas de Adjacências
de Sucessores e de Antecessores (2)
Pesquisar:
Arco (v1; v2) - O(|min(Suc(v1)|, |Ant(v2)|)
Sucessores v - O(|Suc(v)|)
Antecessores v - O(|Ant(v)|)
Inserir:
Arco (v1; v2) - O(|Suc(v1)|)
Se as listas forem duplamente ligadas e partilharem as células
Remover: 
Arco (v1; v2) - O(|min(Suc(v1)|, |Ant(v2)|)
Nos outros casos
Remover: 
Arco (v1; v2) - O(|max(Suc(v1)|, |Ant(v2)|)
03 - Noções Básicas de Grafos 20
25-10-2021
H. Rosa, ISCTEM: AED2-2021 11
3. MATRIZ DE INCIDÊNCIAS
a b c d e f g
V1 1 1 0 0 0 0 0
V2 0 1 1 0 0 1 0
V3 0 0 1 1 0 0 0
V4 0 0 0 1 1 0 1
V5 1 0 0 0 0 1 1
V6 0 0 0 0 1 0 0
03 - Noções Básicas de Grafos 21
EXERCÍCIOS (1)
1. DADO O GRAFO ABAIXO
1.1. REPRESENTE A MATRIZ DE ADJACENCIA.
1.2. REPRESENTE A LISTA DE ADJACENCIA 
(sucessores)... E
1.2. ... (de sucessores e antecessores).
03 - Noções Básicas de Grafos 22
v1 v2 v3 v4 v5 v6
V1 0 1 0 0 1 0
V2
V3
V4
V5
V6
25-10-2021
H. Rosa, ISCTEM: AED2-2021 12
Continua a ...
03 - Noções Básicas de Grafos 23
TIPO ABSTRACTO DE DADOS
GRAFO
Grafo (Vértices, Arcos)
03 - Noções Básicas de Grafos 24
25-10-2021
H. Rosa, ISCTEM: AED2-2021 13
Tipo Abstracto de Dados Vértice
public interface Vertex
{
// In practice, a vertex is an integer.
}
03 - Noções Básicas de Grafos 25
Tipo Abstracto de Dados Arco
com Etiqueta do Tipo L
public interface Edge<L>
{
// Returns the edge label.
L label( );
// Returns an array of length 2 with the edge end-vertices.
Vertex[] endVertices( );
// Returns the edge end-vertex that is distinct from the
// specified vertex.
Vertex oppositeVertex( Vertex endVertex );
}
03 - Noções Básicas de Grafos 26
25-10-2021
H. Rosa, ISCTEM: AED2-2021 14
TAD Qualquer Grafo (L) (1)
public interface AnyGraph<L>
{
// Returns the number of vertices.
int numVertices( );
// Returns the number of edges.
int numEdges( );
// Returns an iterator of the vertices.
Iterator<Vertex> vertices( );
// Returns an iterator of the edges.
Iterator<Edge<L>> edges( );
03 - Noções Básicas de Grafos 27
TAD Qualquer Grafo (L) (2)
// Returns an arbitrary vertex.
Vertex aVertex( );
// Inserts and returns theedge (vertex1, vertex2) and
// associates it with the specified label.
Edge<L> insertEdge( Vertex vertex1, Vertex vertex2, L label );
// Removes the specified edge.
void removeEdge( Edge<L> edge );
// Returns true if there is an edge of the form (vertex1, vertex2).
boolean edgeExists( Vertex vertex1, Vertex vertex2 );
}
03 - Noções Básicas de Grafos 28
25-10-2021
H. Rosa, ISCTEM: AED2-2021 15
TAD Grafo Não Orientado (L)
public interface UndiGraph<L> extends AnyGraph<L>
{
// Returns the degree of the specified vertex.
int degree( Vertex vertex );
// Returns an iterator of the vertices adjacent to the specified
// vertex.
Iterator<Vertex> adjacentVertices( Vertex vertex );
// Returns an iterator of the edges incident upon the specified
// vertex.
Iterator<Edge<L>> incidentEdges( Vertex vertex );
}
03 - Noções Básicas de Grafos 29
TAD Grafo Orientado (L) (1)
public interface Digraph<L> extends AnyGraph<L>
{
// Returns the in-degree of the specified vertex.
int inDegree( Vertex vertex );
// Returns the out-degree of the specified vertex.
int outDegree( Vertex vertex );
// Returns an iterator of the vertices adjacent to the 
// specified vertex along incoming edges to it.
Iterator<Vertex> inAdjacentVertices( Vertex vertex );
03 - Noções Básicas de Grafos 30
25-10-2021
H. Rosa, ISCTEM: AED2-2021 16
TAD Grafo Orientado (L) (2)
// Returns an iterator of the vertices adjacent to the specified
// vertex along outgoing edges from it.
Iterator<Vertex> outAdjacentVertices( Vertex vertex );
// Returns an iterator of the incoming edges to the specified
// vertex.
Iterator<Edge<L>> inIncidentEdges( Vertex vertex );
// Returns an iterator of the outgoing edges from the specified
// vertex.
Iterator<Edge<L>> outIncidentEdges( Vertex vertex );
}
03 - Noções Básicas de Grafos 31
EXERCÍCIOS (2)
2. DADO O GRAFO ABAIXO
2.1. CLASSIFIQUE O GRAFO EM TERMOS DE CIRCUITO.
2.2. INDIQUE O COMPRIMENTO DO CAMINHO: 
v1,v2,v3,v4.
2.3. CALCULE O COMPRIMENTO PESADO DO 
CAMINHO: v1,v2,v5,v4.
03 - Noções Básicas de Grafos 32
25-10-2021
H. Rosa, ISCTEM: AED2-2021 17
REFERÊNCIAS
BIBLIOGRAFIA BÁSICA:
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stain, C. (2009). Introduction to Algorithms 
(3rd edition). The MIT Press.
• Goodrich, M. T., Tamassia, R. & Goldwasser, M. H. (2014). Data Structures and 
Algorithms in Java. (6th Edition). John Wiley & Sons.
• Weiss, M. A. (2012). Data Structures and Algorithm Analysis in Java (3rd edition). 
Pearson.
BIBLIOGRAFIA COMPLEMENTAR:
• Mamede, M. (2010/2011). Análise e Desenho de Algoritmos (Acetatos). DI-FCT/UNL. –
Base das aulas teóricas
• Drozdek, A. (2012). Data Structures and Algorithms in C++ (4th edition). Cengage
Learning.
• Shafer, C. A.(2011). Data Structures and Algorithm Analysis in Java/C++ (3rd edition). 
Dover Publication
03 - Noções Básicas de Grafos 33