Disciplina: Matemática Discreta

Lista no 1: Teoria de grafos e árvores

1. Um grafo tem 21 arestas, 7 vértices de grau 9. Qual o número de arestas de um grafo

1, 3 de grau 2, 7 de grau 3, o resto de grau simples G, sabendo que |V (G)| = 56 e
4. Quantos vértices tem o grafo? |E(Gc )| = 80?

2. Mostre que não existe grafo de 12 vértices 10. Caracterize o complementar de cada um
e 28 arestas no qual dos seguintes grafos:
(a) o grau de cada vértice é 2 ou 4; (a) Kn (b) Km,n
(b) o grau de cada vértice é 3 ou 6. 11. Se G tem n vértices, de graus d1 , d2 , . . . , dn
e a arestas. Quantos vértices e arestas tem
3. Decida se pode existir um grafo G com
o seu complementar? Quais são os graus
vértices que têm graus 2, 3, 3, 4, 4, 5. E
dos vértices de Gc .
graus 2, 3, 4, 4, 5?
4. Existem 11 equipes em uma liga de 12. Desenhe um grafo não orientado
futebol. O organizador da liga decide que representado pela seguinte matriz de
cada equipe irá jogar cinco jogos contra adjacência:
diferentes oponentes. Explique porque essa 
1 2 0 1

ideia não irá funcionar.  2 0 3 0 
(a)  
5. Qual o número de arestas de um grafo  0 3 1 1 
completo de Kn ? 1 0 1 1
 
6. Qual o número de arestas de um grafo 0 2 0 1
 2 0 2 1 
completo de Km,n ? (b) 
 0

2 0 1 
7. Seja Gn um grafo com vértices V = 1 1 1 0
{1, 2, 3, 4, . . . , 3n} e em que dois vérices
i; j ∈ V são adjacentes se e só se, seu 13. Desenhe um digrafo representado pela
produto ij é múltiplo de 3. Por exemplo: seguinte matriz de adjacência:
 
1 2 1
(a) 2 0 0
 
0 2 2
 
0 2 3 0
 1 2 2 1 
(b) 
 2 1 1

0 
1 0 0 2

14. caracterize a matriz de adjacência do grafo

completo Kn .
5n2 − n
Prove que |E(Gn )| = . 15. Identique a forma geral da matriz de
2
adjacência do grafo bipartido completo
8. Suponha que G e Gc têm 10 e 5 arestas, Km,n .
respectivamente. Quantos vértices tem o
grafo G? 16. Determine se os grafos são isomorfos
Matemática Discreta Lista de Exercícios

(a) um caminho de comprimento 9;

17. Considere os seguintes grafos. (b) ciclos de comprimento 5, 6 e 8.
 
1 1 2
22. Seja A =  1 0 1  .
2 1 0
(a) Ache A2 e A3 .
(b) Considere um grafo G =
({v1 , v2 , v3 }, E) com matriz de
adjacência A. Use a resposta da
alínea anterior para determinar o
número de caminhos de comprimento
2 de v1 para v3 .
Prove que apenas dois grafos são isomorfos.
(c) Determine o número de caminhos de
18. Mostre que dois grafos simples são comprimento 3 de v1 para v3 .
isomorfos se e somente se os seus 23. Considere a seguinte matriz de adjacência
complementares são isomorfos. de um grafo G = ({v1 , v2 , v3 , v4 }, E)
19. Use o exercício anterior, para justicar se
 
0 1 1 0
são ou não isomorfos os seguintes grafos:  1
 0 2 1 

 1 2 0 1 
0 1 1 1
Determine
(a) o número de caminhos de
comprimento 2 de vértice v2 para v3 ;
(b) o número de caminhos de
comprimento 2 de vértice v3 para v4 ;
(c) o número de caminhos de
comprimento 3 de vértice v1 para v4 ;
(d) o número de caminhos de
20. Diremos que um grafo é autocomplementar comprimento 2 de vértice v2 para v3 ;
se é isomorfo ao seu complementar. 24. Indique os valores de n para os quais o
Quantas arestas tem um grafo grafo Kn é euleriano.
autocomplementar de n vértices?
25. Indique os valores de m e n para os quais
21. Nos grafos seguintes, procure: o grafo Km,n é euleriano.

© T.Sambo Página 2 de 7. . .
Matemática Discreta Lista de Exercícios

26. Para quais valores de m e n o grafo para os restantes vértices; (ii) o caminho
bipartido Km,n é hamiltoniano? mínimo de S para A.
27. Considere os seguintes grafos

29. Determine o caminho mínimo de A para os

restantes vértices do grafo

30. considere a rede

(a) Quais são semi-eulerianos?

Justique!
(b) Quais são eulerianos? Justique!
(c) Quais são hamiltonianos?

28. Aplicando o algoritmo de Dijkstra,

determine: (i) o caminho mínimo de S

© T.Sambo Página 3 de 7. . .
Matemática Discreta Lista de Exercícios

(a) Verique a lei de conservação do uxo

nos vértices a, d e e;
(b) Determine o valor do uxo;
(c) Enumere as arestas saturadas;
(d) Diga justicando, se é possível
aumentar o uxo por cada um dos
seguintes caminhos: (i) sbdt; (ii)
sbect.
(e) Ache a capacidade do corte denido
por S = {s, a, b}, T = {c, d, e, t};
(f) Diga justicando se o uxo dado é
máximo.
(g) Determine o uxo máximo.

31. Determine um uxo máximo e um corte

mínimo para cada uma das redes a seguir
33. Sejam A1 = (V1 , E1 ), A2 = (V2 , E2 ) duas
representadas.
árvores com |E1 | = 17 e |V2 | = 2|V1 |.
Determine |V1 |, |V2 | e |E2 |.
34. Dê exemplo de um grafo G = (V, E) com
|V | = |E| + 1, que não seja árvore.

35. Determine a quantidade de folhas de uma

árvore de quatro vértices de grau 2, um
vértice 3, dois vértices de grau 4 e um
vértice de grau 5.
36. Uma árvore de 37 vértices, possui 25
vértices com grau 1, 3 vértices com grau 2,
3 vértices com grau 4, 1 vértice com grau 5
e 2 vértices com grau 6. ela também possui
um vértice de grau desconhecido. Qual
deverá ser esse grau para garantir que o
grafo é realmente uma árvore?
37. Para quais valores de n o grafo Kn é uma
árvore?
38. Para quais valores de m e n o grafo
bipartido Km,n é uma árvore?
39. Apresente todas árvores geradoras do grafo
K4 .

32. Obtenha um uxo máximo e um corte 40. Quantas árvores geradoras não isomorfas
mínimo para a rede possui o k2,3 ?

© T.Sambo Página 4 de 7. . .
Matemática Discreta Lista de Exercícios

41. Quantas árvores geradoras não isomorfas 43. Como encontraria a árvore geradora
possui o K2,m ? máxima em um grafo com pesos?
42. Ache a árvore geradora mínima dos grafos 44. Determine a árvore geradora máxima de
de cada um dos seguintes usando: (a) cada um dos grafos do exercício 42.
algorítmo de Prim e (b) algorítmo de
Kruskal. 45. Dado o alfabeto que consiste das letras
A=30; B=2; F=14; G=3; H=12; I=25;
M=15; N=9; O=8; R=20; U=6, e as
frequências correspondentes.

(a) Ache a árvore óptima e o código

prexo correspondente;
(b) Obtenha a sequência de carateres
que deu origem a sequência binária:
110111001000000001011001
(c) Codique a palavra: GRAFO.

46. Considere a tabela de frequência dos

símbolos do alfabeto {a, c, d, e, l, n, (, ), +}
Carater a c d e l n ( ) +
frequência 7 12 4 9 10 8 2 19 29

(a) Ache a árvore óptima e o código

prexo correspondente;
(b) Obtenha a sequência de carateres que
deu origem a sequência binária:
i. 01011111110110011101
ii. 11000110011001100101111
(c) Codique a mensagem: (d + e)
(d) Codique a mensagem: c + d

© T.Sambo Página 5 de 7. . .
Disciplina: Matemática Discreta
Lista no 2: Linguagens, Gramáticas e Autómatos

1. Classique as seguintes gramática: Quais das seguintes linhas são reconhecidas

pelo autómato
(a) T = {a, b}, N = {σ, A} com as
regras de produção (a) bb;
σ → bσ|aA|b, A → aσ|bA|a (b) aabbbaba;
(b) T = {a, b}, N = {σ, A, B} com as (c) babbbbbabaa;
regras de produção
(d) bbaaaabaa.
σ → AB, AB → BA,
A → aA|a, B → Bb|b 5. Caracterize a linguagem reconhecida pelo
(c) T = {a, b}, N = {σ, A, B} com as autómato nito
regras de produção
σ → A|AAB, Aa → ABa,
A → aa, Bb → ABb,
AB → ABB, B → b
(d) T = {a, b}, N = {σ, A} com as
regras de produção σ → aA, A →
aA, A → a e símbolo inicial σ.

2. Considere α1 = bbabbab, α2 = abab,

α3 = aabbaab, α4 = abbbaabab,
α5 = abaabbabba. Determine se αi ∈ L(G), 6. Especique um autómato nito
para cada G do exercício 1. determinístico, que de entre as palavras
3. Especique uma gramática regular para que se escrevem com os símbolos do
a linguagem sobre {a, b} constituída por alfabeto {a, b}, reconheça as que:
palavras que: (a) contêm ab;
(a) começam por aa; (b) terminam em ab;
(b) terminam em aa; (c) começam com aa e terminam em bb;
(c) não terminam em ab; (d) começam com aa ou terminam em bb;
(d) começam em a ou terminam em b; (e) terminam em aba;
(e) começam em a e terminam em b; (f) entre dois a's consecutivos, tenham no
máximo um b.
4. Considere o autómato
(g) têm dois a's ou dois b's consecutivos.
(h) começam em aa e não terminam em
aa;

7. Especicar um autómato que, de entre

as palavras que se escrevem com os
símbolos do alfabeto {0, 1, 2}, aceita as
que, somados os números, originam um
múltiplo de três. Mostrar, em seguida,
recorrendo ao critério de aceitação por
Matemática Discreta Lista de Exercícios

autómato nito determinístico, que a (a) N = {σ, A, B}, T = {a, b}, P =

palavra 201 é aceite por esse autómato, {σ → aA, σ → bA, A → aB, σ →
mas que a palavra 101 não é aceite. b, B → b};

8. Considere o autómato (b) N = {σ, A, B}, T =

{a, b}, P = {σ → aA|bB|a, A →
aA|aσ|bB, B → bB|a|b}.

11. Dena uma gramática regular que gera a

linguagem reconhecida por

Quais das seguintes linhas são reconhecidas

pelo autómato
(a) abba; 12. Construa um autómato nito não
determinístico que aceita linhas nao vazias
(b) ababab; de a e b satisfazendo a condição:
(c) aaaabbabbb;
(a) contém exactamente um a;
(d) aabb
(b) contém pelo menos um a;
9. Especicar um autómato nito não (c) começam por aa;
determinístico que, de entre as palavras
que se escrevem com os símbolos do (d) termina em aa.
alfabeto binário, aceite apenas as que têm (e) começam com abb e terminam em ab;
1 na antepenúltima posição. Recorrendo (f) todo símbolo a aparece entre dois b0 s;
ao critério de aceitação por autómato nito
não determinístico, mostrar que a palavra (g) com número ímpar de a0 s e número
1100 é aceite por esse autómato. par de b0 s e contendo a linha ababa.
(h) contém a sequência bb ou bab.
10. Construa o autómato nito não
determinístico que aceita a linguagem 13. Transforme os autómatos não determinísticos
gerada pela gramática regular G(N, T, P, σ), obtidos nas alíneas 12b e 12d, em
onde: autómatos determinísticos equivalentes.

© T.Sambo