Exerc Cio De Grafos

1

EXERCÍCIO DE GRAFOS
ATENÇÃO: AS QUESTÕES DESTA PÁGINA DEVEM ESTAR COM RESPSOTAS MANUSCRITAS,
AS DEMAIS DIGITADAS, CASO CONTRÁRIO, O EXERCÍCIO NÃO SERÁ ACEITO.
1) O que é um Grafo?
2) Desenhe a representação gráfica das matrizes de adjacências dos grafos abaixo:
G1
v1 v2 v3 v4 v5 v6 v1
0
1
1
1
1
1

v2
1
0
1
1
1
1

v3
1
1
0
1
1
1

v4
1
1
1
0
1
1

G3 v1 v2 v3 v4 v5 v6

v1
0
1
1
0
0
0

v2
1
0
1
1
1
0

v3
1
1
0
1
1
0

v4
0
1
1
0
1
1

G5 v1 v2 v3 v4 v5 v6 v7 v8

v1
0
0
0
0
0
0
5
0

v2
10
0
0
0
10
0
0
0

G7 v1r v2 v3 v4 v5 v6 v7 v1
0
0
0
0
0
0
0

v2
3
0
0
0
0
0
0

v3
0
5
0
0
0
0
0
0 v3 0
1
2
0
0
1
0

v4
0
0
10
0
0
0
0
10 v4 0
0
3
0
0
0
0

v5
1
1
1
1
0
1

v6
1
1
1
1
1
0

v5
0
1
1
1
0
1

v5
0
0
0
5
0
0
0
0 v5 0
0
0
1
1
3
0

G2 v1 v2 v3 v4 v5 v6

v6
0
0
0
1
1
0

v6
0
0
0
0
8
0
0
0 v6 0
0
0
0
3
0
0

v7
0
0
0
0
5
0
0
0 v7 0
0
0
0
0
2
3

v1
0
0
0
0
1
0

v1
1
0
1
0
0

G4 v1r v2 v3 v4 v5 v8
0
0
0
0
0
10
0
0

v2
0
0
0
0
1
1

G6 v1 v2 v3 v4 v5 v6 v7 v8

v1
0
1
0
1
1
0
0
0

G8 v1 v2 v3 v4 v5 v6 v7 v1
0
1
1
0
0
0
0

v3
0
0
0
0
0
1

v2
1
0
0
0
0

v2
1
0
0
1
0
1
0
0 v2 1
0
1
0
0
0
0

v3
0
0
0
0
1
1
1
0 v3 1
1
0
0
1
0
1

v4
0
0
0
0
1
1

v5
1
1
0
1
0
0

v3
0
1
0
0
1

v4
0
0
1
0
0

v4
1
1
0
0
0
0
0
1

v5
1
0
1
0
0
0
0
1

v4
0
0
0
0
0
0
0

v5
0
0
1
0
0
0
1

v6
0
1
1
1
0
0

v5
1
0
0
0
0

v6
0
1
1
0
0
0
1
0 v6 0
0
0
0
0
0
0

v7
0
0
1
0
0
1
0
1 v7 0
0
1
0
1
0
0

v8
0
0
0
1
1
0
1
0

2

Nome:

CONTINUAÇÃO DO EXERCÍCIO
Turno: Manhã

Noite

ATENÇÃO: A PARTIR DESTA PÁGINA, AS RESPOSTAS DEVEM ESTAR
DIGITADAS, INCLUSIVE O NOME COMPLETO!
A partir da questão 3, considere os grafos da questão 2 e as figuras da apostila.
Chamaremos de GD, o conjunto formado por todos os grafos da questão 2, ou seja,
GD = {G1, G2, G3, G4, G5, G6, G7, G8}
Considere também que G9 é o grafo formado por:
G3 – (a(v2-v3), a(v2-v4), a(v3-v5), a(v4-v5), a(v4-v6))
3) Construa a lista de adjacência de G6;
4) Construa a matriz de incidência de G5;
5) Construa a matriz figurativa por vértices de G4 e por arestas de G6;
6)