TEORIA DOS GRAFOS.

UNIVERSIDADE ESTATUAL DA PARAÍBA[pic 1]

CENTRO DE CIÊNCIAS EXATAS E SOCIAIS APLICADAS – CCEA

BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO

NOME:	ALLAN RAFAEL FERREIRA DE OLIVEIRA
DISCIPLINA:	TEORIA DOS GRAFOS
PROFESSOR:	ALANNA CAMYLLA COÊLHO MONTEIRO
TURNO:	MANHÃ

RESOLUÇÃO DO EXERCÍCIO

1. a) [pic 2]

b)[pic 3]

1. a) Os nós 3 e 1 não são adjacentes, pois para haver adjacência entre eles seria necessário haver um arco a = (3 ~ 1), o que não ocorre.

 

b) Os vértices 3 e 4 são adjacentes, pois existe um arco a6 = (3 ~ 4).

         

1. a) (1 ~ 2), (1 ~ 2), (2 ~ 3), (2 ~ 4), (3 ~ 4).

b) a3 = 1 - 1

c) a3 = 1 - 1, a2 = 1 - 2, a1 = 1 - 2

d) c1 (4,1) = 4 a6 3 a4 2 a1 1 a3 1

    len(c1 (4,1) ) = 4  

e) d1(n) = 4

    d2(n) = 4

    d3(n) = 2

    d4(n) = 2

1. a) Ele é conexo, pois existe um caminho para cada par de nó.

b) Não, um grafo completo deveria ter todos os vértices adjacentes aos outros vértices, o que não ocorre.

1. | N1 | = 8, | N2 | = 8

               | A1 | = 12, | A2 | = 12

      d(n1) = 8 x 3, d(n2) = 8 * 3 (lê-se 8 nós de 4)  

              f1: N1 → N2

                a → 1, b → 2, c → 3, d → 8, e → 5, f → 6, g → 7, h → 4.

              a ~ b, SSE, f(a) ~ f(b) = 1 ~ 2

              b ~ c, SSE, f(b) ~ f(c) = 2 ~ 3

              c ~ d, SSE, f(c) ~ f(d) = 3 ~ 8

              d ~ a, SSE, f(d) ~ f(a) = 8 ~ 1

              a ~ f, SSE, f(a) ~ f(f) = 1 ~ 6

              b ~ g, SSE, f(b) ~ f(g) = 2 ~ 7

              c ~ h, SSE, f(c) ~ f(h) = 3 ~ 4

              d ~ e, SSE, f(d) ~ f(e) = 8 ~ 5

               f ~ g, SSE, f(f) ~ f(g) = 6 ~ 7

             g ~ h, SSE, f(g) ~ f(h) = 7 ~ 4

             h ~ e, SSE, f(h) ~ f(e) = 4 ~ 5

             e ~ f, SSE, f(e) ~ f(f) = 5 ~ 6

1.          [pic 4]

...