parte 06 grafos.pdf

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

parte-06-grafos.pdf
EDUARDO 	
   F R E I R E 	
   NAKAMURA 	
  
I n s / t u t o 	
   d e 	
   C o m p u t a ç ã o 	
  
U n i v e r s i d a d e 	
   F e d e r a l 	
   d o 	
   A m a z o n a s 	
  
n a k a m u r a @ i c o m p . u f a m . e d u . b r 	
  
	
  
Grafos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
1	
  
1Este material baseia-se no capítulo 1 do livro: Vieira, N.J. Introdução aos Fundamentos da Computação: Linguagens e Máquinas, Pioneira 
Thomson Learning (atualmente, CENGAGE), 2006. 
Teoria	
  dos	
  grafos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
2	
  
—  Modelar	
  en2dades	
  e	
  seus	
  relacionamentos	
  
—  Ramo	
  específico	
  das	
  relações	
  binárias	
  
—  Aplicações	
  
u  Química	
  
u  Biologia	
  
u  Economia	
  
u  Engenharia	
  
u  Computação	
  
Exemplo	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Suponha	
  seis	
  cidades	
  
u  A,	
  B,	
  C,	
  D,	
  E,	
  F	
  
Com	
  as	
  estradas	
  
u  A-­‐B	
  	
  
u  A-­‐C	
  	
  
u  A-­‐D	
  
u  A-­‐E	
  
u  B-­‐C	
  
u  C-­‐E	
  
u  C-­‐D	
  
u  E-­‐F	
  
3	
  
Teoria	
  dos	
  grafos	
  
A	
   B	
  
C	
  
D	
  E	
  
F	
  
Vér2ce	
  
Vér2ce	
  
Exemplo	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Vér2ces	
  
u  A,	
  B,	
  C,	
  D,	
  E,	
  F	
  
Arestas	
  
u  A-­‐B	
  	
  
u  A-­‐C	
  	
  
u  A-­‐D	
  
u  A-­‐E	
  
4	
  
Teoria	
  dos	
  grafos	
  
A	
   B	
  
C	
  
D	
  E	
  
F	
  
u  B-­‐C	
  
u  C-­‐E	
  
u  C-­‐D	
  
u  E-­‐F	
  
Aresta	
  
Aresta	
  
Exemplo	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Vér2ces	
  
u  A,	
  B,	
  C,	
  D,	
  E,	
  F	
  
Arestas	
  
u  A-­‐B	
  	
  
u  A-­‐C	
  	
  
u  A-­‐D	
  
u  A-­‐E	
  
5	
  
Teoria	
  dos	
  grafos	
  
A	
   B	
  
C	
  
D	
  E	
  
F	
  
u  B-­‐C	
  
u  C-­‐E	
  
u  C-­‐D	
  
u  E-­‐F	
  
Grafo	
  G	
  =	
  (V,	
  E)	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Conjunto	
  V	
  de	
  Vér2ces	
  
u  Conjunto	
  de	
  en2dades	
  
u  V	
  =	
  {v1	
  ,…,	
  vn}	
  
Conjunto	
  E	
  de	
  Arestas	
  
u  Conjunto	
  de	
  relacionamentos	
  
u  E	
  =	
  {e1	
  ,…,	
  en}	
  
u  Pares	
  ordenados	
  ei=	
  〈va,	
  vb〉	
  	
  
6	
  
Conceitos	
  fundamentais	
  
A	
   B	
  
C	
  
D	
  E	
  
F	
  
Dígrafo	
  G	
  =	
  (V,	
  E)	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Conjunto	
  V	
  de	
  Vér2ces	
  
u  Conjunto	
  de	
  en2dades	
  
u  V	
  =	
  {v1	
  ,…,	
  vn}	
  
Conjunto	
  E	
  de	
  Arestas	
  
u  Conjunto	
  de	
  relacionamentos	
  
u  E	
  =	
  {e1	
  ,…,	
  en}	
  
u  Pares	
  ordenados	
  ei=	
  〈va,	
  vb〉	
  	
  
u  Ordem	
  é	
  discriminante	
  
7	
  
Grafo	
  direcionado	
  
A	
   B	
  
C	
  
D	
  E	
  
F	
  
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
8	
  
http://www.ostpreussen.net/ostpreussen/karten/galerie/images/osty11303-9499.jpg 
A	
   cidade	
   de	
   Königsberg	
   foi	
   construída	
   numa	
  
região	
   onde	
   havia	
   dois	
   braços	
   do	
   Rio	
   Pregel	
   e	
  
uma	
  ilha	
  
	
  	
  
Foram	
  construídas	
  sete	
  pontes	
  ligando	
  diferentes	
  
partes	
  da	
  cidade	
  
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
9	
  
http://media-2.web.britannica.com/eb-media/77/74877-004-6D15B0BD.jpg 
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
https://upload.wikimedia.org/wikipedia/commons/d/d7/Leonhard_Euler.jpg 
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
10	
  
http://media-2.web.britannica.com/eb-media/77/74877-004-6D15B0BD.jpg 
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
https://upload.wikimedia.org/wikipedia/commons/d/d7/Leonhard_Euler.jpg 
A
B C
D
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
11	
  
http://media-2.web.britannica.com/eb-media/77/74877-004-6D15B0BD.jpg 
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
https://upload.wikimedia.org/wikipedia/commons/d/d7/Leonhard_Euler.jpg 
A
B C
D
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
12	
  
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
https://upload.wikimedia.org/wikipedia/commons/d/d7/Leonhard_Euler.jpg 
A
B C
D
As	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
13	
  
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
Euler	
  reformulou	
  o	
  problema	
  
(1736)	
  
	
  
•  É	
   possível	
   achar	
   um	
   caminho	
  
que	
   comece	
   e	
   termine	
   num	
  
vér2ce	
  qualquer	
  (A,	
  B,	
  C,	
  ou	
  D)	
  
e	
   passe	
   por	
   cada	
   aresta,	
  
exatamente,	
  e	
  uma	
  única	
  vez?	
  
•  É	
  possível	
  desenhar	
  este	
  grafo	
  
que	
   comece	
   e	
   termine	
   na	
  
mesma	
  posição	
  sem	
  levantar	
  o	
  
lápis	
  do	
  papel?	
  
A
B C
D
Aplicações	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
14	
  
http://web.math.princeton.edu/math_alive/5/Lab1/caida2Sm.png 
Aplicações	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
15	
  
http://images.wisegeek.com/illustration-of-a-molecule.jpg 
Terminologia	
  	
   Grafo	
  
Eduardo Freire
Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
16	
  
Terminologia	
  em	
  grafos	
  
0	
   1	
  
2	
  3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Laço	
  
Aresta	
  da	
  forma	
  〈v, v〉	
  
17	
  
Terminologia	
  em	
  grafos	
  
0	
   1	
  
2	
  3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Vér/ces	
  adjacentes	
  
Vér2ces	
  de	
  uma	
  mesma	
  aresta	
  〈a, b〉	
  
18	
  
Terminologia	
  em	
  grafos	
  
0	
   1	
  
2	
  3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Extremidade	
  de	
  uma	
  aresta	
  
Um	
  vér2ce	
  da	
  aresta	
  
19	
  
Terminologia	
  em	
  grafos	
  
0	
   1	
  
2	
  3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Arestas	
  paralelas	
  
Arestas	
  com	
  as	
  mesmas	
  extremidades	
  
20	
  
Terminologia	
  em	
  grafos	
  
0	
  
3	
  
1	
  
2	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Vér/ce	
  isolado	
  
Vér2ce	
  que	
  não	
  é	
  adjacente	
  a	
  nenhum	
  
outro	
  vér2ce	
  
21	
  
Terminologia	
  em	
  grafos	
  
0	
  
3	
  
1	
  
2	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Grau	
  do	
  vér/ce	
  
Número	
  de	
  extremidades	
  de	
  arestas	
  no	
  
vér2ce	
  
22	
  
Terminologia	
  em	
  grafos	
  
0	
  
3	
  
1	
  
2	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Grau	
  do	
  vér/ce	
  
Número	
  de	
  extremidades	
  de	
  arestas	
  no	
  
vér2ce	
  
23	
  
Terminologia	
  em	
  grafos	
  
3	
  
1	
  
2	
  
0	
  
4	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Grau	
  do	
  vér/ce	
  
Número	
  de	
  extremidades	
  de	
  arestas	
  no	
  
vér2ce	
  
24	
  
Terminologia	
  em	
  grafos	
  
3	
  
1	
  
2	
  
0	
  
3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Grau	
  do	
  vér/ce	
  
Número	
  de	
  extremidades	
  de	
  arestas	
  no	
  
vér2ce	
  
25	
  
Terminologia	
  em	
  grafos	
  
3	
  
1	
  
2	
  
0	
  
3	
  
Terminologia	
  	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Grau	
  do	
  vér/ce	
  
Número	
  de	
  extremidades	
  de	
  arestas	
  no	
  
vér2ce	
  
26	
  
Terminologia	
  em	
  grafos	
  
3	
  
1	
  
2	
  
0	
  
0	
  
Função	
  aresta-­‐vér/ce	
   Grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Aresta	
   Vér/ce	
  
a	
  
b	
  
c	
  
d	
  
e	
  
f	
  
g	
  
{0,1}	
  
{0,1}	
  
{0,2}	
  
{1,2}	
  
{4,4}	
  
{4,5}	
  
{5,5}	
  
27	
  
Terminologia	
  em	
  grafos	
  
2	
  
1	
  
5	
  
0	
   4	
  
3	
  
a	
  
b	
  
c	
   d	
  
e	
  
f	
  
g	
  
Definição	
   Caracterís/cas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Caminho:	
  seq.	
  de	
  vér2ces	
  	
  arestas	
  
u  Comprimento:	
  #	
  de	
  arestas	
  
u  Caminho	
  gerador:	
  inclui	
  todos	
  vér2ces	
  
u  Trajeto:	
  caminho	
  sem	
  repe2r	
  arestas	
  
u  Circuito:	
  trajeto	
  fechado	
  
u  Ciclo:	
  trajeto	
  sem	
  repe2r	
  vér2ces*	
  
Grafo	
  	
  
u  Acíclico:	
  sem	
  ciclos	
  
u  Conexo:	
  todos	
  os	
  vér2ces	
  
alcansáveis	
  
Tipo	
  
Aresta	
  
repe/da
?	
  
Vér/ce	
  
repe/do
?	
  
Começa	
  e	
  
termina	
  
mesmo	
  vér/ce	
  
caminho	
   ✓ ✓ ✓ 
fechado	
   ✓ ✓ ✓✓ 
trajeto	
   ✗ ✓ ✓ 
circuito	
   ✗ ✓ ✓✓ 
ciclo	
   ✗ ✓✓ ✓✓ 
28	
  
Terminologia	
  em	
  grafos	
  
✓✓	
  :	
  sim,	
  ✓	
  :	
  pode,	
  ✗	
  :	
  não	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Tamanho	
  do	
  caminho	
  abcd?	
  
—  abcda?	
  
—  abcb?	
  
—  abcdae?	
  
—  aba?	
  
—  abcdaefga?	
  
—  abcda?	
  
29	
  
Terminologia	
  em	
  grafos	
  
g	
  f	
  
a	
  e	
   b	
  
c	
  d	
  
Comprimento:	
  #	
  de	
  arestas	
  
Caminho	
  gerador:	
  inclui	
  todos	
  vér2ces	
  
Trajeto:	
  caminho	
  sem	
  repe2r	
  arestas	
  
Circuito:	
  trajeto	
  fechado	
  
Ciclo:	
  trajeto	
  sem	
  repe2r	
  vér2ces*	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
30	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Grafo	
  simples	
  
Grafo	
  sem	
  laços	
  e	
  sem	
  arestas	
  paralelas	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
31	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Grafo	
  direcionado	
  
Grafo	
  com	
  arestas	
  direcionadas	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
32	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Grafo	
  valorado	
  
Grafo	
  cujas	
  arestas	
  possuem	
  um	
  valor	
  
associado	
  (peso)	
  
5	
  
10	
  
-­‐2	
   7	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
33	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Subgrafo	
  
Um	
  subconjunto	
  de	
  vér2ces	
  e	
  um	
  
subconjunto	
  de	
  arestas	
  do	
  grafo	
  original	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
34	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Subgrafo	
  
Um	
  subconjunto	
  de	
  vér2ces	
  e	
  um	
  
subconjunto	
  de	
  arestas	
  do	
  grafo	
  original	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
35	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Subgrafo	
  
Um	
  subconjunto	
  de	
  vér2ces	
  e	
  um	
  
subconjunto	
  de	
  arestas	
  do	
  grafo	
  original	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
36	
  
Tipos	
  de	
  grafos	
  
2	
  
1	
  0	
  
3	
  
Subgrafo	
  
Um	
  subconjunto	
  de	
  vér2ces	
  e	
  um	
  
subconjunto	
  de	
  arestas	
  do
grafo	
  original	
  
Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
37	
  
Tipos	
  de	
  grafos	
  
Grafo	
  completo	
  
Um	
  grafo	
  simples	
  de	
  n	
  vér2ces,	
  
denominado	
  Kn	
  ,	
  é	
  completo	
  se	
  todo	
  
vér2ce	
  é	
  adjacente	
  a	
  todos	
  os	
  outros.	
  	
  
	
  
O	
  número	
  de	
  arestas	
  em	
  Kn	
  é	
  C(n,2)	
  
(combinação	
  de	
  n,	
  dois	
  a	
  dois)	
  
Definição	
   K2	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
38	
  
Tipos	
  de	
  grafos	
  
Grafo	
  completo	
  
Um	
  grafo	
  simples	
  de	
  n	
  vér2ces,	
  
denominado	
  Kn	
  ,	
  é	
  completo	
  se	
  todo	
  
vér2ce	
  é	
  adjacente	
  a	
  todos	
  os	
  outros.	
  	
  
	
  
O	
  número	
  de	
  arestas	
  em	
  Kn	
  é	
  C(n,2)	
  
(combinação	
  de	
  n,	
  dois	
  a	
  dois)	
  
2	
  1	
  
Definição	
   K3	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
39	
  
Tipos	
  de	
  grafos	
  
Grafo	
  completo	
  
Um	
  grafo	
  simples	
  de	
  n	
  vér2ces,	
  
denominado	
  Kn	
  ,	
  é	
  completo	
  se	
  todo	
  
vér2ce	
  é	
  adjacente	
  a	
  todos	
  os	
  outros.	
  	
  
	
  
O	
  número	
  de	
  arestas	
  em	
  Kn	
  é	
  C(n,2)	
  
(combinação	
  de	
  n,	
  dois	
  a	
  dois)	
  
1	
  
3	
  2	
  
Definição	
   K4	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
40	
  
Tipos	
  de	
  grafos	
  
Grafo	
  completo	
  
Um	
  grafo	
  simples	
  de	
  n	
  vér2ces,	
  
denominado	
  Kn	
  ,	
  é	
  completo	
  se	
  todo	
  
vér2ce	
  é	
  adjacente	
  a	
  todos	
  os	
  outros.	
  	
  
	
  
O	
  número	
  de	
  arestas	
  em	
  Kn	
  é	
  C(n,2)	
  
(combinação	
  de	
  n,	
  dois	
  a	
  dois)	
  
2	
  1	
  
3	
  4	
  
Definição	
   K5	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
41	
  
Tipos	
  de	
  grafos	
  
Grafo	
  completo	
  
Um	
  grafo	
  simples	
  de	
  n	
  vér2ces,	
  
denominado	
  Kn	
  ,	
  é	
  completo	
  se	
  todo	
  
vér2ce	
  é	
  adjacente	
  a	
  todos	
  os	
  outros.	
  	
  
	
  
O	
  número	
  de	
  arestas	
  em	
  Kn	
  é	
  C(n,2)	
  
(combinação	
  de	
  n,	
  dois	
  a	
  dois)	
  
2	
  
1	
  
5	
  
3	
  4	
  
Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
42	
  
Tipos	
  de	
  grafos	
  
Grafo	
  bipar/do	
  completo	
  
Um	
  grafo	
  simples	
  com	
  m+n	
  vér2ces,	
  
denominado	
  Km,n	
  ,	
  é	
  bipar2do	
  completo	
  
se	
  os	
  vér2ces	
  podem	
  ser	
  divididos	
  em	
  
dois	
  conjuntos	
  disjuntos	
  não	
  vazios	
  V1	
  e	
  
V2	
  ,	
  tais	
  que	
  〈vi,	
  vj〉	
  é	
  uma	
  aresta	
  se,	
  e	
  
somente	
  se,	
  vi	
  ∈	
  V1	
  e	
  	
  vj	
  ∈	
  V2	
  
Definição	
   K2,3	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
43	
  
Tipos	
  de	
  grafos	
  
Grafo	
  bipar/do	
  completo	
  
Um	
  grafo	
  simples	
  com	
  m+n	
  vér2ces,	
  
denominado	
  Km,n	
  ,	
  é	
  bipar2do	
  completo	
  
se	
  os	
  vér2ces	
  podem	
  ser	
  divididos	
  em	
  
dois	
  conjuntos	
  disjuntos	
  não	
  vazios	
  V1	
  e	
  
V2	
  ,	
  tais	
  que	
  〈vi,	
  vj〉	
  é	
  uma	
  aresta	
  se,	
  e	
  
somente	
  se,	
  vi	
  ∈	
  V1	
  e	
  	
  vj	
  ∈	
  V2	
   2	
  
1	
  
5	
  
3	
  
4	
  
V1 
V2 
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
44	
  
1.  Desenhe	
  um	
  grafo	
  com	
  	
  
u  vér2ces	
  {1,	
  2,	
  3,	
  4,	
  5}	
  e	
  	
  
u  arestas:	
  e1=〈1,2〉,	
  	
  e2=〈1,3〉,	
  	
  e3=〈3,4〉,	
  	
  e4=〈3,4〉,	
  	
  e5=〈4,5〉,	
  	
  e6=〈5,5〉	
  
a)  Encontre	
  dois	
  nós	
  que	
  não	
  são	
  adjacentes	
  
b)  Encontre	
  duas	
  arestas	
  paralelas	
  
c)  Encontre	
  um	
  laço	
  
d)  Encontre	
  o	
  grau	
  do	
  nó	
  3	
  
e)  Encontre	
  um	
  caminho	
  de	
  comprimento	
  5	
  
f)  Encontre	
  um	
  ciclo	
  
g)  Esse	
  grafo	
  é	
  completo?	
  
h)  É	
  conexo?	
  
2.  Desenhe	
  os	
  grafos	
  K6	
  e	
  K3,4	
  
Caracterís2cas	
  de	
  um	
  grafo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
45	
  
Lema	
  do	
  aperto	
  de	
  mão	
  
•  Em	
  um	
  grafo,	
  a	
  soma	
  dos	
  graus	
  dos	
  vé2ces	
  é	
  igual	
  ao	
  dobro	
  do	
  número	
  de	
  arestas.	
  
•  Em	
  um	
  grafo,	
  o	
  número	
  de	
  vér2ces	
  de	
  grau	
  ímpar	
  é	
  par.	
  
c	
  a	
   b	
   d	
  
f	
  h	
   g	
   e	
  
Circuito	
  Euleriano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
46	
  
Circuito	
  Euleriano	
  
Dado	
  um	
  grafo	
  G,	
  um	
  circuito	
  Euleriano	
  é	
  um	
  circuito	
  que	
  
•  Contém	
  todos	
  os	
  vér2ces	
  de	
  e	
  todas	
  as	
  arestas	
  de	
  G	
  
•  É	
  uma	
  sequência	
  de	
  vér2ces	
  e	
  arestas	
  adjacentes	
  que	
  começa	
  e	
  termina	
  no	
  mesmo	
  
vér2ce,	
  passando	
  pelo	
  menos	
  uma	
  vez	
  por	
  cada	
  vér2ce	
  e	
  exatamente	
  uma	
  única	
  vez	
  
por	
  cada	
  aresta.	
  
a	
   b	
  
d	
   c	
  
a	
  
b	
  
d	
  
c	
  
e	
  
Circuito	
  Euleriano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
47	
  
Teorema	
  
Se	
  um	
  grafo	
  possui	
  um	
  circuito	
  Euleriano,	
  então	
  
cada	
  vér2ce	
  do	
  grafo	
  tem	
  grau	
  par.	
  
Revisitando	
  as	
  sete	
  pontes	
  de	
  Königsberg	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
48	
  
É	
  possível	
  que	
  uma	
  pessoa	
  faça	
  um	
  percurso	
  
na	
   cidade	
   de	
   tal	
   forma	
   que	
   inicie	
   e	
   volte	
   a	
  
mesma	
  posição	
  passando	
  por	
  todas	
  as	
  pontes	
  
somente	
  uma	
  única	
  vez?	
  
https://upload.wikimedia.org/wikipedia/commons/d/d7/Leonhard_Euler.jpg 
A
B C
D
Circuito	
  Euleriano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
49	
  
Se	
  cada	
  vér2ce	
  de	
  um	
  grafo	
  tem	
  grau	
  par,	
  então	
  o	
  grafo	
  tem	
  um	
  
circuito	
  Euleriano?	
  
a	
  
c	
  
b	
  
d	
  
Circuito	
  Euleriano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
50	
  
Teorema	
  
Se	
  cada	
  vér2ce	
  de	
  um	
  grafo	
  não	
  vazio	
  tem	
  grau	
  
par	
  e	
  o	
  grafo	
  é	
  conexo,	
  então	
  o	
  grafo	
  tem	
  um	
  
circuito	
  Euleriano.	
  
Circuito	
  Hamiltoniano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
51	
  
William	
  Hamilton	
  (1805-­‐1865),	
  
matemá2co	
  irlandês,	
  propôs	
  em	
  
1859
um	
  jogo	
  que	
  envolve	
  um	
  
dodecaedro.	
  
ht
tp
s:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Fi
le
:W
ill
ia
m
_R
ow
an
_H
am
ilt
on
_p
or
tr
ai
t_
ov
al
_c
om
bi
ne
d.
pn
g 
Cada	
  vér2ce	
  recebeu	
  o	
  nome	
  de	
  uma	
  
cidade:	
  Londres,	
  Paris,	
  Hong	
  Kong,	
  
New	
  York,	
  etc.	
  	
  
É	
  possível	
  começar	
  em	
  uma	
  cidade	
  e	
  visitar	
  todas	
  as	
  outras	
  cidades	
  	
  
exatamente	
  uma	
  única	
  vez	
  e	
  retornar	
  à	
  cidade	
  de	
  par2da? 
Circuito	
  Hamiltoniano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
52	
  
É	
  possível	
  começar	
  em	
  uma	
  cidade	
  e	
  visitar	
  todas	
  as	
  outras	
  cidades	
  	
  
exatamente	
  uma	
  única	
  vez	
  e	
  retornar	
  à	
  cidade	
  de	
  par2da? 
ht
tp
s:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Fi
le
:W
ill
ia
m
_R
ow
an
_H
am
ilt
on
_p
or
tr
ai
t_
ov
al
_c
om
bi
ne
d.
pn
g 
Circuito	
  Hamiltoniano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
53	
  
É	
  possível	
  começar	
  em	
  uma	
  cidade	
  e	
  visitar	
  todas	
  as	
  outras	
  cidades	
  	
  
exatamente	
  uma	
  única	
  vez	
  e	
  retornar	
  à	
  cidade	
  de	
  par2da? 
ht
tp
s:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Fi
le
:W
ill
ia
m
_R
ow
an
_H
am
ilt
on
_p
or
tr
ai
t_
ov
al
_c
om
bi
ne
d.
pn
g 
Circuito	
  Hamiltoniano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
54	
  
É	
  possível	
  começar	
  em	
  uma	
  cidade	
  e	
  visitar	
  todas	
  as	
  outras	
  cidades	
  	
  
exatamente	
  uma	
  única	
  vez	
  e	
  retornar	
  à	
  cidade	
  de	
  par2da? 
ht
tp
s:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Fi
le
:W
ill
ia
m
_R
ow
an
_H
am
ilt
on
_p
or
tr
ai
t_
ov
al
_c
om
bi
ne
d.
pn
g 
Circuito	
  Hamiltoniano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
55	
  
Circuito	
  Hamiltoniano	
  
Dado	
  um	
  grafo	
  G=(V,	
  E),	
  um	
  circuito	
  Hamiltoniano	
  para	
  G	
  é	
  
um	
  circuito	
  simples	
  que	
  inclui	
  todos	
  os	
  vér/ces	
  de	
  G.	
  
Quais	
  grafos	
  possuem	
  circuito	
  Hamiltoniano?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
56	
  
a	
   b	
  
d	
   c	
  
a	
  
b	
  
d	
  
c	
  
e	
  
a	
  
b	
  
d	
  
c	
  
h	
  
f	
  
e	
  g	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 57	
  
http://static.etrend.sk/uploads/tx_media/2013/01/16/lenivy_vyvojar_flickr.jpg 
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 58	
  
http://i.telegraph.co.uk/multimedia/archive/03237/brucedieh_3237639k.jpg 
Grafos	
  planares	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
59	
  
Grafos	
  planares	
  
Grafos	
  que	
  podem	
  ser	
  desenhados	
  no	
  plano,	
  de	
  
modo	
  que	
  suas	
  arestas	
  não	
  se	
  cruzam.	
  
a	
   b	
  
c	
   d	
  
a	
   b	
  
d	
   c	
  
Como	
  determinar	
  planaridade?	
   Exemplo:	
  K4	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Traçar	
  os	
  ciclos	
  longos	
  
—  Tentar	
  colocar	
  as	
  arestas	
  restantes	
  
—  Grafos	
  de	
  tamanho	
  moderado:	
  
usar	
  bom	
  senso	
  
60	
  
Grafos	
  planares	
  
1	
   2	
  
3	
   4	
  
1	
   2	
  
3	
   4	
  
✓	
  
Como	
  determinar	
  planaridade?	
   Exemplo:	
  K3,3	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Traçar	
  os	
  ciclos	
  longos	
  
—  Tentar	
  colocar	
  as	
  arestas	
  restantes	
  
—  Grafos	
  de	
  tamanho	
  moderado:	
  
usar	
  bom	
  senso	
  
61	
  
Grafos	
  planares	
  
1	
   3	
  
2	
   4	
  
5	
  
5	
  
2	
  
6	
  
3	
  
5	
  
✗
1	
   4	
  
Teorema	
   Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  G	
  =	
  (V,	
  E)	
  um	
  grafo	
  planar,	
  
conexo	
  e	
  simples	
  	
  
—  Se	
  a	
  representação	
  planar	
  de	
  G	
  	
  
1.  Divide	
  o	
  plano	
  em	
  F	
  regiões,	
  
então	
  
V	
  –	
  E	
  +	
  F	
  =	
  2	
  
2.  Se	
  V	
  ≥	
  3,	
  então	
  
E	
  ≤	
  	
  3V	
  –	
  6	
  
3.  Se	
  V	
  ≥	
  3	
  e	
  se	
  não	
  existem	
  ciclos	
  
de	
  comprimento	
  3,	
  então	
  	
  
E	
  ≤	
  	
  2V	
  –	
  4	
  
—  K5	
  é	
  planar?	
  
—  K3,3	
  é	
  planar?	
  
62	
  
Fórmula	
  de	
  Euler	
  
Grafos	
  isomorfos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
63	
  
a	
   b	
  
d	
   c	
  
E	
  
H	
  
G	
   F	
  
Grafos	
  isomorfos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
64	
  
Isomorfismo	
  de	
  grafos	
  
Critério	
  que	
  permite	
  saber	
  se	
  dois	
  grafos	
  (aparentemente)	
  dis2ntos	
  são	
  
o	
  mesmo	
  grafo.	
  
Grafos	
  isomorfos	
  
Dois	
  grafos	
  G1=(V1,E1)	
  e	
  G2=(V2,E2)	
  são	
  isomorfos	
  se	
  existe	
  uma	
  bijeção	
  	
  	
  
f	
  :	
  V1→V2,	
  tal	
  que	
  〈f(u),	
  f(v)〉	
  é	
  uma	
  aresta	
  de	
  G2	
  se,	
  e	
  somente	
  se,	
  〈u,	
  v〉	
  
for	
  uma	
  aresta	
  de	
  G1.	
  	
  
Grafos	
  isomorfos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
65	
  
a	
   b	
  
d	
   c	
  
E	
  
H	
  
G	
   F	
  
f	
  
a	
   E	
  
b	
   F	
  
c	
   H	
  
d	
   G	
  
Isomorfos?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
66	
  
a	
  
c	
  e	
  
f	
   b	
  
d	
  
W
U	
   V	
  
Z	
  
X	
  
Y	
  
f	
  
a	
   W	
  
b	
   X	
  
c	
   U	
  
d	
   Z	
  
e	
   V	
  
f	
   Y	
  
Isomorfos?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
67	
  
a	
   b	
  
f	
   e	
  
c	
  
d	
  
a	
  
b	
  
f	
  
e	
  
c	
  
d	
  
ciclo	
  de	
  
tamanho	
  3	
  
__MACOSX/._parte-06-grafos.pdf