Questões quinto semestre unip

...

entre os vértices:

c) Qual o diâmetro do grafo? d) O grafo é conexo? Por quê?

16) Seja o grafo G de uma relação a seguir:

a2

a1 a3

a4

a) Escreva a matriz de incidência; b) Dê o peso dos vértices:

17) Seja o grafo G, a seguir, de uma relação qualquer, dê a sua matriz de incidência.

a2

a2

a1 a3

a4

18) Seja a matriz de incidência de um grafo G dada por:

G =

1 0 0 1

0 1 1 0

0 1 1 1

1 0 1 1

a) O grafo é Eureliano? Por quê? b) Tem ciclos? Dê um exemplo

c) Escolha dois vértices: há um caminho entre os dois? Dê o caminho.

19) Dada a matriz de incidência de um grafo quais das perguntas podem ser respondidas:

a) Quantas arestas têm o grafo. b) Há pontos isolados? c) O grafo é conexo? d) Qual o peso de

cada vértice? e) Qual a representação geométrica? f) Qual o problema do cotidiano que ele está

representando?

3

20) Sejam os grafos G1 e G2 dados a seguir:

G1 = G2

=

Eles são isomorfos? Dê o isomorfismo nomeando os vértices.

21) Se todos os vértices de um grafo possuem o mesmo peso ele é dito regular.

Quais dos grafos a seguir são regulares:

a) Completos; b) Quadriláteros. c) O tetraedro, d) Os ciclos e) As árvores.

22) Se dois grafos são isomorfos podemos concluir que eles possuem o mesmo número de vé

rtices e o mesmo número de arestas? De exemplo. A recíproca é verdadeira?________

23) Um grafo tem como matriz de adjacência a matriz:

G =

0 8 12 5

8 0 16 3

12 16 0 2

5 3 2 0

Invente um problema do cotidiano cujo grafo tem essa matriz.

24) Seja A = {1, 2, 3, 4, 5, 6, 7, 8, 9} os vértices do dígrafo G dado por:

G = {(1, 2), (1, 8), (1, 9), (2,7), (3, 4), (3, 6), (4, 9), (5, 1), (6, 4), (6, 1), (7, 3), (8,5),

(8, 7), (9, 3), (9, 5)}. a) Tem cadeias? Represente uma. b) São Eurelianas? Dê uma.

c) Tem ciclos? Represente um.

25) No espaço a seguir represente uma quadra que possua três casas, não alinhadas na borda da

quadra. Represente numa borda distinta das casas três tubulações de água, luz e telefone. Faça

um grafo de abastecimento para as três casas de modo que as tubulações não se cruzem.

26) Seja Z2 = {0, 1} e Z2

2

= { (0,0), (1, 0), (0,1), (1,1)} represente um grafo em Z2

2

e Z2

3

.

27) a) O que significa colorir vértices e arestas de um grafo? b) O que é número cromático de

um grafo? Qual o menor número cromático de um grafo planar?

28) Dê um exemplo de um grafo que é uma árvore com no mínimo 6 vértices.

29) Seja um grafo com 8 vértices cuja lista de pesos é dada por: 3 3 3 1 1 1 1 1. Faça duas

representações geométricas.

30) Mostre que todo grafo com dois ou mais vértices, tem pelo menos dois vértices de mesmo

peso(grau).

31) É possível que um grafo tenha exatamente um vértice com valência par e o resto com valê

ncia impar? dê um exemplo.

32) Dado um grafo obtemos sua lista de valência (pesos dos vértices). Inversamente dada uma

lista de inteiros positivos, podemos obter grafos cujos pesos correspondem a essa lista. Quais

das seguintes listas podem corresponder a um grafo?

a) 4, 4, 4, 4, 4 b) 4, 4, 2, 2, 2 c) 4, 4, 3, 3, 2 d) 4, 4, 4, 3, 2.

4

33) O grafo das palavras é definido assim: cada vértice é uma palavra da língua portuguesa e

duas palavras são adjacentes se diferem em exatamente uma posição: por exemplo: rato e ralo sã

o adjacentes e ralo e rota não são. Faça o grafo definido pelas palavras: caiado; cavalo;

cavado; girafa; girava; ralo; ramo; rata; rato; remo; reta; reto; rota; vaiado; varado;

virada; virado; virava.

34) Represente duas árvores com 5 vértices. Qual a soma dos pesos dos vértices?

35) Uma árvore com 8 vértices possui a lista de pesos, graus, dos vértices dada por:

4, 3, 2, 1, 1, 1, 1, 1. Faça duas representações geométricas.

36) Os hidrocarbonetos conhecidos como alcanos (etano, butano, isobutano) têm fórmula quí

mica dada por: CpH2p+2 onde:

C = molécula de carbono (peso 4) e H = molécula de hidrogênio (peso 1).

Represente graficamente duas possibilidades para um alcano em