Matemática Discreta 2012.13
Cursos: EI
Departamento de Matemática – ESTiG
Instituto Politécnico de Bragança
Ficha Prática 5: Cap4. Elementos da Teoria de Grafos
5
1. Considere cada um dos grafos seguintes.
a. Represente-o formalmente.
b. Determine o número de arestas e vértices. Determine os graus
dos vértices.
c. Escreva um caminho de comprimento maior que 3.
d. Escreva um circuito simples, um caminho não fechado e um
ciclo.
2. Represente graficamente os grafos k5, k6, k3,2 e k2,4.
3. Considere o grafo G na figura seguinte. Quais dos subgrafos G1,G2,G3
são subgrafos induzidos do grafo G?
4.
* Considere o grafo G na figura seguinte.
a. Defina um subgrafo de G que não seja um subgrafo induzido.
b. Descreva o subgrafo G1 como um subgrafo induzido de G.
c. G2 é um subgrafo induzido de G?
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
5.
ESTiG\IPB
Ficha Prática 5
pg 2
Verifique que os seguintes grafos não são isomorfos.
6. Escreva as matrizes de adjacência dos grafos da pergunta 1.
7. Esboce representações gráficas para os grafos relativos às seguintes
matrizes de adjacência.
3 ,
 2 2 1
 0 3 1 ,


1 1 1
1
2

0

1
2 0 1
0 1 0 
[(a)digrafo (b)grafo]
1 1 1

0 1 1
8.
Existe um grafo 4-regular com 10 arestas? E com 15 arestas?
9.
Mostre que a resposta ao problema das 7 pontes de Königsberg é
negativa.
10. Escreva, se existir, um caminho ou um circuito de Euler para cada
um dos grafos seguintes.
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Ficha Prática 5
pg 3
*
11. Obtenha um circuito de Hamilton do grafo.
a
f
b
g
e
g
hc
d
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Ficha Prática 5
pg 4
12. Determine os números cromáticos dos grafos seguintes. (para cada
grafo, mostre que não é possível colori-lo com um número de cores
inferior ao que encontrou).
13.
Mostre que o grafo g da questão 12 é planar.
14.
Apenas dois dos grafos são planares. Quais?
15.
O grafo seguinte é conhecido por grafo de Petersen. Mostre que
não é planar.
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
16.
ESTiG\IPB
Ficha Prática 5
pg 5
Num conjunto de 8 moedas exteriormente iguais, existe uma
mais pesada que as restantes, tendo estas igual peso. Qual o
número de pesagens mínimo a efectuar com uma balança de dois
pratos, para encontrar essa moeda? (sugestão: utilize uma árvore
ternária).
17.
Ordenar os vértices da árvore da figura.
a. Usando um percurso em preorder.
b. Usando um percurso em postorder.
18.
Ordenar os vértices da árvore usando um percurso em inorder.
19.
Encontrar uma árvore de cobertura do grafo a) da pergunta 12,
considerando as duas ordenações dos vértices a,b,c,d,e,f,g,h e
d,h,c,b,a,g,f,e.
a. Usando uma pesquisa depth-first.
b. Usando uma pesquisa breadth-first.
20.
Três missionários e três canibais encontram-se na margem de um
rio. Junto a essa margem existe um barco com capacidade para 2
ocupantes. Qual o número mínimo de travessias necessário para
transportar as 6 pessoas para a outra margem, de modo que no
decorrer do processo não tenhamos, em nenhuma margem, mais
canibais do que missionários?
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Ficha Prática 5
pg 6
21.
Temos 3 recipientes com capacidades de 10, 7 e 4 litros. O de 10
litros está cheio de água e os outros dois estão vazios. Qual o
número mínimo de transvases de água a efectuar, de modo que
fiquemos com 2 litros de água em um qualquer dos recipientes de
7 e 4 litros? As únicas medidas que podemos usar são as
capacidades dos recipientes.
22.
Encontrar uma spanning tree para o grafo da figura, considerando
pesquisas depth-first e breadth-first, e as ordenações de vértices
a.
*v7, v6, …, v1.
b.
v1, v2, …, v7..
23.
Qual o número máximo de vértices internos que pode ter uma
árvore quaternária completa, de altura 6?
24.
A árvore seguinte representa uma expressão algébrica.
a. Obtenha essa expressão
Na forma usual.
Em notação polaca.
Em notação polaca reversa.
b. Calcule o valor da expressão usando as notações polaca e
polaca reversa, considerando a=2,b=4,c=3,d=5,e=2,q=3,f=1,g=1.
x
/
+
a
c
b
/
_
g
f
q
d
25.
/
_
e
Encontre uma árvore de cobertura mínima para o grafo da figura.
Use o algoritmo de Prim, começando no vértice g.
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Ficha Prática 5
pg 7
26.
Considere o grafo da figura.
a. Utilize os algoritmos de Kruskal e Prim para obter uma
árvore de cobertura mínima.
b. Utilize o algoritmo de Dijkstra para obter as distâncias
mínimas do nó h aos restantes nós do grafo.
27.
* Utilize o algoritmo de Dijkstra para obter a distância mínima do
nó b ao nó g , no grafo não orientado da página 130 dos resumos
das aulas teóricas.
Bibliografia: http://www.ipb.pt/~mar/MD2013/Apresentacao.pdf
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar