Lista02 Grafos

Prévia do material em texto

Universidade Federal Rural de Pernambuco 
Departamento de Estatística e Informática 
Bacharelado em Ciências da Computação 
Disciplina: Matemática Discreta II 
Professor: Maigan Alcântara 
 
Lista 02 – Grafos e Árvores 
Teoria dos Grafos 
 
1. O grafo de interseção de uma coleção de conjuntos 𝐴1, 𝐴2, . . . , 𝐴𝑛 é o grafo que tem um vértice para cada um 
dos conjuntos da coleção e tem uma aresta conectando os vértices se esses conjuntos têm uma interseção não 
vazia. Construa o grafo de interseção para as seguintes coleções de conjuntos. 
(a) 𝐴1 = {0, 2, 4, 6, 8} 𝐴2 = {0, 1, 2, 3, 4} 𝐴3 = {1, 3, 5, 7, 9} 𝐴4 = {5, 6, 7, 8, 9} 𝐴5 = {0, 1, 8, 9} 
 
(b) 𝐴1 = {. . . , −4, −3, −2, −1, 0}𝐴2 = {. . . , −2, −1, 0, 1, 2, . . . }𝐴3 = {. . . , −6, −4, −2, 0, 2, 4, 6, . . . } 
𝐴4 = {. . . , −5, −3, −1, 1, 3, 5, . . . }𝐴5 = {. . . , −6, −3, 0, 3, 6, . . . } 
 
(c) 𝐴1 = {𝑥|𝑥 < 0}𝐴2 = {𝑥| − 1 < 𝑥 < 0} 𝐴_3 = {𝑥|0 < 𝑥 < 1}𝐴4 = {𝑥| − 1 < 𝑥 <
 1} 𝐴_5 = {𝑥|𝑥 > −1}𝐴6 = 𝑅 
 
2. Desenhe os grafos abaixo: 
a) K7 b) K1,8 c) C7 d) W7 
 
4. Pode haver um grafo simples com 15 vértices, cada um com grau 5? 
 
5. Determine se cada um dos grafos abaixo é bipartido. 
 
 
 
6. Quantos vértices e quantas arestas têm os grafos abaixo? 
a) 𝐾𝑛 𝑏)𝐾𝑚,𝑛 𝑐)𝐶𝑛 𝑑)𝑄𝑛 𝑒)𝑊𝑛 
 
7. Quantas arestas tem um grafo com vértices de graus 5, 2, 2, 2, 2, 1? Desenhe um possível grafo. 
 
8. Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um possível grafo. 
a) 3, 3, 3, 3, 2 b) 1, 2, 3, 4, 5 c) 1, 2, 3, 4, 4 d) 3, 4, 3, 4, 3 e) 0, 1, 2, 2, 3 f) 1, 1, 1, 1, 1 
 
9. Quantos subgrafos com pelo menos um vértice tem 𝐾3? 
 
11. Para que valores de n os grafos abaixo são regulares? 
𝑎) 𝐾𝑛 𝑏)𝐶𝑛 𝑐) 𝑊𝑛 𝑑)𝑄𝑛 
 
12. Quantos vértices tem um grafo regular de grau 4 com 10 arestas? 
 
13. O grafo complementar G’ de um grafo simples G tem os mesmos vértices de G. Dois vértices são adjacentes 
em G’ se, e somente se, eles não são adjacentes em G. Determine os seguintes grafos. 
a) 𝐾’𝑛 𝑏)𝐾’𝑚,𝑛 𝑐)𝐶’𝑛 𝑑)𝑄’𝑛 
 
14. Se o grafo simples G tem v vértices e e arestas, quantas arestas tem G’? 
 
15. Mostre que se G é um grafo simples com n vértices, então G ∪ G’ = Kn. 
 
16. Represente a matriz de adjacência do grafo 𝑄3. 
 
17. Seja uma matriz simétrica quadrada formada apenas por 0's e 1's que tem apenas 0's na diagonal principal. Essa 
matriz pode representar a matriz de adjacência de um grafo simples? 
 
18. Os grafos abaixo são isomorfos? Se sim, apresente uma função de isomorfismo, caso contrário explique a sua 
resposta. 
a) 
 
 
b) 
 
 
c) 
 
 
19. Os grafos dados pelas matrizes de adjacência abaixo são isomorfos? 
 
 
20. Determine se cada um dos grafos abaixo é fortemente conectado, e caso não seja, se é fracamente conectado 
 
 
 
21. Quantos grafos simples conectados não isomorfos existem com n vértices, quando n é: (a) 2 (b) 3? 
 
22. Utilize caminhos para mostrar que os grafos abaixo não são isomorfos ou encontre um isomorfismo entre eles. 
 
 
23. Apresente um grafo que tenha um circuito Euleriano e um circuito Hamiltoniano mas que não sejam idênticos. 
 
24. Determine se existe um circuito ou caminho Euleriano nos grafos abaixo. Caso exista, indique a sequência de 
vértices. 
a) b) 
 
 
25. Um grafo possui oito vértices e seis arestas? Esse grafo é conexo? Justifique sua resposta. 
 
26. Suponha que um grafo planar conectado tenha 6 vértices, cada um com grau 4. Em quantas regiões a 
representação planar deste grafo divide o plano? 
 
 
27. Dado o mapa abaixo, construa o grafo dual e encontre o número de cores necessárias para colorir o mapa, 
de maneira que duas regiões adjacentes tenham cores diferentes. 
 
 
28. Dados os grafos abaixo, encontre o seu respectivo número cromático 
a) 
 
 
 
 
 
 
 
 
29. Suponha que um grafo planar conectado possui 30 arestas. Se uma representação planar deste grafo divide 
o plano em 20 regiões, quantos vértices possui este grafo? 
 
30. Suponha que um grafo planar conexo possui 35 vértices, cada um com grau 4. Em quantas regiões a 
representação dessa grafo divide o plano? 
 
31. Qual o número cromático de Wn? 
 
32. Quais dos grafos não planares abaixo possuem a propriedade que a remoção de qualquer vértice e todas as 
arestas incidentes a ele produz um grafo planar? 
(a) K5 (b) K6 (c) K3,3 (d) K3,4 
 
 
c) 
b) 
33. Imagine que você esteja organizando um casamento, para o qual foram convidadas 16 pessoas: A, B, C, … 
H são parentes do noivo e da noiva; I, J, K, … P são outros convidados do casamento. O problema é que algumas 
dessas pessoas não se dão muito bem: 
• A não se dá bem com F, G, ou H, 
▪ B não se dá bem com C, D, ou H, 
▪ C não se dá bem com B, D, E, G, ou H, 
▪ D não se dá bem com B, C, ou E, 
▪ E não se dá bem com C, D, F, ou G, 
▪ F não se dá bem com A, E, ou G, 
▪ G não se dá bem com A, C, E, ou F, 
▪ H não se dá bem com A, B, ou C. 
Como organizar a distribuição das mesas de maneira que pessoas que não se dêem bem sentem-se em mesas 
diferentes? 
 
 
 
Árvores 
 
34. Quantas arestas uma árvore binária cheia com 1000 vértices internos possui? 
 
35. Quantos vértices uma árvore cheia 5-ária com 100 nós internos. 
 
36. Use a codificação de Huffman para codificar os símbolos abaixo, dadas suas frequências. Qual o o número 
médio de bits necessários em cada caso. 
a) a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30. 
b) A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07, G: 0.08. 
 
37. Represente as expressões abaixo usando árvores binárias, e as expresse em notação pré-fixa, pós-fixa e 
infixa 
a) ((x + 2) ↑ 3) ∗(y −(3 + x)) − 5 
b) (x + xy) + (x/y) 
c) x + ((xy + x)/y) 
 
38. Mostre qual a soma dos graus dos vértices de uma árvore com n vértices. 
 
39. Suponha que uma carta deve ser enviada para 5 outras pessoas. Cada pessoa que a recebeu, deve passa-la 
para outras 5 pessoas que ainda não a tenha recebido ou não envie para ninguém. Suponha que 10.000 pessoas 
enviaram a carta antes da cadeia terminar, e que ninguém recebeu mais do que uma carta. Quantas pessoas 
receberam a carta, e quantas não a repassaram? 
 
40. Suponha que o endereço de um vértice v na árvore enraizada ordenada T é 3.4.5.2.4 
a) Em que nível está v? 
b) Qual o endereço do pai de v? 
c) Qual o menor número de vizinhos que v pode ter? 
d) Qual o menor número possível de vértices em T se v tem este endereço? 
 
41. a) Quantas árvores não enraizadas e não isomorfas com 3 vértices existem? 
b) Quantas árvores enraizadas e não isomorfas com 3 vértices existem? 
 
42. Quantas arestas existem em uma floresta de t árvores, contendo NO TOTAL n vértices? 
 
43. Toda árvore é um grafo bipartido? Explique a sua resposta.