grafosarvores

Prévia do material em texto

Matemática Discreta
Aula 07 – Grafos e Árvores
Profa Carlota
2
Um grafo é um modelo matemático para
representar uma coleção de objetos (nós ou
vértices – pontos ou círculos) que são ligados aos
pares (por arcos ou arestas – linhas ou setas)
com outra coleção de objetos.
As posições dos vértices e a forma das linhas são
irrelevantes – apenas representa quem está
ligado a quem.
Grafos não direcionadosGrafos direcionados (orientados)
3
Podem representar, por exemplo:
- Rotas de uma companhia aérea (cidades/rotas)
4
- Agendamento de tarefas (diagrama de PERT)
Por este grafo, podemos verificar que a tarefa A,
que demora 3 horas para concluir, deve ser
executada antes das tarefas C, D e F.
5
- Malha rodoviária (cidades/estradas)
Este grafo é:
Rotulado (nome de cidades)
Ponderado (distâncias)
Direcionado (setas: da origem para o destino)
Terminologia
1 e 3 são vértices adjacentes, mas 1 e 4 não são. 
5 é vértice isolado (tem grau 0 – não possui arestas).
Vértices 1 e 3 têm grau 3. O vértice 2 tem grau 5. 
As arestas 𝑎1 e 𝑎2 são paralelas. 
A aresta 𝑎3 é um laço. 
𝑎1
𝑎2
𝑎3
𝑎4
𝑎6𝑎51
2
3 4 5
Terminologia (continuação)
Grafo simples – não tem laços nem arestas paralelas.
Grafo completo – todos os vértices distintos são
adjacentes.
Este grafo é simples e completo
e é subgrafo de
𝑎1
𝑎2
𝑎3
𝑎4
𝑎6𝑎51
2
3 4 5
𝑎1
𝑎4
𝑎51
2
3
Terminologia (continuação)
Neste grafo, a sequência 2, 𝑎1, 1, 𝑎2, 2, 𝑎4, 3, 𝑎6, 4 é
um caminho do vértice 2 ao vértice 4, de
comprimento 4 (quantidade de arestas utilizadas).
Um grafo é conexo se houver um caminho entre
quaisquer dois vértices. Logo, o grafo acima não é
conexo (devido ao 5). 8
𝑎1
𝑎2
a3
𝑎4
𝑎6𝑎51
2
3 4 5
Terminologia (continuação)
Um ciclo em um grafo é um caminho de algum
vértice 𝑛0 até 𝑛0 de forma que nenhum vértice
(diferente de 𝑛0) ocorra mais de uma vez no caminho.
Exemplo: No grafo abaixo, 1, 𝑎1, 2, 𝑎4, 3, 𝑎5, 1 é um
ciclo.
𝑎1
𝑎2
𝑎3
𝑎4
𝑎6𝑎51
2
3 4 5
10
Uma árvore é um grafo não orientado conexo que não
possui nenhum ciclo.
G1 e G2 são árvores, pois são grafos conexos sem ciclos.
G3 não é uma árvore, pois e, b, a, d, e é um ciclo.
G4 não é uma árvore, pois não é conexo.
G1 G2
G3 G4
10
Exercício 1 Quais destes grafos são árvores?
12
Matriz de Adjacência de um grafo
1 2 3 4 5
1 0 2 1 0 0
2 2 1 1 0 0
3 1 1 0 1 0
4 0 0 1 0 0
5 0 0 0 0 0
Quantidade 
de arestas
do nó 1 ao 2.
𝑎1
𝑎2
𝑎3
𝑎4
𝑎6𝑎51
2
3 4 5
13
Lista de Adjacências de um grafo
Vértices
Lista de 
Adjacências 
1 2, 2, 3
2 1, 1, 2, 3
3 1, 2, 4
4 3
5
𝑎1
𝑎2
𝑎3
𝑎4
𝑎6𝑎51
2
3 4 5
14
Matriz e lista de adjacência de um grafo orientado
1 2 3
1 1 1 0
2 0 1 1
3 1 0 1
Vértices
Lista de 
Adjacências 
1 1, 2
2 2, 3
3 1, 3
Exercício 2 Escreva a lista e a matriz de adjacência
do grafo que represente a rede de contatos abaixo.
c)
16
Exercício 3 Escreva a lista e a matriz de
adjacência dos grafos.
a) 
b) 
d) 
e)
Exercício 4 Desenhe o grafo representado pela matriz.
c) 
0 2 0
2 0 2
0 2 0
 
 
 
  
d) 
0 1 0 0 0 0
1 0 1 0 0 0
0 1 1 1 0 0
0 0 1 0 0 0
0 0 0 0 2 0
0 0 0 0 0 2
 
 
 
 
 
 
 
 
 
a)
0 1 1 1 0
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
0 1 1 1 0
 
 
 
 
 
 
  
b)
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
 
 
 
 
 
 
  
Os grafos abaixo são isomorfos entre si.
Assim como os dois grafos abaixo.
Associação 
(Isomorfismo)
1 → 𝑎
2 → 𝑐
3 → 𝑏
4 → 𝑑
𝑎1 → 𝑒2
𝑎2 → 𝑒1
3
2
1
4
5
3
2
1
4
5
3
1
2
4
c d
a b
Exercício 5 Os grafos abaixo são isomorfos.
Escreva um isomorfismo dos grafos.
1
54
6
32
a
c
b
fe
d
19
Exercício 6 Os grafos abaixo são isomorfos.
Escreva um isomorfismo.
a
dc
e
b
1
43
5
2
20
Exercício 7 A Figura abaixo mostra os grafos
simples completos com 1, 2, 3 e 4 vértices (imagine
todos dando um abraço em todos). Estes grafos são
denotados por 𝐾𝑛 . Desenhe 𝐾5 . Quantas arestas ele
possui?
𝐾3𝐾2 𝐾4𝐾1
22
Um grafo é planar se ele pode ser desenhado em
um plano, de forma que suas arestas se interceptem
apenas em vértices (não podem ser cruzar).
Exemplo:
O grafo
é planar porque é isomorfo ao grafo
1
2 3
4
1
3 4
2
Como verificar que um grafo é planar ou não?
Sendo:
v = número de vértices
a = número de arestas
o grafo é planar se
𝑎 ≤ 3𝑣 − 6.
Exemplo:
𝑎 = 3 + 2 + 2 + 2 = 9
3𝑣 − 6 = 18 − 6 = 12
9 ≤ 12
⇒ 𝑎 ≤ 3𝑣 − 6.
Logo, é planar.
1 2 3
4 5 6
Grafo dual do mapa: Colocamos um vértice em cada região
do mapa e uma aresta entre dois vértices que representem
países adjacentes. O mapa dual será sempre simples, conexo e
planar.
Teorema das Quatro Cores: “Quatro cores são suficientes
para colorir qualquer mapa no plano.”
Inicialmente, criamos o grafo dual do mapa. Assim, o
enunciado do teorema é similar a: dois vértices adjacentes não
podem ter a mesma cor. 24
25
Exercício 8 Desenhe um grafo dual do mapa da figura
abaixo.
Exercício 10 𝐾4 e 𝐾5 são planares? Se sim,
desenhe os grafos planares correspondentes.
𝐾4 𝐾5
Exercício 9 O grafo abaixo é planar? Se sim,
desenhe o grafo planar correspondente.
Fórmula de Euler
Um grafo simples, conexo e planar divide o plano em um
número de regiões, incluindo as regiões totalmente
fechadas e uma região infinita exterior.
Sendo:
𝑣 = número de vértices
𝑎 = número de arestas
𝑟 = número de regiões
a relação entre eles neste tipo de grafos é
𝑣 − 𝑎 + 𝑟 = 2.
Exercício 11 Verifique a fórmula de Euler no grafo
abaixo.
Exercício 12 Construa um grafo simples, conexo e
planar com seis vértices, todos de grau 3. Desenhe o seu
grafo no quadro. Em quantas regiões ele divide o plano?
a
c
b
fe
d
Exercício 13 Seja um grafo simples conexo e
planar com 20 vértices, cada um com grau 3. Em quantas
regiões o plano é dividido em uma representação planar
desse grafo?
30
Referências
• LIPSCHUTZ, Seymour; LIPSON, Marc Lars. Matemática
Discreta. 3.ed. Porto Alegre: Bookman, 2013.
• MENEZES, Paulo Blauth. Matemática Discreta para
Computação e Informática. Col. Livros Didáticos, V.16.
Bookman, 2008.
• GERSTING, Judith L. Fundamentos Matemáticos para a
Ciência da Computação. Rio de Janeiro: LTC, 2004.
• MENEZES, Paulo Blauth et. al. Aprendendo Matemática
Discreta com Exercícios. Vol. 19. São Paulo: Artmed
Editora S.A., 2009.
• Rosen, Kenneth H. Matemática discreta e suas
aplicações. 6. ed. São Paulo: McGraw-Hill Interamericana
do Brasil Ltda. , 2009.
31
MENEZES, Paulo Blauth et. al. Aprendendo
Matemática Discreta com Exercícios. Vol. 19. São
Paulo: Artmed Editora S.A., 2009.
(https://integrada.minhabiblioteca.com.br/#/books/97
88577805105)
Rosen, Kenneth H. Matemática discreta e
suas aplicações. 6. ed. São Paulo: McGraw-
Hill Interamericana do Brasil Ltda. , 2009.
(https://integrada.minhabiblioteca.com.br/#/book
s/9788563308399)
https://integrada.minhabiblioteca.com.br/#/books/9788577805105
https://integrada.minhabiblioteca.com.br/#/books/9788563308399