Exercícios resolvidos - teoria dos grafos

Prévia do material em texto

1) 
Um ​grafo é simples se ele não tem laços nem mais de uma aresta ligando dois 
vértices. 
 
Um multigrafo é ​é um grafo não dirigido que pode possuir arestas múltiplas (ou 
paralelas), ou seja, arestas com mesmos nós finais. Assim, dois vértices podem 
estar conectados por mais de uma aresta. 
 
 
 
 
2) 
 
 
 
 
 
 
3) 
 
 
 
4) 
a - 
 
 
b - 
 
 
d - 
 
 
 
 
e - 
 
 
f - 
 
 
5 - Dados os grafos da questão anterior, classifique-os como simples ou 
multigrafos. 
a) Multigrafo 
b) Multigrafo 
c) Grafo simples 
d) Grafo simples 
e) Muiltigrafo 
 
 
6 - 
a) 
 
 
b) 
 
 
7 - 
a) Sim 
b) Não 
c) Sim 
d) Sim 
e) Sim 
f) Sim 
g) Sim 
 
 
8) 
 
a - 
 
 
 
b - 
 
 
c - 
 
 
9) 
 
10) 
(X) Os vértices v e w são adjacentes; 
(X) A aresta 2 é incidente ao vértice u; 
 
11) 
 
 
 
 
 
 
A quantidade de arestas é dada pela fórmula da combinação 2 a 2