TEMA_1 2_-_ARA0175_-_CLASSES_DE_GRAFOS

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 1.2 – CARACTERÍSTICAS E CLASSES DE 
GRAFOS
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
CARACTERÍSTICAS DOS GRAFOS
Grafos – Graus (Aula anterior...)
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 3
O grau (ou valência) de um vértice de um grafo é o número 
de arestas incidentes para com o vértice, com os laços contados 
duas vezes. De forma análoga, o número de vértices adjacentes a 
ele.
O grau de um vértice 𝑣 é denotado por deg(𝑣). 
Grafos – Graus (Aula anterior...)
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 4
O grau máximo de um grafo 𝐺 é 
denotado por Δ(𝐺), e o grau mínimo de 
um grafo, denotado por 𝛿 𝐺 .
São os graus máximos e mínimos de 
seus vértices. 
2
3
1
4
Grafos – Graus (Aula anterior...)
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 5
O grau máximo de um grafo 𝐺 é 
denotado por Δ(𝐺), e o grau mínimo de 
um grafo, denotado por 𝛿 𝐺 .
São os graus máximos e mínimos de 
seus vértices. 
2
3
1
4
Δ 𝐺 = 3
Grafos – Graus (Aula anterior...)
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 6
O grau máximo de um grafo 𝐺 é 
denotado por Δ(𝐺), e o grau mínimo de 
um grafo, denotado por 𝛿 𝐺 .
São os graus máximos e mínimos de 
seus vértices. 
2
3
1
4
𝛿 𝐺 = 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 7
Definição 1. Um grafo 𝐺 é dito regular se todos vértices em 𝐺 possuem o 
mesmo grau.
Característica em Grafos: 𝑘-regular
2-regular 1-regular
3-regular
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 8
Definição 1. Um grafo 𝐺 é dito regular se todos vértices em 𝐺 possuem o 
mesmo grau.
Característica em Grafos: 𝑘-regular
Um grafo 𝐺 é 𝑘-regular se 𝑑(𝑣) = 𝑘, ∀ 𝑣 ∈ 𝑉 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 9
Definição 2. Um grafo 𝐺 é dito completo se todo vértice em 𝐺 está conectado 
a qualquer outro vértice em 𝐺.
Característica em Grafos: Grafo Completo 
𝐾1
𝐾2 𝐾3 𝐾4
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 10
Definição 2. Um grafo 𝐺 é dito completo se todo vértice em 𝐺 está conectado 
a qualquer outro vértice em 𝐺.
Característica em Grafos: Grafo Completo 
- Um grafo completo com 𝑛 vértices é denotado por 𝐾𝑛
- Quantas arestas tem um grafo 𝐾𝑛?
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 11
Definição 3. Um grafo 𝐺 é um grafo ciclo que consiste de um único ciclo, ou 
em outras palavras, um número de vértices é conectados em uma rede 
fechada.
Característica em Grafos: Grafo Ciclo 
O grafo ciclo com 𝑛 vértices é 
chamado 𝐶𝑛.
𝐶4
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 12
Definição 3. Um grafo 𝐺 é um grafo ciclo que consiste de um único ciclo, ou 
em outras palavras, um número de vértices é conectados em uma rede 
fechada.
Característica em Grafos: Grafo Ciclo 
O número de vértices em um 𝐶𝑛 se iguala 
ao número de arestas, e cada vértice 
tem grau 2; isto é, cada vértice tem 
exatamente duas arestas incidentes a ele.
𝐶4
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 13
Definição 3. Um grafo 𝐺 é um grafo ciclo que consiste de um único ciclo, ou 
em outras palavras, um número de vértices é conectados em uma rede 
fechada.
Característica em Grafos: Grafo Ciclo 
Um ciclo com um número par de 
vértices é chamado de ciclo par. 
𝐶4
Um ciclo com um número ímpar de 
vértices é chamado de ciclo ímpar.
𝐶5
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 14
Definição 4. Um grafo 𝐺 é um caminho sem arcos repetidos, ou seja, um 
passeio em que os arcos são todos diferentes entre si.
Característica em Grafos: Grafo Caminho 
𝑃4
𝑃3
O grafo caminho com 𝑛 vértices é 
denotado por 𝑃𝑛 e possui 𝑛 − 1 
arestas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 15
Definição 4. Um grafo 𝐺 é um caminho sem arcos repetidos, ou seja, um 
passeio em que os arcos são todos diferentes entre si.
Característica em Grafos: Grafo Caminho 
𝑃4
𝑣1
𝑣2
𝑣3
𝑣4
A sequência 𝑣1, … , 𝑣𝑘 , ∀ 𝑣1, … , 𝑣𝑘 ∈ 𝑉, é um passeio de 𝑣1 
a 𝑣𝑘 , se (𝑣𝑗 , 𝑣𝑗+1) ∈ 𝐸, 1 ≤ 𝑗 ≤ |𝑘 – 1|
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 16
Definição 5. Um grafo 𝐻(𝑉′ , 𝐸′) é um subgrafo de um grafo 𝐺(𝑉, 𝐸) se todos 
os vértices e todas as arestas de 𝐻 pertencem a 𝐺 (isto é, 𝑉’ ⊆ 𝑉, 𝐴′ ⊆ 𝐴), e 
cada aresta de 𝐻 possui as mesmas extremidades que em 𝐺.
Característica em Grafos: Subgrafos 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 17
Definição 5. Um grafo 𝐻(𝑉′ , 𝐸′) é um subgrafo de um grafo 𝐺(𝑉, 𝐸) se todos 
os vértices e todas as arestas de 𝐻 pertencem a 𝐺 (isto é, 𝑉’ ⊆ 𝑉, 𝐴′ ⊆ 𝐴), e 
cada aresta de 𝐻 possui as mesmas extremidades que em 𝐺.
Característica em Grafos: Subgrafos 
𝐺 Subgrafos de 𝐺
a b
c
d
e
d
c d
b
e
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 18
Definição 5. Um grafo 𝐻(𝑉′ , 𝐸′) é um subgrafo de um grafo 𝐺(𝑉, 𝐸) se todos 
os vértices e todas as arestas de 𝐻 pertencem a 𝐺 (isto é, 𝑉’ ⊆ 𝑉, 𝐴′ ⊆ 𝐴), e 
cada aresta de 𝐻 possui as mesmas extremidades que em 𝐺.
Característica em Grafos: Subgrafos 
Propriedade de Subgrafos:
• Todo grafo é um subgrafo de si próprio. 
• Um subgrafo de um subgrafo de um grafo 𝐺 também é um subgrafo de 𝐺. 
• Um vértice de um grafo 𝐺 é um subgrafo de 𝐺. 
• Uma aresta (e os vértices aos quais ela é incidente) de um grafo 𝐺 é um 
subgrafo de 𝐺. 
• Se 𝐻 é subgrafo de 𝐺, então 𝐺 é um super grafo de 𝐻.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 19
Característica em Grafos: Subgrafos 
Características de Subgrafos:
1. Um subgrafo de um grafo 𝐺 é gerador se contém todos os vértices de 𝐺.
𝐺
a b
c d
a b
c d
É subgrafo 
gerador de 𝐺
a
c d
É subgrafo de 𝐺, 
mas não é gerador.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 20
Característica em Grafos: Subgrafos 
Características de Subgrafos:
2. Um subgrafo de um grafo 𝐺 é induzido se toda aresta de 𝐺 que tem ambas as pontas 
em 𝐻 também é aresta de 𝐻.
𝐺
a b
c d
a
c d
É subgrafo 
induzido de 𝐺
a
c d
É subgrafo de 𝐺, 
mas não é induzido.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 21
Característica em Grafos: Subgrafos 
Características de Subgrafos:
2. Um subgrafo de um grafo 𝐺 é induzido se toda aresta de 𝐺 que tem ambas as pontas 
em 𝐻 também é aresta de 𝐻.
𝐺
É subgrafo 
induzido de 𝐺?
É subgrafo 
induzido de 𝐺?
a b
c d
e
a
c
e
b
d
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 22
Característica em Grafos: Isomorfismo 
Definição 6. Dois grafos 𝐺 e 𝐺′ são isomorfos se eles apresentam as mesmas 
propriedades estruturais, obedecendo a seguinte função bijetora:
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 23
Característica em Grafos: Isomorfismo 
Definição 6. Dois grafos 𝐺 e 𝐺′ são isomorfos se eles apresentam as mesmas 
propriedades estruturais, obedecendo a seguinte função bijetora:
𝐺 𝐺′ 
Os grafos 𝑮 e 𝑮′ são isomorfos ?
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 24
Característica em Grafos: Isomorfismo 
Definição 6. Dois grafos 𝐺 e 𝐺′ são isomorfos se eles apresentam as mesmas 
propriedades estruturais, obedecendo a seguinte função bijetora:
𝐺 𝐺′ 
SimOs grafos 𝑮 e 𝑮′ são isomorfos ?
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
CLASSES DOS GRAFOS
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 26
Um grafo bipartido é um grafo cujos vértices podem ser divididos em 
dois conjuntos disjuntos 𝑈 e 𝑉 tal que toda aresta conecta um vértice 
em 𝑈 a um vértice em 𝑉.
Classes em Grafos – Grafos Bipartidos
𝑈
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 27
Um grafo bipartido é um grafo cujos vértices podem ser divididos em 
dois conjuntos disjuntos 𝑈 e 𝑉 tal que toda aresta conecta um vértice 
em 𝑈 a um vértice em 𝑉.
Classes em Grafos – Grafos Bipartidos
𝑉
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 28
Classes em Grafos – Grafos Bipartidos
𝑮[𝑽, 𝑼] – Denota em grafo bipartido, onde 𝑉 é o conjuntos de 
vértices de uma partição e 𝑈 é o conjunto de vértices de outra 
partição.
Um grafo bipartido é um grafo cujos vértices podemser divididos em 
dois conjuntos disjuntos 𝑈 e 𝑉 tal que toda aresta conecta um vértice em 𝑈 a 
um vértice em 𝑉.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 29
Um grafo bipartido é um grafo cujos vértices podem ser divididos em 
dois conjuntos disjuntos 𝑈 e 𝑉 tal que toda aresta conecta um vértice em 𝑈 a 
um vértice em 𝑉.
Classes em Grafos – Grafos Bipartidos
𝑮 𝑽, 𝑼 = 𝑮[𝟒, 𝟓] 
𝑮 𝑽, 𝑼 = 𝑮[𝟒, 𝟓] 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 30
Classes em Grafos – Grafos Bipartido Completo
Um grafo bipartido completo é um grafo onde cada vértice do primeiro 
conjunto 𝑈 está associado a cada vértice do segundo conjunto 𝑉.
Grafo bipartido completo – Wikipédia, a enciclopédia livre 
(wikipedia.org)
https://pt.wikipedia.org/wiki/Grafo_bipartido_completo
https://pt.wikipedia.org/wiki/Grafo_bipartido_completo
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 31
Classes em Grafos – Grafos Bipartido Completo
O grafo bipartido completo com partições de tamanho |𝑉1| = 𝑚 e |𝑉2| = 𝑛, é 
denotado 𝐾𝑚,𝑛.
𝐾3,4𝐾4,4
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 32
Classes em Grafos – Grafos Bipartido Completo
Um grafo bipartido completo 𝐺 ∶= (𝑉1 + 𝑉2, 𝐸), é um grafo bipartido tal 
que para quaisquer dois vértices, 𝑣1 ∈ 𝑉1 e 𝑣2 ∈ 𝑉2, 𝑣1𝑣2 é uma aresta 
em 𝐺. 
O grafo bipartido completo com partições de tamanho |𝑉1| = 𝑚 e |𝑉2| = 𝑛, é 
denotado 𝐾𝑚,𝑛.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 33
Classes em Grafos – Grafos Bipartido Completo
O grafo bipartido completo com partições de tamanho |𝑉1| = 𝑚 e |𝑉2| = 𝑛, é 
denotado 𝐾𝑚,𝑛. Alguns casos especiais:
Para qualquer k, K1,k é chamado grafos estrelas.
𝐾1,2 𝐾1,3 𝐾1,4 𝐾1,5 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 34
Classes em Grafos – Grafos Bipartido Completo
O grafo bipartido completo com partições de tamanho |𝑉1| = 𝑚 e |𝑉2| = 𝑛, é 
denotado 𝐾𝑚,𝑛. Alguns casos especiais:
O grafo K1,3 é chamado de grafo garra.
𝐾1,3 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 35
Classes em Grafos – Grafos Bipartido Completo
O grafo bipartido completo com partições de tamanho |𝑉1| = 𝑚 e |𝑉2| = 𝑛, é 
denotado 𝐾𝑚,𝑛. Alguns casos especiais:
O grafo K3,3 é chamado de grafo utilidade.
𝐾3,3 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 36
Classes em Grafos – Grafos Bipartido Completo
Propriedades dos grafo bipartidos:
• Um grafo é bipartido se e somente se ele não contém um ciclo ímpar.
• Um grafo é bipartido se e somente se ele é 2-colorível.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 37
Um grafo árvore é um grafo conexo e 
sem ciclos.
Classes em Grafos – Grafos Árvores
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 38
Classes em Grafos – Grafos Árvores
Seja 𝐺(𝑉, 𝐴) um grafo com ordem 𝑛 ≥ 2. As propriedades seguintes são 
equivalentes e suficientes para caracterizar 𝐺 como uma árvore:
1. 𝐺 é conexo e sem ciclos;
2. 𝐺 é sem ciclos e tem 𝑛 − 1 arestas;
3. 𝐺 é conexo e tem 𝑛 − 1 arestas;
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 39
Classes em Grafos – Grafos Árvores
Seja 𝐺(𝑉, 𝐴) um grafo com ordem 𝑛 ≥ 2. As propriedades seguintes são 
equivalentes e suficientes para caracterizar 𝐺 como uma árvore:
4. 𝐺 é sem ciclos e por adição de uma aresta se cria um ciclo e somente 
um;
5. 𝐺 é conexo, mas deixa de sê-lo se uma aresta é suprimida (todas as 
arestas são pontes);
6. todo par de vértices de 𝐺 é unido por uma e somente uma cadeia 
simples.
7. Um grafo 𝐺 é uma árvore se e somente se existir um único caminho 
entre cada par de vértices de 𝐺.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 40
Um grafo floresta é um grafo cuja as suas componentes são 
árvores.
Classes em Grafos – Grafos Árvores
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 41
Exercícios em Grafos
1. Quantos subgrafos com pelo menos um vértice tem 𝐾3?
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 42
1. Quantos subgrafos com pelo menos um vértice tem 𝐾3?
Exercícios em Grafos
Resposta: 
 São os subgrafos com um, dois e três vértices. Temos, então, três casos:
a) Um vértice: existem três subgrafos com um vértice e, consequentemente, 
nenhuma aresta.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 43
1. Quantos subgrafos com pelo menos um vértice tem 𝐾3?
Exercícios em Grafos
Resposta: 
 b) Dois vértices: existem 𝐶(3, 2) = 3 
possibilidades de escolher subgrafos 
com dois vértices (de um conjunto com 
três vértices, devemos escolher dois). 
Para cada possibilidade, podemos incluir 
ou não a aresta, i.e., 3 × 2 = 6 subgrafos 
com dois vértices;
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 44
1. Quantos subgrafos com pelo menos um vértice tem 𝐾3?
Exercícios em Grafos
Resposta: 
 c) Três vértices: neste caso, para uma das três 
arestas que podemos ter, podemos incluí-la ou 
não, ou seja, para cada aresta temos duas 
possibilidades. Assim, temos 2×2×2 = 8 
possibilidades. Uma outra forma de analisarmos 
este caso é que temos um conjunto 𝐸 com três 
arestas. O conjunto potência de 𝐸 nos dá todos os 
subconjuntos de aresta que podemos escolher. 
Assim, temos 23 = 8 possibilidades de 
subconjuntos distintos. 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 45
Exercícios em Grafos
2. Quantos vértices tem um grafo regular de grau 4 com 10 arestas?
3. Um grafo possui oito vértices e seis arestas? Esse grafo é conexo? 
Justifique a resposta. 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 46
Dúvidas?
	Slide 1: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 2: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 3: Grafos – Graus (Aula anterior...)
	Slide 4: Grafos – Graus (Aula anterior...)
	Slide 5: Grafos – Graus (Aula anterior...)
	Slide 6: Grafos – Graus (Aula anterior...)
	Slide 7: Característica em Grafos: k-regular
	Slide 8: Característica em Grafos: k-regular
	Slide 9: Característica em Grafos: Grafo Completo 
	Slide 10: Característica em Grafos: Grafo Completo 
	Slide 11: Característica em Grafos: Grafo Ciclo 
	Slide 12: Característica em Grafos: Grafo Ciclo 
	Slide 13: Característica em Grafos: Grafo Ciclo 
	Slide 14: Característica em Grafos: Grafo Caminho 
	Slide 15: Característica em Grafos: Grafo Caminho 
	Slide 16: Característica em Grafos: Subgrafos 
	Slide 17: Característica em Grafos: Subgrafos 
	Slide 18: Característica em Grafos: Subgrafos 
	Slide 19: Característica em Grafos: Subgrafos 
	Slide 20: Característica em Grafos: Subgrafos 
	Slide 21: Característica em Grafos: Subgrafos 
	Slide 22: Característica em Grafos: Isomorfismo 
	Slide 23: Característica em Grafos: Isomorfismo 
	Slide 24: Característica em Grafos: Isomorfismo 
	Slide 25: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 26: Classes em Grafos – Grafos Bipartidos
	Slide 27: Classes em Grafos – Grafos Bipartidos
	Slide 28: Classes em Grafos – Grafos Bipartidos
	Slide 29: Classes em Grafos – Grafos Bipartidos
	Slide 30: Classes em Grafos – Grafos Bipartido Completo
	Slide 31: Classes em Grafos – Grafos Bipartido Completo
	Slide 32: Classes em Grafos – Grafos Bipartido Completo
	Slide 33: Classes em Grafos – Grafos Bipartido Completo
	Slide 34: Classes em Grafos – Grafos Bipartido Completo
	Slide 35: Classes em Grafos – Grafos Bipartido Completo
	Slide 36: Classes em Grafos – Grafos Bipartido Completo
	Slide 37: Classes em Grafos – Grafos Árvores
	Slide 38: Classes em Grafos – Grafos Árvores
	Slide 39: Classes em Grafos – Grafos Árvores
	Slide 40: Classes em Grafos – Grafos Árvores
	Slide 41: Exercícios em Grafos
	Slide 42: Exercícios em Grafos
	Slide 43: Exercícios em Grafos
	Slide 44: Exercícios em Grafos
	Slide 45: Exercícios em Grafos
	Slide 46