Questões quinto semestre unip

1

UNIP. Curso: CC/SI Disciplina: Teoria dos Grafos.

Questões de Prova

Nome do aluno:______________________________________ RA:__________

1) Seja A = {a, b, c, d, e, f}, represente por pares ordenados:

a) Um dígrafo com 7 arestas: b) Um grafo de 8 arestas:

2) Sejam A = {a, b, c, d, e, f, g, h}: (deixe os cálculos indicados)

a) Quantos vértices tem o grafo/dígrafo? b) Quantas arestas são possíveis num grafo? e num dí

grafo? c) Quantos grafos com 4 arestas são possíveis?

3) Seja A = {a, b, c, d, e, f}: a) Construa um grafo com 6 arestas.

b) Dê o entorno de raio um de duas arestas do grafo que você construiu. c) O seu grafo é

conexo? Por quê? d) Escreva a matriz de incidência. e) Dê o peso dos vértices:

4) 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) Tem ciclos? Dê um exemplo

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

5) Desenhe um grafo completo com 6(seis) vértices.

6) 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 pode estar representando?

7) 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) Escolha dois vértices: ( , ) e ( , ) Represente um caminho entre os

dois. b) Tem ciclos? Represente um.

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

9) Represente um grafo desconexo com 7 vértices

10) Seja um grafo com 6 vértices cuja lista de pesos é dada por: 4 3 3 2 2 2. Faça uma

representação geométrica do mesmo.

11) 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.

12) 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.

2

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.

13) 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 que p = 4.

14) Seja A = {a, b, c, d, e, f}, escolha: a) Um dígrafo com 6 arestas. b) Um grafo de 6 arestas.

Sejam A = {a, b, c, d} e o grafo G dado por:

G ={(a, a), (a, b), (a, c), (b, c), (b, d), (c, c), (c, d), (d, c)}.

15) a) Dê o entorno de raio um dos vértices; b) Calcule a distância 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