Teoria dos Grafos Ciências da Computação

                 Teoria dos Grafos - Lista Atividade 2       [pic 1]



Curso: Ciências da Computação
Turma: CC5P42
Aluno: Matheus Miranda Borges
N.A: N278AH-3

Questão 1.  São Planares, porque são grafos que podem ser imersos no plano. Um detalhe interessante sobre esta imersão (que corresponde a uma forma de desenho, exatamente um desenho sem cruzamentos) é dado por um resultado no qual estabelece que um grafo planar pode sempre ser desenhado no plano (sem cruzamentos) de modo que suas arestas sejam retas.

Questão 2.    |V| - |E| + f = k + 1

                        9 – 10 + f = 2 + 1      🡪  f = 4            N° de faces é igual a 4.

Questão 3.   f = |E| - |V| + 2

                       f = 12 – 6 + 2              🡪  f = 8            N° de faces é igual a 8.

Questão 4.  |E| <= 3 x |V| - 6

                      8 <= 3 x 5 - 6

                      8 <= 9                               Não é planar, mas ele satisfaz o teorema.

Questão 5. |E| <= 3 x |V| - 6

                     10 <= 3 x 5 - 6

                     10 <= 9                              Não é planar e não satisfaz o teorema.

Questão 6. |E| <= 2 x |V| - 4

                     4 <= 2 x 4 – 4

                     4 <= 4                                 Não é planar, mas ele satisfaz o teorema

Questão 7. O caminho mais curto é A C D G H igual a 17 unidades.

Questão 8.      

Vértices	Peso 1	Peso 2	Peso 3	Peso 4	Peso 5	Peso 6
S	(0,S)
B	(4,S)	(4,S)
C	(5,S)	(7,B)	(7,B)
D		(9,B)	(15,C)	(15,C)
E			(17,C)	(17,D)	(17,D)
T				(19,D)	(19,E)	(19,E)

 

De acordo com o algoritmo de Dijkstra, o menor caminho seria S B C D E T

...