Mestrado em Informática
Representação computacional de
redes de fluxo
Maria Claudia Silva Boeres
[email protected]
Teoria dos Grafos
UFES
Tipos de representação
• As principais são:
– Matriz de incidência
– Matriz de adjacência
– Lista de adjacências
– Forward e Reverse Star
Teoria dos Grafos
UFES
Matriz de incidência
Teoria dos Grafos
UFES
Matriz de adjacência
1
2
3
4
5
1
0
1
0
0
0
2
0
0
1
1
0
3
0
0
0
1
1
4
1
1
0
0
1
5
0
0
0
0
0
Teoria dos Grafos
UFES
Lista de adjacências
Teoria dos Grafos
UFES
Forward Star
6
9
Teoria dos Grafos
UFES
Reverse Star
arc
cost
1
11
30
(4,1)
2
2
5
(1,2)
rpoint
3
3
8
(4,2)
1
1
4
7
10
(2,3)
2
2
5
4
20
(2,4)
3
4
6
5
25
(3,4)
4
5
7
9
50
(3,5)
5
7
8
4
50
(4,5)
6
9
Teoria dos Grafos
capacity (tail,read)
UFES
Compact Forward
and Reverse Star
trace
rpoint
6
1
1
1
2
2
7
3
4
2
4
5
3
5
7
6
9
4
6
9
5
8
Teoria dos Grafos
UFES