Lista 3

Prévia do material em texto

Instituto de Ciências Exatas 
Departamento de Ciência da Computação 
Disc. DCC059 – Teoria dos Grafos Período: 2014-1 
Prof. Stênio Sã. 	
  
3ª Lista de Exercícios 	
  1)	
  Considere	
  o	
  algoritmo	
  de	
  busca	
  em	
  profundidade	
  em	
  grafos.	
  Dado	
  o	
  grafo	
  a	
  seguir	
   e	
   o	
   vértice	
   A	
   como	
   ponto	
   de	
   partida,	
   determine	
   a	
   ordem	
   em	
   que	
   os	
  vértices	
  são	
  visitados.	
  	
  	
  	
  	
  	
  	
  2)	
   Considere	
   o	
   algoritmo	
   abaixo.	
   Ele	
   resolve	
   o	
   problema	
   do	
   Conjunto	
  Independente	
  Máximo?	
  Justifique	
  sua	
  resposta.	
  
 
 
 	
  3)	
  Encontre	
  os	
  seguintes	
  valores	
  para	
  cada	
  grafo	
  abaixo	
  e	
  mostre	
  soluções	
  com	
  esses	
  valores	
  (por	
  exemplo,	
  se	
  o	
  número	
  cromático	
  é	
  3	
  apresente	
  uma	
  coloração	
  com	
  3	
  cores):	
  a)	
  β	
  =	
  número	
  de	
  cobertura	
  (tamanho	
  da	
  menor	
  cobertura)	
  	
  b)	
  χ	
  =	
  número	
  cromático	
  (quantidade	
  mínima	
  de	
  cores)	
  	
  
	
  4)	
  Na	
  tabela	
  abaixo	
  estão	
  as	
  atividades	
  envolvidas	
  em	
  um	
  projeto	
  de	
  um	
  coral	
  a	
  luz	
  de	
  velas.	
  a.	
  Construa	
  a	
  rede	
  associada	
  às	
  atividades	
  deste	
  projeto	
  b.	
  Determine	
  o	
  caminho	
  crítico	
  na	
  rede	
  construída	
  no	
  item	
  anterior	
  	
  	
   Atividades	
   Predecessoras	
   Duração	
  (dias)	
  A:	
  Selecionar	
  música	
   -­‐	
   2	
  B:	
  Aprender	
  música	
   A	
   14	
  
Universidade Federal de Vic¸osa
Departamento de Informa´tica
prof. Andre´ Gustavo dos Santos
INF 330 - Teoria e Modelos de Grafos - 2012/2
6a Lista de Exerc´ıcios Colorac¸a˜o, Clique, Cobertura, Conj.Indep. Para: 14/fev/2012
1. Encontre os seguintes valores para cada grafo da figura 1 e mostre soluc¸o˜es com esses valores
(por exemplo, se o nu´mero croma´tico e´ 3 apresente uma colorac¸a˜o com 3 cores):
a) ↵ = nu´mero de independeˆncia (tamanho do maior conjunto independente)
b) � = nu´mero de cobertura (tamanho da menor cobertura)
c) � = nu´mero croma´tico (quantidade mı´nima de cores)
G1 G2 G3 G4
2. Fac¸a o mesmo da questa˜o anterior, pore´m considerando arestas, em vez de ve´rtices (ou seja,
encontra ↵0, �0, �0)
3. Prove as seguintes afirmac¸o˜es:
(i) O nu´mero croma´tico de um grafo que tem clique ma´ximo tamanho n e´ no mı´nimo n
(ii) Existe grafo que tem clique ma´ximo de tamanho n e nu´mero croma´tico maior que n
4. Prove que sim ou que na˜o:
(i) Existe grafo com mais de um ve´rtice e nu´mero croma´tico igual a 1
(ii) Existe grafo com mais de uma aresta e nu´mero croma´tico igual a 1
(iii) Existe grafo com mais de um ve´rtice e ı´ndice croma´tico igual a 1
(iv) Existe grafo com mais de uma aresta e ı´ndice croma´tico igual a 1
(v) Quanto mais ve´rtices tem um grafo, maior seu nu´mero croma´tico
(vi) Quanto mais arestas tem um grafo, maior seu ı´ndice croma´tico
5. Um grafo dual de um grafo G e´ um grafo com um ve´rtice representando cada face de G e uma
aresta representando cada aresta de G, unindo ve´rtices cujas faces correspondentes sejam
adjacentes.
(i) Encontre um grafo cujo grafo dual tenha mu´ltiplas arestas
(ii) Encontre um grafo cujo grafo dual tenha loop
(iii) Encontre um grafo cujo grafo dual seja isomorfo a ele
(iv) Construa o grafo dual do mapa dos estados da regia˜o sul do Brasil
6. Mostre que um grafo simples e´ bipartido se e somente se ele e´ 2-color´ıvel
7. Mostre que �(K5) = 5. Isso contradiz o Teorema das 4 cores?
8. POSCOMP 2003-40
Quais dos quatro grafos abaixo sa˜o Eulerianos?
(a) somente I e II
(b) somente I
(c) somente II
(d) somente I, II e IV
(e) nenhum deles e´ Euleriano
9. POSCOMP 2004-33
Considere as seguintes afirmac¸o˜es sobre um grafo G com n > 0 ve´rtices:
I. Se G e´ conexo o nu´mero de arestas e´ maior que n;
II. G sera´ ac´ıclico somente se o nu´mero de arestas for menor que n;
III. Se G na˜o tem triaˆngulos enta˜o G e´ planar;
IV. G e´ Euleriano se, e somente se, todo grau e´ par.
As afirmativas verdadeiras sa˜o:
(a) I e II
(b) I e III
(c) II e III
(d) II e IV
(e) II, III e IV
10. POSCOMP 2009-30
Considere o algoritmo de busca em largura em grafos. Dado o grafo a seguir e o ve´rtice A
como ponto de partida, a ordem em que os ve´rtices sa˜o descobertos e´ dada por:
(a) A B C D E F
(b) A B D C E F
(c) A C D B F E
(d) A B C E D F
(e) A B D F E C
11. The Marriage Problem: suponha um grupo de homens e e um grupo de igual nu´mero de
mulheres, cada homen interessado em algumas das mulheres. Sob que condic¸o˜es e´ poss´ıvel
para todos os homens e mulheres se casarem, de tal forma que cada casamento acontece entre
um homem e uma mulher na qual ele esteja interessado?
1
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Conjunto Independente de Vértices, Clique e 
Cobertura de Vértices
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Conjunto Independente de Vértices
• Seja um grafo G= (V, E):
– Um conjunto independente de vértices VIND de G é um 
subconjunto de V em que não existe nenhuma aresta entre
qualquer par de elementos de VIND.
• Seja um grafo G= (V, E):
– Um conjunto independente de vértices VIND de G é um 
subconjunto de V em que não existe nenhuma aresta entre
qualquer par de elementos de VIND.
Grafo G Conjunto Independente de G
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Conjunto Independente de Vértices
• VIND é máximo se não existe um VIND’ tal que |VIND’| > |VIND|.
• VIND é maximal se não existe um VIND’ tal que VIND’ Š VIND.
• O conjunto independente do exemplo abaixo é máximo? É 
maximal?
• VIND é máximo se não existe um VIND’ tal que |VIND’| > |VIND|.
• VIND é maximal se não existe um VIND’ tal que VIND’ Š VIND.
• O conjunto independente do exemplo abaixo é máximo? É 
maximal?
Grafo G Conjunto Independente de G
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Conjunto Independente de Vértice
Exercício 1:
• Encontre no grafo abaixo um Conjunto Independente Maximal 
que não é máximo. Qual a cardinalidade do Conjunto
Independente máximo?
Exercício 1:
• Encontre no grafo abaixo um Conjunto Independente Maximal 
que não é máximo. Qual a cardinalidade do Conjunto
Independente máximo?
A B C D
E F G H
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Conjunto Independente de Vértice
Exercício 2:
• Considere o algoritmo abaixo. Ele resolve o problema do 
conjunto independente máximo?
Exercício 2:
• Considere o algoritmo abaixo. Ele resolve o problema do 
conjunto independente máximo?
CINDMax1(G)
CINDł ‡
while �v  V-CIND | CIND ‰ {v} é independente do
CINDł CIND ‰ {v}
return CIND
Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG
Conjunto Independente de Vértice
Exercício 3:
• Considere o algoritmo abaixo. Ele resolve o problema do 
conjunto independente máximo?
Exercício 3:
• Considere o algoritmo abaixo. Ele resolve o problema do 
conjunto independente máximo?
CINDMax2(G)
CINDł ‡
Y ł V
while Y z ‡ do
escolher v  V, com |N(v)| mínimo
CINDł CIND ‰ {v}
Y ł Y – {v}
Y ł Y – N(v)
return CIND
C:	
  Fazer	
  cópia	
  das	
  partituras	
  e	
  comprar	
  pastas	
   A	
   14	
  D:	
  provas	
   B,	
  C	
   3	
  E:	
  Ensaios	
   D	
   70	
  F:	
  Alugar	
  candelabros	
   D	
   14	
  G:	
  Decorar	
  candelabros	
   F	
   1	
  H:	
  Montar	
  as	
  decorações	
   D	
   1	
  I:	
  Providenciar	
  túnicas	
  para	
  os	
  cantores	
   D	
   7	
  J:	
  Providenciar	
  o	
  sistema	
  de	
  comunicação	
  com	
  o	
  público	
   D	
   7	
  K:	
  Selecionartrilhas	
  musicais	
   J	
   14	
  L:	
  Montar	
  o	
  sistema	
  de	
  comunicação	
  com	
  o	
  público	
   K	
   1	
  M:	
  Ensaio	
  Final	
   E,	
  G,	
  L	
   1	
  N:	
  Festa	
  com	
  apresentação	
  do	
  coral	
   H,	
  L,	
  M	
   1	
  O:	
  Programa	
  final	
   I,	
  N	
   1	
  	
  5)	
  Existe	
  algum	
  grafo	
  euleriano	
  com	
  n	
  par	
  e	
  m	
  ímpar?	
  Em	
  caso	
  positivo,	
  descreva-­‐o.	
  Caso	
  contrário,	
  justifique	
  a	
  não	
  existência.	
  	
  6)	
  Se	
  G	
  é	
  um	
  grafo	
  euleriano	
  com	
  arestas	
  e1	
  e	
  e2	
  que	
  têm	
  um	
  vértice	
  em	
  comum,	
  então	
  G	
  tem	
  um	
  circuito	
  euleriano	
  no	
  qual	
  e1	
  e	
  e2	
  aparecem	
  consecutivamente?	
  Prove,	
  se	
  for	
  verdadeiro.	
  Caso	
  contrário,	
  justifique.	
  	
  7)	
  Se G possui vértices v1, v2, . . . , vn, a sequência (d(v1), d(v2), . . . , d(vn)) é 
denominada sequência de ���graus de G. 
 
(i) Existe um multigrafo com a seguinte sequência de graus: 3,3,3,3,5,6,6,6,6? 
(ii) Existe um multigrafo com a seguinte sequência de graus: 
1,1,3,3,3,3,5,6,8,9? 
���(iii) Existe um grafo (simples) com a sequência de graus do ítem anterior? 
(iv) Demonstre que a sequência (d1,d2,...,dn) de inteiros não negativos é uma 
sequência de graus de algum multigrafo se e somente se a soma de termos da 
sequência é par. 
8) Classifique cada uma das afirmações abaixo como Verdadeira ou Falsa, 
justificando convenientemente sua resposta: ��� 
 (i) Se G e H são grafos isomorfos entãoo eles têm o mesmo número de vértices e o 
mesmo número de arestas. 
 (ii) Se G e H têm o mesmo número de vértices e o mesmo número de arestas então 
eles são isomorfos. 
 (iii) Se G e H são grafos isomorfos então eles têm a mesma sequência de graus. 
 (iv) Se G e H têm a mesma sequência de graus então eles são isomorfos.