Aula 3
519 palavras
3 páginas
Teoria dos GrafosAula 3
Aula passada
Exemplos
Definições
Algumas
propriedades
Aula de hoje
Representando
grafos
Matriz e lista
Figueiredo – 2011
Grafo
Grafo G=(V, E)
V = conjunto de vértices (inteiros)
E = conjunto de arestas (pares nãoordenados)
Representação
matemática
Exemplo
de grafos
V = {1, 2, 3, 5, 6, 7},
E = {(1,2), (1,5), (2,3), (2,6), (3,7), (5,7)}
1
2
3
5
6
7
Como representar no computador?
Figueiredo – 2011
Representando Grafos
Como representar grafos no computador?
Estrutura de dados
Duas estruturas fundamentais matriz lista
Qual é a estrutura mais adequada
(ou mais eficiente)?
Depende do algoritmo!
Figueiredo – 2011
Representação via Matriz
Como representar utilizando matrizes?
Idéia: associar vértices à linhas e colunas da matriz elemento da matriz indica se há aresta
Matriz de adjacência
Matriz n x n (n é número de vértices) aij = 1 , se existe aresta entre vértices i e j aij = 0 , caso contrário.
Figueiredo – 2011
Matriz de Adjacência
Exemplo
1
2
3
4
1
2
3
4
5
1
0
1
1
0
0
2
1
0
1
0
1
3
1
1
0
1
0
1
2
3
4
4
0
0
1
0
1
5
0
1
0
1
0
1
0
1
1
0
2
1
0
1
0
3
1
1
0
1
4
0
0
1
0
?
Figueiredo – 2011
Matriz de Incidência
Idéia: associar vértices às linhas e arestas às colunas elemento da matriz indica se aresta incide sobre o vértice
Matriz de incidência
Matriz n x m (n vértices, m arestas) aij = 1 , se vértice i incide sobre aresta j aij = 0 , caso contrário.
Figueiredo – 2011
Matriz de Incidência
Exemplo
1
e2
e1 e3 3
1
2
3
4
2
4
e4
e1 e2 e3 e4
1
1
0
0
1
0
1
0
0
1
1
0
0
0
1
1
e1 e2 e3 e4 e5 e6
1
2
3
4
5
1
1
0
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
?
Figueiredo – 2011
Desvantagem
Desvantagem da representação matricial? Considere grafos grandes e esparços grande: muitos vértices esparço: relativamente poucas arestas
Matriz formada principalmente de zeros!
Grande consumo de memória (desnecessário)!
Como resolver este problema?
Figueiredo – 2011
Representação via Listas
Idéia: associar a