A Teoria de Grafos

“Exercícios 1 á 3 figura 1”[pic 1]

1 - O grafo da figura possui ordem igual à:

D - 5 - Ordem 5 pela quantidade de vértices

2 - No grafo da figura, vértice 4 possui grau à: [pic 2]

A - 2 - Esta ligados pelo vértice 1 e 2.

3 - No grafo da figura, ao passarmos pelos vértices 1;3;2;5;1 respectivamente, é correto afirmar que:

B - Estamos fazendo um ciclo simples de comprimento igual a 4. - No exemplo, ele não passa pelo vértice 4 mas consegue completar o ciclo.

“Exercicios 4 figura 2”[pic 3]

4 -O grafo da figura possui 4 vértices. È correto afirmar que:

E - Este grafo possui 1 laço. - Um dos vértices ela com 1 laço[pic 4]

“Exercicios 5 figura3”

5 - No grafo acima o vértice de maior grau é o de número:[pic 5]

B - 6 - 6 esta ligado a outras 4 vértices.

6 - Podemos afirmar que a soma dos graus dos vértices de um grafo G não direcionado, é sempre um número:[pic 6]

B - Par - Ela vai possuir duas arestas.

7 - Um grafo completo simples indicado por K7:

C - Possui 21 Arestas - Um grafo K7 tem 21 arestas conectando os vértices.  [pic 7]

“Exercício 8 figura 4”

8 - Com relação aos grafos G, H e K dados abaixo, podemos afirmar que:

E - G, H e K são isomorfos entre si. - Eles são iguais, mas representados diferente, com 5 vértices e 6 arestas.[pic 8]

“Exercício 9 figura 5”[pic 9]

9 - Com relação aos grafos G, H e K dados acima, podemos afirmar que:

E - Os quatro grafos são isomorfos entre si. – Todos são iguais, representados de formas diferente, tendo 5 vértices e 6 arestas[pic 10]

“Exercicio 10 figura 6 ”10 - Considerando os  grafos A, B e C  acima,  podemos afirmar que:

D - não existem grafos isomorfos neste grupo. - Os grafos não são isomorfos pela forma que uma aresta foi representada, onde na A todos os vértices se comunicam com 3 vértices, na B uma das vértices se comunicam com apenas 2 vértices e C uma das vértices possui um multigrafo.[pic 11]

[pic 12]

“Exercício 11 figura 7”

11 - Considerando os  grafos A, B e C  acima,  podemos afirmar que :

C - B e C são isomorfos entre sí, mas não são isomorfos à A. - Apenas os grafos B e C são isomorfos, A não é isomorfo pois uma aresta esta colocada de uma maneira que altera as propriedades a deixando diferente das outras.

[pic 13]

Figura 7

“Exercício 12 figura 8”

12 - Considerando os  grafos A, B, C e D  acima,  podemos afirmar que:

E - os quatro grafos são isomorfos entre si. - Todos são isomorfos entre entre si, são iguais mas representados de formas diferente. 5 Vértices e 6 Arestas. [pic 14]

Figura 8

“Exercício 13 figura 9”

13 - 13 - Considerando os dois grafos 1 e 2 abaixo, podemos afirmar que:

B - O grafo 1 é planar. - O grafo 1 pode ser representado de uma forma onde as arestas não se cruzem[pic 15][pic 16]

14 - Com relação aos grafos K4 , K5 , K6, podemos afirmar que:

C - K4   é planar, mas K5  e K6 não. - Posso representar o K4 de modo que suas arestas não se cruzem, enquanto o k5 e k6 não.

15 - Com relação aos grafos K3,3 ,  K4,4  e  K5,5 , podemos afirmar que:

E - Nenhum deles é planar. - Não tem como desenhar eles sem que suas aresta se cruzem.

...