Apresentação do Curso - dsc.ufcg.edu.brabrantes/CursosAnteriores/TG072/slidesTG072.pdf · As Pontes de Königsberg ... – Diminua o ritmo de apresentação dos slides, se for o

1

Teoria dos Grafos – 2007.2 © Jorge Figueiredo, DSC/UFCG

Teoria dos Grafos

Jorge Figueiredo

Visão Geral do CursoVisão Geral do Curso


Agenda

• Apresentação do curso• Introdução Informal• Motivação

• Apresentação do curso• Introdução Informal• Motivação


Apresentação do Curso

• Homepage (http://www.dsc.ufcg.edu.br/~abrantes/tg.html)• Lista de discussão ([email protected])• Pré-requisito:

– Teoria dos conjuntos– Programação

• Homepage (http://www.dsc.ufcg.edu.br/~abrantes/tg.html)• Lista de discussão ([email protected])• Pré-requisito:

– Teoria dos conjuntos– Programação


Apresentação do Curso

• Horário e Sala– Auditório Mário Hattori - DSC– S142

• Horário de dúvidas:– Sob demanda, com hora marcada.

• Horário e Sala– Auditório Mário Hattori - DSC– S142

• Horário de dúvidas:– Sob demanda, com hora marcada.


Avaliação

• Mini-provas (pelo menos 4 por nota parcial)• Reposição:

– Possível deixar 20% das mini-provas (por nota parcial)• Prova Final: 07/04/2008

• Mini-provas (pelo menos 4 por nota parcial)• Reposição:

– Possível deixar 20% das mini-provas (por nota parcial)• Prova Final: 07/04/2008


Bibliografia

• Grafos e Algoritmos Computacionais, de J.L. Szwarcfiter.• Fundamentos Matemáticos para a Computação, de J.L.

Gersting.• Introduction to Graph Theory, de R. J. Wilson.• Discrete Mathematics with Graph Theory, de E.G. Goodaire

e M.M. Parmenter.• Graph Theory, de R. Diestel. (versão eletrônica disponível)

• Grafos e Algoritmos Computacionais, de J.L. Szwarcfiter.• Fundamentos Matemáticos para a Computação, de J.L.

Gersting.• Introduction to Graph Theory, de R. J. Wilson.• Discrete Mathematics with Graph Theory, de E.G. Goodaire

e M.M. Parmenter.• Graph Theory, de R. Diestel. (versão eletrônica disponível)

2


Introdução Informal

• Por que estudar grafos?– Um grande número de problemas, nas mais diversas

áreas da Ciência da Computação, podem ser vistos comoproblemas de grafos.

• Em muitos casos, basta resolver a seguinte questão: como expressar o meu problema como um problemade grafos?

– Poderosa ferramenta matemática com soluções prontaspra uso.

• Por que estudar grafos?– Um grande número de problemas, nas mais diversas

áreas da Ciência da Computação, podem ser vistos comoproblemas de grafos.

• Em muitos casos, basta resolver a seguinte questão: como expressar o meu problema como um problemade grafos?

– Poderosa ferramenta matemática com soluções prontaspra uso.


O Que São Grafos?

• Ferramenta para resolver problemas. • Ferramenta de modelagem.• Estrutura de dados.• Ferramenta utilizada na abstração de problemas

computacionais.

• Ferramenta para resolver problemas. • Ferramenta de modelagem.• Estrutura de dados.• Ferramenta utilizada na abstração de problemas

computacionais.

Ferramenta fundamental para a ciência da computação.


As Pontes de Königsberg

•Resolvido em 1736 por Leonhard Euler.•Marco inicial da Teoria dos Grafos.•É possível sair de uma das ilhas, passar uma única vez emcada uma das pontes e retornar ao ponto de origem?

•Resolvido em 1736 por Leonhard Euler.•Marco inicial da Teoria dos Grafos.•É possível sair de uma das ilhas, passar uma única vez emcada uma das pontes e retornar ao ponto de origem?


As Pontes de Königsberg

• Necessário um modelo para representar o problema daspontes.

• Abstrair detalhes irrelevantes:– Área de cada ilha.– Formato de cada ilha.– Tipo da ponte, etc.

• Euler generalizou o problema a partir de um modelo de grafos.

• Necessário um modelo para representar o problema daspontes.

• Abstrair detalhes irrelevantes:– Área de cada ilha.– Formato de cada ilha.– Tipo da ponte, etc.

• Euler generalizou o problema a partir de um modelo de grafos.


O Problema das 3 Casas

• É possível conectar os 3 serviços em cada uma das casassem haver cruzamento de tubulação?

• É possível conectar os 3 serviços em cada uma das casassem haver cruzamento de tubulação?

A Teoria dos Grafos mostra que não é possível!!!


Coloração de Mapas

•Com quantas cores é possível colorir o mapa da RegiãoNordeste?

–Estados vizinhos não podem ter a mesma cor.

•Com quantas cores é possível colorir o mapa da RegiãoNordeste?

–Estados vizinhos não podem ter a mesma cor.

3


Coloração de Mapas

•O Teorema das 4 cores (1977) garante que com 4 cores épossível colorir qualquer mapa planar.•O Teorema das 4 cores (1977) garante que com 4 cores épossível colorir qualquer mapa planar.


Modelagem com Grafos

• Estamos interessados em entidades e as relações entreelas.

• Quem são elas nos problemas apresentados?• Como representar no modelo?

– Forma matemática.– Forma gráfica.

• Estamos interessados em entidades e as relações entreelas.

• Quem são elas nos problemas apresentados?• Como representar no modelo?

– Forma matemática.– Forma gráfica.



•A forma mais simples de representar graficamente:–Pontos (vértices) e linhas (arestas).

•A forma mais simples de representar graficamente:–Pontos (vértices) e linhas (arestas).



• No problema das casas:– Vértices = casas + serviços.– Arestas = tubulação entre casa e serviço.

• No problema de coloração de mapas:– Vértices = estados.– Arestas = relacionam estados vizinhos.

• No problema das casas:– Vértices = casas + serviços.– Arestas = tubulação entre casa e serviço.

• No problema de coloração de mapas:– Vértices = estados.– Arestas = relacionam estados vizinhos.


Grafos no Mundo Real

• Redes de computadores.• Conexão de vôos aéreos.• Restrições de precedência.• Fluxo de um programa.• Mais exemplos?

• Redes de computadores.• Conexão de vôos aéreos.• Restrições de precedência.• Fluxo de um programa.• Mais exemplos?


Programa a ser cumprido

1. Conceitos Básicos.2. Representação de Grafos.3. Caminhos e circuitos.4. Grafos dirigidos.5. Grafos valorados.6. Conectividade, Planaridade e Coloração.7. Árvores.8. Busca em Grafos.9. Fluxo em Redes.10.Emparelhamento.

1. Conceitos Básicos.2. Representação de Grafos.3. Caminhos e circuitos.4. Grafos dirigidos.5. Grafos valorados.6. Conectividade, Planaridade e Coloração.7. Árvores.8. Busca em Grafos.9. Fluxo em Redes.10.Emparelhamento.

4


Algumas Dicas

• Participem em sala de aula. Façam perguntas.– Isso ajuda a conhecer o que a turma não está entendendo– Diminua o ritmo de apresentação dos slides, se for o

caso.• Não deixem mini-prova pra reposição.• Façam as listas de exercícios:

– Resolvam, se possível, novos problemas. Isso requer insight na percepção do mapeamento para grafos. Consolidam os algoritmos estudados em sala de aula.

• Leiam atentamente as questões das mini-provas:– Muita gente erra pelo fato de não entender o que foi

pedido.

• Participem em sala de aula. Façam perguntas.– Isso ajuda a conhecer o que a turma não está entendendo– Diminua o ritmo de apresentação dos slides, se for o

caso.• Não deixem mini-prova pra reposição.• Façam as listas de exercícios:

– Resolvam, se possível, novos problemas. Isso requer insight na percepção do mapeamento para grafos. Consolidam os algoritmos estudados em sala de aula.

• Leiam atentamente as questões das mini-provas:– Muita gente erra pelo fato de não entender o que foi

pedido.


Teoria dos Grafos

Definições e Conceitos Básicos


Definições

• Dois tipos de elementos:– Vértices ou nós.– Arestas.

• Dois tipos de elementos:– Vértices ou nós.–– ArestasArestas..

v3

v2v4v1

v5 v6


Grafo Simples

G = (V, E)V é um conjunto finito não-vazio de vértices.E é um conjunto finito de arestas.Se e ∈ E, é um conjunto da forma:

e = { v, w} = vw = wv, onde v,w ∈ V.e é incidente a v e w.v e w são adjacentes ou vizinhos.

G = (V, E)V é um conjunto finito não-vazio de vértices.E é um conjunto finito de arestas.Se e ∈ E, é um conjunto da forma:

e = { v, w} = vw = wv, onde v,w ∈ V.e é incidente a v e w.v e w são adjacentes ou vizinhos.


Grafo Simples

v3

v2v4v1

v5 v6

e1

V = {v1, v2, v3, v4, v5, v6}

E = {v1v2, v1v3, v2v3, v2v4, v2v5, v3v4}

e1 é incidente a v2 e v5

v1, v3, v4 e v5 são adjacentes a v2


Graus de Vértices

• Grau de um vértice v (deg(v)) é o número de arestas queincidem em v.– Vértice ímpar.– Vértice par.– Vértice isolado.

• Um grafo é regular (k-regular) se todos os seus vértices tem o mesmo grau (k).

• Seqüência de graus de um grafo consiste em escrever emordem crescente os graus de seus vértices.

• Grau de um vértice v (deg(v)) é o número de arestas queincidem em v.– Vértice ímpar.– Vértice par.– Vértice isolado.

• Um grafo é regular (k-regular) se todos os seus vértices tem o mesmo grau (k).

• Seqüência de graus de um grafo consiste em escrever emordem crescente os graus de seus vértices.

5


Graus de Vértices

v3

v2v4v1

v5 v6

e1

v6 é um vértice isolado. deg(v6) = 0

v2 é um vértice par. deg(v2) = 4

v5 é um vértice ímpar. deg(v5) = 1

Seqüência de graus = 0, 1, 2, 2, 3, 4


Outros Tipos de Grafos

• Pseudo-grafos:– Multigrafos.– Grafos com auto-laços.

• Grafos dirigidos.• Não existe terminologia padronizada.

• Pseudo-grafos:– Multigrafos.– Grafos com auto-laços.

• Grafos dirigidos.• Não existe terminologia padronizada.

Vamos usar o termo grafo para representar grafos finitos, não dirigidos, com auto-laços e múltiplas arestas.


v3

v2v4v1

v5 v6

e1

deg(v4) = 4deg(v3) = 5


Proposição de Euler

•A partir do conceito de adjacência e graus de vértices.•Prova é intuitiva.•Como conseqüência: número de vértices ímpares é par.

•A partir do conceito de adjacência e graus de vértices.•Prova é intuitiva.•Como conseqüência: número de vértices ímpares é par.

Proposição de Euler:

i 1

n

deg vi 2 E


v3

v2v4v1

v5 v6

Σ deg(vi) = 2 + 4 + 3 + 2 + 1 + 0 = 12 = 2 x 6

№ de vértices ímpares = 2 = v3 e v5


Isomorfismo de Grafos

• Dois grafos são isomórficos:– São essencialmente iguais.– Correspondência entre os vértices e arestas.

• Sejam G1= (V1, E1) e G2 = (V2, E2):– G1 ≈ G2, se existir uma bijeção f: V1 → V2:

• Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2.

• Toda aresta em E2 tem a forma de f(v)f(w) paraalguma aresta vw ∈ E1.

• Dois grafos são isomórficos:– São essencialmente iguais.– Correspondência entre os vértices e arestas.

• Sejam G1= (V1, E1) e G2 = (V2, E2):– G1 ≈ G2, se existir uma bijeção f: V1 → V2:

• Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2.

• Toda aresta em E2 tem a forma de f(v)f(w) paraalguma aresta vw ∈ E1.

6



u v w

x y z



u v w

x y z

f(u) = azul, f(v) = roxo, f(w) = vermelhof(x) = verde, f(y) = amarelo, f(z) = rosa



• Isomorfismo preserva:– Simetria: G1 ≈ G2 ↔ G2 ≈ G1.– Reflexividade: G ≈ G.– Transitividade: G1 ≈ G2 e G2 ≈ G3 → G1 ≈ G3.

• Proposições válidas se G1 ≈ G2:– G1 e G2 têm o mesmo número de vértices.– G1 e G2 têm a mesma seqüência de graus.– G1 e G2 têm o mesmo número de arestas.

• Isomorfismo preserva:– Simetria: G1 ≈ G2 ↔ G2 ≈ G1.– Reflexividade: G ≈ G.– Transitividade: G1 ≈ G2 e G2 ≈ G3 → G1 ≈ G3.

• Proposições válidas se G1 ≈ G2:– G1 e G2 têm o mesmo número de vértices.– G1 e G2 têm a mesma seqüência de graus.– G1 e G2 têm o mesmo número de arestas.


Subgrafos

• G1 = (V1, E1) é subgrafo de G2 = (V2, E2) sss:– V1 é subconjunto de V2; e,– E1 é subconjunto de E2.

• Subgrafos podem ser obtidos através da remoção de arestase vértices.

• G1 = (V1, E1) é subgrafo de G2 = (V2, E2) sss:– V1 é subconjunto de V2; e,– E1 é subconjunto de E2.

• Subgrafos podem ser obtidos através da remoção de arestase vértices.


Subgrafos

u w

x y z

u v w

x y z

u v w

x y z

G1 G2 G3

G2 = G1 \ {uz}G3 = G1 \ {v}


Grafos Completos e nulos

• Grafo nulo é aquele em que E = Ø.• Um grafo simples é completo se qualquer par de vértices

distintos é adjacente.– Grafo simples completo de n vértices é dito Kn.

• Grafo nulo é aquele em que E = Ø.• Um grafo simples é completo se qualquer par de vértices

distintos é adjacente.– Grafo simples completo de n vértices é dito Kn.

K3

K4

K5

7


Grafos Bipartidos

• Grafo bipartido é aquele em que V pode ser dividido em doissubconjuntos disjuntos não vazios V1 e V2.– Cada aresta conecta um vértice de V1 e um vértice de V2.

• Grafo bipartido completo: cada um dos elementos de V1 éadjacente a cada um dos elementos de V2.

• Grafo bipartido é aquele em que V pode ser dividido em doissubconjuntos disjuntos não vazios V1 e V2.– Cada aresta conecta um vértice de V1 e um vértice de V2.

• Grafo bipartido completo: cada um dos elementos de V1 éadjacente a cada um dos elementos de V2.


Grafos Bipartidos

u v w

x y z

K3,3

V1 = {u, v, w}V2 = {x, y, z}


Complemento de um Grafo

• Seja G um grafo simples:– G é complemento de G se:

• V = V; e,• Dois vértices são adjacentes em G se e somente se

eles não são adjacentes em G.

• Seja G um grafo simples:– G é complemento de G se:

• V = V; e,• Dois vértices são adjacentes em G se e somente se

eles não são adjacentes em G.


Exercício

1. Considere as 8 primeiras letras do seu nome. Construa um grafo simples em que:

• Toda vogal é adjacente a toda consoante.• Nenhuma vogal é adjacente a outra vogal.• Nenhum consoante é adjacente a outra consoante.

a) Defina formalmente esse grafo.b) Determine o complemento desse grafo.c) É um grafo bipartido? Justifique.

1. Considere as 8 primeiras letras do seu nome. Construa um grafo simples em que:

• Toda vogal é adjacente a toda consoante.• Nenhuma vogal é adjacente a outra vogal.• Nenhum consoante é adjacente a outra consoante.

a) Defina formalmente esse grafo.b) Determine o complemento desse grafo.c) É um grafo bipartido? Justifique.


Exercício

1. Você e seu amigo retornam das férias e são recebidos no aeroporto pelas mães e por duas irmãs do seu amigo. Após troca de abraços, cada uma das (outras) cinco pessoas lhe fala o número de abraços que deu. Curiosamente, todos os números são diferentes. Assumindo que:– Você e seu amigo não se abraçaram.– A mãe de vocês não se abraçaram.– As irmãs não se abraçaram.– Duas mesmas pessoas se abraçaram, no máximo, uma vez.

Responda:1. Quantas pessoas você abraçou?2. Quantas pessoas seu amigo abraçou?

1. Você e seu amigo retornam das férias e são recebidos no aeroporto pelas mães e por duas irmãs do seu amigo. Após troca de abraços, cada uma das (outras) cinco pessoas lhe fala o número de abraços que deu. Curiosamente, todos os números são diferentes. Assumindo que:– Você e seu amigo não se abraçaram.– A mãe de vocês não se abraçaram.– As irmãs não se abraçaram.– Duas mesmas pessoas se abraçaram, no máximo, uma vez.

Responda:1. Quantas pessoas você abraçou?2. Quantas pessoas seu amigo abraçou?


Exercício

1. Hoje à noite tem quatro jogos na rodada do Campeonato Brasileiro. Antes das partidas, comentaristas de três jornais deram seu palpite sobre quem venceria. São eles:

• Diário da Bola - São Paulo, Corinthians, Flamengo e Vasco. • Folha da Arquibancada - Palmeiras, Santos, Flamengo e

São Paulo. • O Pênalti - Cruzeiro, Corinthians, Santos e São Paulo. Nenhum jornal apostou que o Grêmio venceria.

Quem joga contra quem?

1. Hoje à noite tem quatro jogos na rodada do Campeonato Brasileiro. Antes das partidas, comentaristas de três jornais deram seu palpite sobre quem venceria. São eles:

• Diário da Bola - São Paulo, Corinthians, Flamengo e Vasco. • Folha da Arquibancada - Palmeiras, Santos, Flamengo e

São Paulo. • O Pênalti - Cruzeiro, Corinthians, Santos e São Paulo. Nenhum jornal apostou que o Grêmio venceria.

Quem joga contra quem?

8


Exercício

1. Se G é um grafo r-regular com n vértices e m arestas, expresse m em função de n e r.

2. Qual o número de arestas de um grafo completo com 6 vértices?

3. Determine o complemento de um K6.

1. Se G é um grafo r-regular com n vértices e m arestas, expresse m em função de n e r.

2. Qual o número de arestas de um grafo completo com 6 vértices?

3. Determine o complemento de um K6.


Teoria dos Grafos

Representação de Grafos


Representação de Grafos

• Representação gráfica:– Útil na prática.– Não é adequada para representar internamente (em um

computador) dados sobre a estrutura de grafos.• Várias formas de representar um grafo:

– Listas de Adjacência.– Matriz de Adjacência.– Matriz de Incidência.

• Representação gráfica:– Útil na prática.– Não é adequada para representar internamente (em um

computador) dados sobre a estrutura de grafos.• Várias formas de representar um grafo:

– Listas de Adjacência.– Matriz de Adjacência.– Matriz de Incidência.


Listas de Adjacência

• Consiste de um array Adj de |V| listas, um para cada vérticede V.

• Para cada u em V, Adj[u] consiste de todos os vértices de Gadjacentes a u.

• Vértices armazenados de forma arbitrária na lista.• Também pode ser utilizada no caso de grafos dirigidos.

• Consiste de um array Adj de |V| listas, um para cada vérticede V.

• Para cada u em V, Adj[u] consiste de todos os vértices de Gadjacentes a u.

• Vértices armazenados de forma arbitrária na lista.• Também pode ser utilizada no caso de grafos dirigidos.


Exemplo

1

3

45

2 52

51

42

23

41

3 4

5

2

1

2

3

4

5


Lista de Adjacência

• Forma compacta de representar grafos esparsos.• Utilizada com outras tipos de grafos.• Ineficiente para determinar se vw está no grafo.

• Forma compacta de representar grafos esparsos.• Utilizada com outras tipos de grafos.• Ineficiente para determinar se vw está no grafo.

9


Matriz de Adjacência

• Requer que os vértices sejam numerados arbitrariamente de 1, 2, ..., |V|.

• Matriz A= (aij), de ordem |V| x |V|:– aij = 1, se (i, j) ∈ E– aij = 0, caso contrário

• Requer que os vértices sejam numerados arbitrariamente de 1, 2, ..., |V|.

• Matriz A= (aij), de ordem |V| x |V|:– aij = 1, se (i, j) ∈ E– aij = 0, caso contrário


Exemplo

1

3

45

2

0 1 0 0 11 0 1 1 1

0 1 1 0 10 1 0 1 0

1 1 0 1 0

1 2 3 4 512345


Matriz de Adjacência

• Preferível em grafos pequenos.• Requer apenas um bit por entrada.• Válido também com outros tipos de grafos. Exemplo: grafos

ponderados.• O(V2).

• Preferível em grafos pequenos.• Requer apenas um bit por entrada.• Válido também com outros tipos de grafos. Exemplo: grafos

ponderados.• O(V2).


Matriz de Incidência

• Matriz B= (bij), de ordem |V| x |E|:– bij = 1, se vértice vi e aresta ej forem incidentes– bij = 0, caso contrário

• Matriz B= (bij), de ordem |V| x |E|:– bij = 1, se vértice vi e aresta ej forem incidentes– bij = 0, caso contrário

1

3

45

2

1 1 0 0 0 0 00 1 1 0 1 1 0

0 0 0 1 1 0 10 0 0 0 0 1 1

1 0 1 1 0 0 0

1 2 3 4 5 6 712345

e1

e2

e3

e4

e5

e6

e7


Verificando Isomorfismo

• Sejam A1 e A2 as matrizes de adjacência de G1 e G2. Se G1e G2 são isomórficos:– PA2PT = A1– P é uma matriz de permutação.

• Sejam A1 e A2 as matrizes de adjacência de G1 e G2. Se G1e G2 são isomórficos:– PA2PT = A1– P é uma matriz de permutação.

Teorema: Dois Grafos são isomórficos sss seus vértices podem ser rotulados de tal forma que as correspondentes matrizes de adjacências são iguais.


Exemplo

v1 v4

v2 v3

u1 u3

u2 u4

G1 G2

0 1 0 11 0 1 00 1 0 11 0 1 0

A1=0 0 1 10 0 1 11 1 0 01 1 0 0

A2=

10


Exemplo

1 0 0 00 0 0 10 1 0 00 0 1 0

P =

Se fizermos: u1 → v1; u2 → v3; u3 → v4; u4 →v2.

Teorema: Dois Grafos rotulados G1 e G2, com respectivas matrizes A1 e A2, são isomórficos sss A2 = PA1P

T, para alguma matriz de permutação P.


Teoria dos Grafos

Conjunto Independente de Vértices, Clique e Cobertura de Vértices


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 entrequalquer par de elementos de VIND.


– Um conjunto independente de vértices VIND de G é um subconjunto de V em que não existe nenhuma aresta entrequalquer par de elementos de VIND.

Grafo G Conjunto Independente de G


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


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 ConjuntoIndependente máximo?

Exercício 1:

• Encontre no grafo abaixo um Conjunto Independente Maximal que não é máximo. Qual a cardinalidade do ConjuntoIndependente máximo?

A B C D

E F G H



Exercício 2:

• Considere o algoritmo abaixo. Ele resolve o problema do conjunto independente máximo?

Exercício 2:


CINDMax1(G)CIND ← ∅while ∃v ∈ V-CIND | CIND ∪ {v} é independente do

CIND ← CIND ∪ {v}return CIND

11



Exercício 3:


Exercício 3:


CINDMax2(G)CIND ← ∅Y ← Vwhile Y ≠ ∅ do

escolher v ∈ V, com |N(v)| mínimoCIND ← CIND ∪ {v}Y ← Y – {v}Y ← Y – N(v)

return CIND


Cobertura de Vértices


– Uma cobertura de vértices VCOB de G é um subconjunto de V em que para qualquer aresta (u, v) ∈ E, u ∈VCOB ou v ∈VCOB.


– Uma cobertura de vértices VCOB de G é um subconjunto de V em que para qualquer aresta (u, v) ∈ E, u ∈VCOB ou v ∈VCOB.

Duas possíveis cobertura de vértices de G


Clique

• Seja um grafo G= (V, E):– Um clique VCLQ de G é um subconjunto de V, em que

quaisquer dois vértices u, v ∈ VCLQ, a aresta (u, v) ∈ E.

• Seja um grafo G= (V, E):– Um clique VCLQ de G é um subconjunto de V, em que

quaisquer dois vértices u, v ∈ VCLQ, a aresta (u, v) ∈ E.


• Não existe nenhum algoritmo de tempo polinomial que resolva estes problemas.

• É possível, entretanto, verificar em tempo polinomial se um determinado conjunto de vértices é um conjunto independente, um clique ou uma cobertura de vértices.

• Um conjunto independente de G é um clique do complemento de G.

• Não existe nenhum algoritmo de tempo polinomial que resolva estes problemas.

• É possível, entretanto, verificar em tempo polinomial se um determinado conjunto de vértices é um conjunto independente, um clique ou uma cobertura de vértices.

• Um conjunto independente de G é um clique do complemento de G.


Exercício

• A Vila de Grafos é uma área que consiste de um grande número de ruas retilíneas que ligam pequenas praças. Um guarda postado em uma praça é capaz de vigiar todas as ruas que saem da praça. Qual o número mínimo guardas necessário para vigiar toda a Vila? Resolva usando grafos.

• A Vila de Grafos é uma área que consiste de um grande número de ruas retilíneas que ligam pequenas praças. Um guarda postado em uma praça é capaz de vigiar todas as ruas que saem da praça. Qual o número mínimo guardas necessário para vigiar toda a Vila? Resolva usando grafos.


Teoria dos Grafos

Caminhos e Conectividade de Grafos

12


Exemplos de Aplicação de Grafos

• Planejamento eficiente de roteamento de pacotes naInternet.

• Definir melhor rota de distribuição de correspondência nospostos de distribuição da ECT.

• Determinar se uma mensagem pode ser trocada por doiscomputadores em uma rede (possivelmente usando links intermediários)

• Planejamento eficiente de roteamento de pacotes naInternet.

• Definir melhor rota de distribuição de correspondência nospostos de distribuição da ECT.

• Determinar se uma mensagem pode ser trocada por doiscomputadores em uma rede (possivelmente usando links intermediários)

Idéia básica: determinar alcançabilidade entre os vérticesatravés de caminhamento em arestas.


Passeio (walk)

• Um passeio em um grafo G= (V, E) é uma seqüênciaalternada de vértices e arestas que começa e termina com vértices.

• A seqüência v1, …, vk , ∀ v1, …, vk ∈ V, é um passeio de v1 avk , se (vj, vj+1) ∈ E, 1 ≤ j ≤ |k – 1|.

• Um passeio com k vértices possui k – 1 arestas.– Neste caso teríamos as seguintes arestas: (v1, v2) , (v2, v3),

…, (vk-1, vk)• O comprimento de um passeio é o número de arestas do

passeio.

• Um passeio em um grafo G= (V, E) é uma seqüênciaalternada de vértices e arestas que começa e termina com vértices.

• A seqüência v1, …, vk , ∀ v1, …, vk ∈ V, é um passeio de v1 avk , se (vj, vj+1) ∈ E, 1 ≤ j ≤ |k – 1|.

• Um passeio com k vértices possui k – 1 arestas.– Neste caso teríamos as seguintes arestas: (v1, v2) , (v2, v3),

…, (vk-1, vk)• O comprimento de um passeio é o número de arestas do

passeio.


Passeio (walk)

1

u3

4 5

2v


Passeio (walk)

1

u3

4 5

2v

Passeio: a seqüência u, 1, 4, 5, v


Passeio (walk)

1

u3

4 5

2v

O que dizer da seqüência u, 1, 4, 3, 5, 4, 3, 5, v ?


Caminho (Path)

• Um caminho ou caminho simples em um grafo é um passeioem que todos os seus vértices são distintos.

• Um caminho ou caminho simples em um grafo é um passeioem que todos os seus vértices são distintos.

1

u3

4 5

2v

O passeio u, 1, 4, 3, 5, 4, 3, 5, v não constitui um caminho.

13


Trilha (Trail), Circuito e Ciclo

• Uma trilha ou trajeto em um grafo é um passeio em quetodas as suas arestas são distintas.

• Um trajeto fechado ou circuito em um grafo é um trajeto emque o vértice inicial e o vértice final são iguais.

• Um circuito em que todos os vértices são distintos (com exceção do primeiro e do último) é chamado de ciclo.

• Um grafo acíclico é aquele que não possui ciclos.• Um triângulo é um ciclo de tamanho 3.

• Uma trilha ou trajeto em um grafo é um passeio em quetodas as suas arestas são distintas.

• Um trajeto fechado ou circuito em um grafo é um trajeto emque o vértice inicial e o vértice final são iguais.

• Um circuito em que todos os vértices são distintos (com exceção do primeiro e do último) é chamado de ciclo.

• Um grafo acíclico é aquele que não possui ciclos.• Um triângulo é um ciclo de tamanho 3.


f

b

e

c

a

d

Forneça exemplos de:-Passeio que não é nem trilha nem caminho.-Passeio que é trilha e não é caminho.-Passeio fechado que não é circuito.-Circuito que não é ciclo.-Triângulo.


Grafos Conectados (ou Conexos)

•Um grafo é conectado se e somente se existe um caminhoentre qualquer par de vértices do grafo.•Um componente de um grafo é um subgrafo conectadomaximal.•Um grafo com apenas um componente é um grafo conectado.

•Um grafo é conectado se e somente se existe um caminhoentre qualquer par de vértices do grafo.•Um componente de um grafo é um subgrafo conectadomaximal.•Um grafo com apenas um componente é um grafo conectado.


Grafo Euleriano

• Um grafo conectado G é dito Euleriano se existe uma trilhafechada contendo cada uma das arestas de G.

• O problema das pontes (lembram da primeira aula?) éequivalente a identificar se o grafo correspondente éEuleriano.

• Um grafo conectado G é dito Euleriano se existe uma trilhafechada contendo cada uma das arestas de G.

• O problema das pontes (lembram da primeira aula?) éequivalente a identificar se o grafo correspondente éEuleriano.

Teorema: Um Grafo Conectado G é Euleriano se e somente se o grau de cada vértice é par.


Grafo Euleriano

• O K5 é Euleriano?• O K5 é Euleriano?

K5


Grafo Hamiltoniano

• Um Grafo Hamiltoniano é um grafo que contém uma trilhafechada, passando exatamente uma única vez em cada um dos vértices.

• Um Grafo Hamiltoniano é um grafo que contém uma trilhafechada, passando exatamente uma única vez em cada um dos vértices.

Teorema (Ore, 1960): Se G é um grafo com n (≥3) vértices, e se deg(v) + deg(w) ≥ n para cada par de vértices não-adjacentes v e

w, então G é Hamiltoniano.

14


Exercício

1. Um grafo G = (V, E) é conexo se e somente se possui um vértice v ∈ V, tal que para cada vértice w ∈ V existe um caminho de w a v. Justifique.

2. Prove que todo grafo conexo com n vértices tem pelo menos n - 1 arestas.

3. K2,3 é Euleriano?4. É possível que um grafo e o seu complemento sejam ambos

desconectados?

1. Um grafo G = (V, E) é conexo se e somente se possui um vértice v ∈ V, tal que para cada vértice w ∈ V existe um caminho de w a v. Justifique.

2. Prove que todo grafo conexo com n vértices tem pelo menos n - 1 arestas.

3. K2,3 é Euleriano?4. É possível que um grafo e o seu complemento sejam ambos

desconectados?


Teoria dos Grafos

Grafos Dirigidos (Digrafos)


Grafos Dirigidos

•Grafos Dirigidos ou Dígrafos:–Conjunto finito não-vazio de vértices. –Conjunto finito de pares ordenados de vértices.–Chamamos de arcos em vez de arestas.–Um arco (v, w) é reduzido para vw.–D = (V, A)

•Grafos Dirigidos ou Dígrafos:–Conjunto finito não-vazio de vértices. –Conjunto finito de pares ordenados de vértices.–Chamamos de arcos em vez de arestas.–Um arco (v, w) é reduzido para vw.–D = (V, A)

ad

V = {a, b, c, d}A = {ab, bb, bc, cb, cb, ca, dc}

bc


Grafos Dirigidos

• Dígrafo Simples:– Todos os arcos são distintos.– Não existem auto-laços.

• Para obter o grafo correspondente de um dígrafo:– Eliminar as direções dos arcos.– Não necessariamente o grafo correspondente a um dígrafo

simples é simples.

• Dígrafo Simples:– Todos os arcos são distintos.– Não existem auto-laços.

• Para obter o grafo correspondente de um dígrafo:– Eliminar as direções dos arcos.– Não necessariamente o grafo correspondente a um dígrafo

simples é simples.


Exemplo

a

b c

d

Dígrafo Simples

a

b c

d

Grafo correspondente.Não é simples.


Representação por Lista de Adjacência

1 3

54

2 42

5

56

2

4

1

2

3

4

5

6

66

15


Representação por Matriz de Adjacência

1 3

54

2

6

0 1 0 1 0 00 0 0 0 1 0

0 1 0 0 0 00 0 0 0 1 1

0 0 0 1 0 0

1 2 3 4 5 6 123456 0 0 0 0 0 1


Representação por Matriz de Incidência

e21 3

54

2

6

1 1 0 0 0 0 0 00 -1 -1 1 0 0 0 0

-1 0 1 0 -1 0 0 00 0 0 0 0 1 1 0

0 0 0 -1 1 -1 0 0

1 2 3 4 5 6 7 8 123456 0 0 0 0 0 0 -1 0

e1 e3

e5

e4 e6 e7

e8


Grau de Vértices

•Os vértices de um dígrafo possuem:–Grau de entrada (indeg(v)) : número de arcos quechegam no vértice. –Grau de saída (outdeg(v)) : número de arcos quepartem do vértice.

•Da mesma forma:–Seqüência de graus de entrada.–Seqüência de graus de saída.

•Os vértices de um dígrafo possuem:–Grau de entrada (indeg(v)) : número de arcos quechegam no vértice. –Grau de saída (outdeg(v)) : número de arcos quepartem do vértice.

•Da mesma forma:–Seqüência de graus de entrada.–Seqüência de graus de saída.

Proposição:

i i) = | A|


Exemplo

a

b c

d indeg(a) = 1outdeg(a) = 1indeg(b) = 4outdeg(b) = 2

seqüência indeg = 0, 1, 2, 4seqüência outdeg = 1, 1, 2, 3

|A| = 7


Outros Conceitos

•Dois dígrafos são isomórficos se:–Existe um isomorfismo entre os respectivos grafos correspondentes.–Preserva a ordem dos vértices em cada arco.

•Os conceitos de passeio, caminho, ciclos, etc. são semelhantes:

–Deve respeitar a orientação dos arcos.

•Dois dígrafos são isomórficos se:–Existe um isomorfismo entre os respectivos grafos correspondentes.–Preserva a ordem dos vértices em cada arco.

•Os conceitos de passeio, caminho, ciclos, etc. são semelhantes:

–Deve respeitar a orientação dos arcos.


Exemplo

•D1 e D2 não são isomórficos.•D1 e D2 não são isomórficos.

a

b c

da

d

D2D1

Exemplo de uma trilha: dcbcaExemplo de um ciclo: cabc

16


Digrafos Conectados

• Um dígrafo D é conectado se:– Grafo correspondente é conectado.

• D é fortemente conectado se para quaisquer dois vértices v e w, existe um caminho entre v e w.

• D é Euleriano se e somente:– Fortemente conectado.– indeg(vi) = outdeg(vi), para todo i.

• Um dígrafo D é conectado se:– Grafo correspondente é conectado.

• D é fortemente conectado se para quaisquer dois vértices v e w, existe um caminho entre v e w.

• D é Euleriano se e somente:– Fortemente conectado.– indeg(vi) = outdeg(vi), para todo i.


Exemplo

a

b c

d

D2

D1 é conectado.D1 não é fortemente conectado.D1 não é Euleriano.

a

b c

D2 é conectado.D2 é fortemente conectado.D1 é Euleriano.


Torneio

• Um torneio é um dígrafo em que para quaisquer 2 vértices distintos v e w, existe exatamente um arco entre eles: ou vw ou wv.

• O score de um vértice v em um torneio é igual a outdeg(v).

• A seqüência de score é a seqüência de graus de saída.

• Um torneio é um dígrafo em que para quaisquer 2 vértices distintos v e w, existe exatamente um arco entre eles: ou vw ou wv.

• O score de um vértice v em um torneio é igual a outdeg(v).

• A seqüência de score é a seqüência de graus de saída.


Exemplo

Torneio de tamanho 5.score(a) = 3score(b) = 2seqüência de score = 0, 2, 2, 3, 3

a

cd

e b


Mais Sobre Torneios

• Teorema: todo torneio tem um caminho Hamiltoniano.• Um torneio é transitivo se e somente se:

– Sempre que uv e vw são arcos, uw também é.• É equivalente dizer de um torneio T:

– T tem um único caminho Hamiltoniano.– T é transitivo.– Todo jogador (vértice) em T tem um score diferente.

• Teorema: todo torneio tem um caminho Hamiltoniano.• Um torneio é transitivo se e somente se:

– Sempre que uv e vw são arcos, uw também é.• É equivalente dizer de um torneio T:

– T tem um único caminho Hamiltoniano.– T é transitivo.– Todo jogador (vértice) em T tem um score diferente.


Exercício

1. Professor Alencar é muito metódico. Todos os dias pela manhã, ele segue o mesmo ritual para se vestir. Faz parte do seu vestuário: cueca, calça, cinto, camisa, gravata, paletó, meias e sapato, além de um vistoso relógio de pulso. Ele sempre veste a cueca antes de por as meias e a calça. Os sapatos são calçados após o professor ter vestido a cueca, calça e meias. O cinto vai depois da calça e da camisa. O relógio pode ser colocado em qualquer momento. O paletó só é vestido depois do cinto e da gravata que écolocada depois da camisa. Modele a rotina do Professor Alencar usando grafos.

1. Professor Alencar é muito metódico. Todos os dias pela manhã, ele segue o mesmo ritual para se vestir. Faz parte do seu vestuário: cueca, calça, cinto, camisa, gravata, paletó, meias e sapato, além de um vistoso relógio de pulso. Ele sempre veste a cueca antes de por as meias e a calça. Os sapatos são calçados após o professor ter vestido a cueca, calça e meias. O cinto vai depois da calça e da camisa. O relógio pode ser colocado em qualquer momento. O paletó só é vestido depois do cinto e da gravata que écolocada depois da camisa. Modele a rotina do Professor Alencar usando grafos.

17


Exercício

2. Considere a figura abaixo que mostra a planta baixa de uma casa.É possível identificar portas que dividem os diversos cômodos da casa e portas que dão acesso à parte externa da casa. Utilize a teoria dos grafos para determinar se é possível começar do lado de fora da casa, entrar na casa e visitar cada cômodo uma única vez (sem deixar a casa) e, finalmente sair da casa. Justifique.

2. Considere a figura abaixo que mostra a planta baixa de uma casa.É possível identificar portas que dividem os diversos cômodos da casa e portas que dão acesso à parte externa da casa. Utilize a teoria dos grafos para determinar se é possível começar do lado de fora da casa, entrar na casa e visitar cada cômodo uma única vez (sem deixar a casa) e, finalmente sair da casa. Justifique.


Teoria dos Grafos

Busca em Grafos


Busca em Grafos

• Objetivo: sistematicamente explorar todos os vérticese arestas de um grafo.• Dois tipos de busca:

–Busca em amplitude (Breadth First Search – BFS).–Busca em profundidade (Depth First Search –DFS).

• Objetivo: sistematicamente explorar todos os vérticese arestas de um grafo.• Dois tipos de busca:

–Busca em amplitude (Breadth First Search – BFS).–Busca em profundidade (Depth First Search –DFS).


Busca em Amplitude (BFS)

• Representa um dos mais simples algoritmos de busca emgrafos.

• É usado como modelo para alguns algoritmos importantes:– Menor caminho.– Árvore de cobertura mínima.

• Similar ao caminhamento por níveis em árvores.• Idéia: processa os vértices por níveis, começando por aqueles

vértices mais próximos do vértice inicial s e deixando osvértices mais distantes para depois.

• Representa um dos mais simples algoritmos de busca emgrafos.

• É usado como modelo para alguns algoritmos importantes:– Menor caminho.– Árvore de cobertura mínima.

• Similar ao caminhamento por níveis em árvores.• Idéia: processa os vértices por níveis, começando por aqueles

vértices mais próximos do vértice inicial s e deixando osvértices mais distantes para depois.



• O algoritmo BFS pode ser resumido nos seguintes passos:1. Distinguir o vértice inicial s.2. Sistematicamente explorar as arestas do grafo para

descobrir todos os vértices alcançáveis a partir de s.3. Computar a distância (menor número de arestas) de s

para todos os vértices alcançáveis.4. Produzir uma árvore de amplitude cuja raiz é s e contém

todos os vértices alcançáveis.5. Para todo vértice v alcançável a partir de s, o caminho na

árvore de amplitude corresponde ao menor caminho de spara v no grafo.

• O algoritmo BFS pode ser resumido nos seguintes passos:1. Distinguir o vértice inicial s.2. Sistematicamente explorar as arestas do grafo para

descobrir todos os vértices alcançáveis a partir de s.3. Computar a distância (menor número de arestas) de s

para todos os vértices alcançáveis.4. Produzir uma árvore de amplitude cuja raiz é s e contém

todos os vértices alcançáveis.5. Para todo vértice v alcançável a partir de s, o caminho na

árvore de amplitude corresponde ao menor caminho de spara v no grafo.



• O algoritmo descobre todos os vértices com distância k a partir de s, antes de descobrir os vértices com distância k+1.

• Para manter controle do processamento dos vértices, o algoritmo utiliza um esquema de 3 cores: branco, cinza e preto:– Todos os vértices começam com cor branca e depois

podem mudar para cinza e, posteriormente, para preto.– Quando um vértice é visitado a primeira vez ele deixa de

ser branco.– É necessário usar duas cores diferente do branco para

garantir a sistemática da amplitude.

• O algoritmo descobre todos os vértices com distância k a partir de s, antes de descobrir os vértices com distância k+1.

• Para manter controle do processamento dos vértices, o algoritmo utiliza um esquema de 3 cores: branco, cinza e preto:– Todos os vértices começam com cor branca e depois

podem mudar para cinza e, posteriormente, para preto.– Quando um vértice é visitado a primeira vez ele deixa de

ser branco.– É necessário usar duas cores diferente do branco para

garantir a sistemática da amplitude.

18


Algoritmo BFS

• Assumir que o grafo G = (V, E) é representado com lista de adjacências.

• Para cada vértice no grafo, o algoritmo mantém estruturas auxiliares:– A variável cor[u] mantém a informação sobre a cor de

cada vértice.– A variável π[u] mantém a informação do predecessor de

cada vértice. Quando não existe predecessor π[u] = NIL.– d[u] mantém o valor da distância entre o vértice inicial e u.– Uma fila Q com política FIFO para gerenciar a lista de

vértices de cor cinza.

• Assumir que o grafo G = (V, E) é representado com lista de adjacências.

• Para cada vértice no grafo, o algoritmo mantém estruturas auxiliares:– A variável cor[u] mantém a informação sobre a cor de

cada vértice.– A variável π[u] mantém a informação do predecessor de

cada vértice. Quando não existe predecessor π[u] = NIL.– d[u] mantém o valor da distância entre o vértice inicial e u.– Uma fila Q com política FIFO para gerenciar a lista de

vértices de cor cinza.


Algoritmo BFS

BFS(G, s)for ∀u ∈ V[G] – {s} do

cor[u] ← BRANCOd[u] ← ∞π[u] ← NIL

cor[s] ← CINZAd[s] ← 0π[s] ← NILQ ← {s}while Q ≠ Ø do

u ← Desenfileira[Q]for ∀v ∈ Adj[u] do

if cor[v] = BRANCO thencor[v] ← CINZAd[v] ← d[u] + 1π[v] ← uEnfileira(Q, v)

cor[u] ← PRETO


Algoritmo BFS




u ← Enfileira[Q]for ∀v ∈ Adj[u] do


cor[u] ← PRETO

Inicia variáveis auxiliares Para cada um dos vértices,Com exceção da origem


Algoritmo BFS






cor[u] ← PRETO

Inicia variáveis auxiliares da origem s e a fila Q


Algoritmo BFS






cor[u] ← PRETO

Se o vértice adjacente é branco,significa que ele nunca foi visitado.Deve ser pintado de CINZA eenfileirado para posterior processamento.


Algoritmo BFS






cor[u] ← PRETO Quando todos os adjacentes de uforem processados, ele passa a serPRETO

19


Exemplo BFS

∞

∞ ∞

∞

∞

∞

∞

r s t u

v w x y


Exemplo BFS

∞

∞

0

∞

∞

∞

∞

∞

r s t u

v w x y

sQ:


Exemplo BFS

1

∞

0

1

∞

∞

∞

∞

r s t u

v w x y

wQ: r


Exemplo BFS

1

∞

0

1

2

2

∞

∞

r s t u

v w x y

rQ: t x


Exemplo BFS

1

2

0

1

2

2

∞

∞

r s t u

v w x y

Q: t x v


Exemplo BFS

1

2

0

1

2

2

3

∞

r s t u

v w x y

Q: x v u

20


Exemplo BFS

1

2

0

1

2

2

3

3

r s t u

v w x y

Q: v u y


Exemplo BFS

1

2

0

1

2

2

3

3

r s t u

v w x y

Q: u y


Exemplo BFS

1

2

0

1

2

2

3

3

r s t u

v w x y

Q: y


Exemplo BFS

1

2

0

1

2

2

3

3

r s t u

v w x y

Q: Ø


Busca em Profundidade (DFS)

• DFS é uma generalização do caminhamento em pré-ordem em árvores.• A idéia principal é buscar verticalmente, sempre quepossível.• Sempre que um novo vértice v é descoberto, ele deveser explorado por completo.• Quando v é totalmente explorado, fazer backtrackingpara o seu predecessor.

• DFS é uma generalização do caminhamento em pré-ordem em árvores.• A idéia principal é buscar verticalmente, sempre quepossível.• Sempre que um novo vértice v é descoberto, ele deveser explorado por completo.• Quando v é totalmente explorado, fazer backtrackingpara o seu predecessor.


Busca em Profundidade (DFS)

• Alguns detalhes sobre o algoritmo de DFS:– Sempre que um vértice v é descoberto, o valo de π(predecessor) é atualizado.– Pode ser formada uma floresta de árvores.– Cada vértice v tem duas marcas de tempo d[v] e f[v] que indicam, respectivamente, quando v foiprimeiramente visitado (cor CINZA) e quando v foitotalmente explorado (cor PRETO).

• Alguns detalhes sobre o algoritmo de DFS:– Sempre que um vértice v é descoberto, o valo de π(predecessor) é atualizado.– Pode ser formada uma floresta de árvores.– Cada vértice v tem duas marcas de tempo d[v] e f[v] que indicam, respectivamente, quando v foiprimeiramente visitado (cor CINZA) e quando v foitotalmente explorado (cor PRETO).

21


Algoritmo DFS

DFS(G)for ∀u ∈ V[G] do

cor[u] ← BRANCOπ[u] ← NIL

tempo ← 0for ∀u ∈ V[G] do

if cor[u] = BRANCO thenVisitaDFS(u)

VisitaDFS(u)cor[u] ← CINZAd[u] ← tempo ← tempo + 1for ∀v ∈ Adj[u] do

if cor[v] = BRANCO thenπ[v] ← uVisitaDFS(v)

cor[u] ← PRETOF[u] ← tempo ← tempo + 1


Exemplo DFS

origem


Exemplo DFS

1 | | |

| | |

| |

d f


Exemplo DFS

1 | | |

| | |

2 | |

d f


Exemplo DFS

1 | | |

| | 3 |

2 | |

d f


Exemplo DFS

1 | | |

| | 3 | 4

2 | |

d f

22


Exemplo DFS

1 | | |

| 5 | 3 | 4

2 | |

d f


Exemplo DFS

1 | | |

| 5 | 63 | 4

2 | |

d f


Exemplo DFS

1 | 8 | |

| 5 | 63 | 4

2 | 7 |

d f


Exemplo DFS

1 | 8 | |

| 5 | 63 | 4

2 | 7 9 |

d f


Exemplo DFS

1 | 8 | |

| 5 | 63 | 4

2 | 7 9 |10

d f


Exemplo DFS

1 | 8 |11 |

| 5 | 63 | 4

2 | 7 9 |10

d f

23


Exemplo DFS

1 |12 8 |11 |

| 5 | 63 | 4

2 | 7 9 |10

d f


Exemplo DFS

1 |12 8 |11 13|

| 5 | 63 | 4

2 | 7 9 |10

d f


Exemplo DFS

1 |12 8 |11 13|

14| 5 | 63 | 4

2 | 7 9 |10

d f


Exemplo DFS

1 |12 8 |11 13|

14|155 | 63 | 4

2 | 7 9 |10

d f


Exemplo DFS

1 |12 8 |11 13|16

14|155 | 63 | 4

2 | 7 9 |10

d f


Teoria dos Grafos

Componentes Fortemente Conectados

24


Exemplo DFS

/

/

/

/

/

r s t

v w x

/


Exemplo DFS

/

/

/

/

/

r s t

v w x

1/


Exemplo DFS

/

2/

/

/

/

r s t

v w x

1/


Exemplo DFS

/

2/

3/

/

/

r s t

v w x

1/


Exemplo DFS

4/

2/

3/

/

/

r s t

v w x

1/


Exemplo DFS

4/5

2/

3/

/

/

r s t

v w x

1/

25


Exemplo DFS

4/5

2/

3/6

/

/

r s t

v w x

1/


Exemplo DFS

4/5

2/7

3/6

/

/

r s t

v w x

1/


Exemplo DFS

4/5

2/7

3/6

/

/

r s t

v w x

1/8


Exemplo DFS

4/5

2/7

3/6

9/

/

r s t

v w x

1/8


Exemplo DFS

4/5

2/7

3/6

9/

10/

r s t

v w x

1/8


Exemplo DFS

4/5

2/7

3/6

9/

10/11

r s t

v w x

1/8

26


Exemplo DFS

4/5

2/7

3/6

9/12

10/11

r s t

v w x

1/8


Busca em Profundidade (Revisão)

• A busca em profundidade produz uma floresta de árvores.• É possível identificar 4 tipos de arcos:

– Arcos da árvore: arcos na árvore de profundidade.– Arcos de retorno: aqueles que conectam um vérticeu a um vértice ancestral na árvore de profundidade.– Arcos forward: aqueles que conectam um vértice ua um vértice descente na árvore de profundidade.– Arcos de cruzamento: os demais arcos.

• A busca em profundidade produz uma floresta de árvores.• É possível identificar 4 tipos de arcos:

– Arcos da árvore: arcos na árvore de profundidade.– Arcos de retorno: aqueles que conectam um vérticeu a um vértice ancestral na árvore de profundidade.– Arcos forward: aqueles que conectam um vértice ua um vértice descente na árvore de profundidade.– Arcos de cruzamento: os demais arcos.


DFS (Tipos de Arcos)

4/5

2/7

3/6

9/12

10/11

r s t

v w x

1/8

F B

B

C


Componente Fortemente Conectado (SCC)

• Um Grafo G é fortemente conectado se, ∀u,v ∈ V, existe um caminho entre u e v e um caminho entre v e u.• Um componente fortemente conectado de um grafo éum subconjunto maximal de vértices (juntamente com os seus correspondentes arcos) que é fortementeconectado.

• Um Grafo G é fortemente conectado se, ∀u,v ∈ V, existe um caminho entre u e v e um caminho entre v e u.• Um componente fortemente conectado de um grafo éum subconjunto maximal de vértices (juntamente com os seus correspondentes arcos) que é fortementeconectado.

FortementeConectado

Não é FortementeConectado


Exemplo SCC

s t u

w x y

r

v


Exemplo SCC

s t u

w x y

r

v

27


Grafo de Componentes

• GSCC = (VSCC, ESCC).• VSCC tem um vértice para cada SCC em G.• ESCC tem um arco se existe um arco entre oscorrespondentes SCCs em G.

• GSCC = (VSCC, ESCC).• VSCC tem um vértice para cada SCC em G.• ESCC tem um arco se existe um arco entre oscorrespondentes SCCs em G.


Transposto de um Grafo Dirigido

• GT é transposto de um grafo dirigiro:– GT = (V, ET), ET = {(u, v) : (v, u) ∈ E}.– GT é G com todos os arcos revertidos.

• GT é transposto de um grafo dirigiro:– GT = (V, ET), ET = {(u, v) : (v, u) ∈ E}.– GT é G com todos os arcos revertidos.

s

w

r

v

s

w

r

v

GG

T


Algoritmo SCC

SCC(G)DFS(G) Calcula GT

DFS(GT)Saída: os arcos de árvore formam SCCs


Exemplo Grafo de SCCs

s t u

w x y

r

v


Passo 1: Aplicar DFS

3/4

1/10

2/7

8/9

5/6

s t u

w x y

11/1613/14

12/15

r

v


Passo 2: Calcular GT

s t u

w x y

r

v

28


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 3: DFS de GT

s t u

w x y

r

v

29


Passo 3: DFS de GT

s t u

w x y

r

v


Passo 4: Componentes de GT

ut

xw y

rsv


Teoria dos Grafos

Menor Caminho de Origem Única


Menor Caminho com Origem Única

• Problema: encontrar o caminho, mais curto possível, entre Campina Grande e Natal.• Suponha que temos um mapa com todas as estradasdo Nordeste, com a distância entre todos os pares de cidades adjacentes.• Como determinar a menor distância entre as duascidades?

• Problema: encontrar o caminho, mais curto possível, entre Campina Grande e Natal.• Suponha que temos um mapa com todas as estradasdo Nordeste, com a distância entre todos os pares de cidades adjacentes.• Como determinar a menor distância entre as duascidades?

Uma maneira de resolver este problema é encontrar a menor distância entre CampinaGrande e todas as outras cidades do Nordeste.

Em grafos: Menor Caminho com Origem Única



• Consideramos um grafo dirigido G = (V, E), com uma funçãopeso w(u, v): E → R, que mapeia pesos a arestas.

• O peso do caminho p = <v0, v1, …, vk> é a soma dos pesos das arestas que o constituem: – w(p) = ∑k

i=1 w(vi-1, vi)• Definimos o menor caminho entre u e v como:

– δ(u, v) = min{w(p): u ⇒ v}, se existir um caminho.– δ(u, v) = ∞, se não existir caminho.

• Consideramos um grafo dirigido G = (V, E), com uma funçãopeso w(u, v): E → RR, que mapeia pesos a arestas.

• O peso do caminho p = <v0, v1, …, vk> é a soma dos pesos das arestas que o constituem: – w(p) = ∑k

i=1 w(vi-1, vi)• Definimos o menor caminho entre u e v como:

– δ(u, v) = min{w(p): u ⇒ v}, se existir um caminho.– δ(u, v) = ∞, se não existir caminho.



• O problema de menor caminho em um grafo consiste emdeterminar o menor caminho entre um vértice inicial s ∈ V e todos os demais vértices de V.

• Algumas variações do problema:– Menor caminho com destino único.– Menor caminho entre um par de vértices.– Menor caminho entre todos os pares de vértices.

• Em algumas instância é possível encontrar pesos negativos.

• O problema de menor caminho em um grafo consiste emdeterminar o menor caminho entre um vértice inicial s ∈ V e todos os demais vértices de V.

• Algumas variações do problema:– Menor caminho com destino único.– Menor caminho entre um par de vértices.– Menor caminho entre todos os pares de vértices.

• Em algumas instância é possível encontrar pesos negativos.

30


Exemplo de Menor Caminho

0

3

5

9

11

s

u v

x y

3

3

6

6

22

1

5

4

7



0

3

5

9

11

s

u v

x y

3

3

6

6

22

1

5

4

7



0

3

5

9

11

s

u v

x y

3

3

6

6

22

1

5

4

7


Algoritmo de Dijkstra

• Assumir que qualquer cidade é infinitamente distante da cidade origem:

• Abordagem otimista: – Sempre que chegar em uma cidade, assumir que

encontrou o menor caminho.– Se depois encontra algo melhor, atualizar os dados.

• A partir da cidade de origem, visitar primeiro as cidades adjacentes, depois as adjacentes das adjacentes, e assim por diante.

• Algoritmo bastante conhecido, utilizado no OSPF.

• Assumir que qualquer cidade é infinitamente distante da cidade origem:

• Abordagem otimista: – Sempre que chegar em uma cidade, assumir que

encontrou o menor caminho.– Se depois encontra algo melhor, atualizar os dados.

• A partir da cidade de origem, visitar primeiro as cidades adjacentes, depois as adjacentes das adjacentes, e assim por diante.

• Algoritmo bastante conhecido, utilizado no OSPF.



• Não considera pesos negativos.• Uso de duas variáveis auxiliares:

– d[v] (estimativa de menor distância)– π[v] (predecessor)

• Não considera pesos negativos.• Uso de duas variáveis auxiliares:

– d[v] (estimativa de menor distância)– π[v] (predecessor)

IniciaMenorCaminho(G, s)for ∀u ∈ V[G] do

d[u] ← ∞π[u] ← NIL

d[s] ← 0



• Atualização dos dados utiliza a técnica de relaxamento.• Atualização dos dados utiliza a técnica de relaxamento.

Relaxa(u, v, w)if d[v] > d[u] + w(u,v) then

d[v] ← d[u] + w(u,v)π[v] ← u

5 9u v

2

5 7u v

2

5 6u v

2

5 6u v

2

31



Dijkstra(G, w, s)IniciaMenorCaminho(G, s)S ← ØQ ← V[G]while Q ≠ Ø do

u ← ExtraiMenor[Q]S ← S ∪ {u}for ∀v ∈ Adj[u] do

Relaxa(u, v, w)


Execução do Algoritmo de Dijkstra

0

∞

∞

∞

∞

s

u v

x y

10

7

1

2

24

3

5

9

6

sQ: u v x y



0

∞

∞

∞

∞

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: u v x y



0

10

5

∞

∞

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: x u v y



0

10

5

∞

∞

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: u v y



0

8

5

14

7

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: y u v

32



0

8

5

14

7

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: u v



0

8

5

13

7

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: u v



0

8

5

9

7

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: v



0

8

5

9

7

s

u v

x y

10

7

1

2

24

3

5

9

6

Q: Ø


Algoritmo Bellman-Ford

• Resolve menor caminho de forma mais genérica, incluindo pesos negativos.

• Verifica a existência de ciclos de peso negativo:– Se existir, indica que não é possível achar menor

caminho.• Também utiliza a técnica de relaxamento de arestas.• A idéia principal: progressivamente ir diminuindo a estimativa

de distância até encontrar o menor caminho.

• Resolve menor caminho de forma mais genérica, incluindo pesos negativos.

• Verifica a existência de ciclos de peso negativo:– Se existir, indica que não é possível achar menor

caminho.• Também utiliza a técnica de relaxamento de arestas.• A idéia principal: progressivamente ir diminuindo a estimativa

de distância até encontrar o menor caminho.


Algoritmo de Bellman-Ford

Bellman-Ford(G, w, s)IniciaMenorCaminho(G, s)for i ← 1 to |V[G]| - 1 do

for ∀(u, v) ∈ E[G] doRelaxa(u, v, w)

for ∀(u, v) ∈ E[G] doif d[v] > d[u] + w(u, v) then

return FALSEreturn TRUE

33


Execução do Algoritmo de Bellman-Ford

0

∞

∞

∞

∞

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4

uv, ux, uy, vu, xv, xy, yv, yz, zu, zx



0

∞

∞

∞

∞

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4




0

6

∞

∞

∞

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4




0

6

7

∞

∞

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4



Resultado Após Primeira Passada

0

6

7

∞

∞

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4



Resultado Após Segunda Passada

0

6

7

4

2

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4


34


Resultado Após Terceira Passada

0

2

7

4

2

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4



Resultado Após Quarta Passada

0

2

7

4

-2

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4



Resultado Final

0

2

7

4

-2

z

u v

x y

6

2

5

9

8

7

-3

7

-2

-4


TRUE: ausência de ciclos negativos


Algoritmo de Floyd-Warshall

• Calcula a menor distância entre todos os pares de vértices.

• Considera uma matriz n×n e utiliza a técnica de programação dinâmica.

• Seja A[i,j] = c[i,j] ∀ i,j & i≠j.• Se (i,j) não é uma aresta, fazer A[i,j]=∞ e A[i,i]=0• Ak[i,j] = min (Ak-1[i,j] , Ak-1[i,k]+ Ak-1[k,j])

• Calcula a menor distância entre todos os pares de vértices.

• Considera uma matriz n×n e utiliza a técnica de programação dinâmica.

• Seja A[i,j] = c[i,j] ∀ i,j & i≠j.• Se (i,j) não é uma aresta, fazer A[i,j]=∞ e A[i,i]=0• Ak[i,j] = min (Ak-1[i,j] , Ak-1[i,k]+ Ak-1[k,j])



Floyd-Warshall(G, w)Iniciar A[i,j] = w[i,j]Iniciar A[i,i] = 0for k ← 1 to n do

for i ← 1 to n dofor j ← to n do

if A[i,j] > A[i,k] + A[k,j] thenA[i,j] = A[j,k] + A[k,j]



35


Teoria dos Grafos

Árvores


Árvore - Introdução

• Em nosso dia-a-dia nos deparamos com muitosexemplos de árvores:

– Árvore genealógica.– Organograma de uma empresa.– Tabela de um torneio esportivo.

• Na computação:– Organização da estrutura de arquivos (diretório).– Armazenamento e busca eficiente de dados.– Ordenação.– Árvores de decisão.

• Em nosso dia-a-dia nos deparamos com muitosexemplos de árvores:

– Árvore genealógica.– Organograma de uma empresa.– Tabela de um torneio esportivo.

• Na computação:– Organização da estrutura de arquivos (diretório).– Armazenamento e busca eficiente de dados.– Ordenação.– Árvores de decisão.


Árvore Livre

• Uma árvore (livre) é um grafo acíclico, não orientado e conectado.

• Uma floresta é um grafo acíclico, não orientado mas, possivelmente, desconectado.

• Considerando que G = (V, E) é um grafo não orientado, éequivalente dizer:1. G é uma árvore.2. Um par de vértice qualquer (v, w) de G está conectado

por apenas um caminho.3. G é conectado. A remoção de uma aresta desconecta G.4. G é conectado e |E| = |V| - 1.5. G é acíclico e |E| = |V| - 1.6. G é acíclico. A adição de uma aresta cria um ciclo em G.

• Uma árvore (livre) é um grafo acíclico, não orientado e conectado.

• Uma floresta é um grafo acíclico, não orientado mas, possivelmente, desconectado.

• Considerando que G = (V, E) é um grafo não orientado, éequivalente dizer:1. G é uma árvore.2. Um par de vértice qualquer (v, w) de G está conectado

por apenas um caminho.3. G é conectado. A remoção de uma aresta desconecta G.4. G é conectado e |E| = |V| - 1.5. G é acíclico e |E| = |V| - 1.6. G é acíclico. A adição de uma aresta cria um ciclo em G.


Árvore Enraizada

• Tipo especial de árvore que apresenta um vértice (raiz) quese distingue dos demais.

• Utilizamos o termo nó para fazer referência aos vértices.

• Tipo especial de árvore que apresenta um vértice (raiz) quese distingue dos demais.

• Utilizamos o termo nó para fazer referência aos vértices.

7

3 10 4

8 12 11 2

6 5 19


Algumas Definições

• Seja x um nó de uma árvore enraizada T com raiz r:– Ancestral: é qualquer nó y no caminho de r a x.– Descendente: x é um descendente de y se y é ancestral

de x.– Ancestral Próprio: y é ancestral próprio de x se y é

ancestral de x e y ≠ x. – Descendente Próprio: y é descendente próprio de x se y

é descendente de x e y ≠ x. – Sub-árvore enraizada em x: árvore induzida pelos

descendentes de x, com x sendo a raiz. – Filho: x é filho de y se ele é um descendente direto. – Pai: é o ancestral próprio mais próximo. A raiz é o único

nó sem pai.

• Seja x um nó de uma árvore enraizada T com raiz r:– Ancestral: é qualquer nó y no caminho de r a x.– Descendente: x é um descendente de y se y é ancestral

de x.– Ancestral Próprio: y é ancestral próprio de x se y é

ancestral de x e y ≠ x. – Descendente Próprio: y é descendente próprio de x se y

é descendente de x e y ≠ x. – Sub-árvore enraizada em x: árvore induzida pelos

descendentes de x, com x sendo a raiz. – Filho: x é filho de y se ele é um descendente direto. – Pai: é o ancestral próprio mais próximo. A raiz é o único

nó sem pai.


Algumas Definições

– Folha: um nó sem filhos.– Nó interno: um nó que não é folha.– Grau: o grau de y é o número de filhos de y. – Profundidade: o comprimento desde a raiz r até x é a

profundidade de x em T. – Altura:

• a altura de um nó em uma árvore é o maiorcomprimento do nó até uma folha.

• A altura de uma árvore é a altura de sua raiz. • Altura da árvore é a maior profundidade de qualquer

nó da árvore.

– Folha: um nó sem filhos.– Nó interno: um nó que não é folha.– Grau: o grau de y é o número de filhos de y. – Profundidade: o comprimento desde a raiz r até x é a

profundidade de x em T. – Altura:

• a altura de um nó em uma árvore é o maiorcomprimento do nó até uma folha.

• A altura de uma árvore é a altura de sua raiz. • Altura da árvore é a maior profundidade de qualquer

nó da árvore.

36


Exemplo

7

3 10 4

8 12 11 2

6 5 19

Profundidade 0

Profundidade 1

Profundidade 2

Profundidade 3

Profundidade 4

Altura da árvore é 4


Implementação de Árvores

• Além da informação de cada nó, um link para cadaum dos filhos.

• Inconveniente: não sabemos a priori a quantidadede filhos em cada nó.

• Além da informação de cada nó, um link para cadaum dos filhos.

• Inconveniente: não sabemos a priori a quantidadede filhos em cada nó.



• Os filhos de um nó são mantidos em uma listaencadeada.

• Os filhos de um nó são mantidos em uma listaencadeada.



A /

B / C / D E F G /

I / J / K / L /H / /

P / Q / /

M / /

N / /


Árvore Ordenada

• Árvore enraizada em que os filhos de cada nó estãoordenados.

• Árvore enraizada em que os filhos de cada nó estãoordenados.

7

3 10 4

8 12 11 2

6 5 1

9

7

3 10 4

12 8 11 2

1 6 5

9

Árvores enraizadas iguais.Árvores ordenadas diferentes.


Árvore Binária

• Estrutura de nós que é definida recursivamente através de um conjunto de nós:– Não contém nenhum nó, ou;– Formada por 3 conjuntos disjuntos: um nó raiz, duas sub-

árvores binárias (direita e esquerda).

• Estrutura de nós que é definida recursivamente através de um conjunto de nós:– Não contém nenhum nó, ou;– Formada por 3 conjuntos disjuntos: um nó raiz, duas sub-

árvores binárias (direita e esquerda).

raiz

TL TR

37


Árvore Binária – Conceitos Importantes

• Árvore vazia ou nula: não contém nenhum nó.• Filho da esquerda: raiz da sub-árvore da esquerda (quando

houver).• Filho da direita: raiz da sub-árvore da direita (quando

houver).• Filho ausente: quando a sub-árvore dé a árvore nula.

• Árvore vazia ou nula: não contém nenhum nó.• Filho da esquerda: raiz da sub-árvore da esquerda (quando

houver).• Filho da direita: raiz da sub-árvore da direita (quando

houver).• Filho ausente: quando a sub-árvore dé a árvore nula.


Árvore Binária Cheia

• Cada nó ou é uma folha ou tem grau exatamente 2.• Cada nó ou é uma folha ou tem grau exatamente 2.

7

3 4

12 8 11 2

6 5

O número de nós internos de uma árvore binária cheia é f – 1, onde f é o número de folhas.


Árvore Binária Completa

• Árvore binária em que todas as folhas estão em uma mesmaprofundidade e todos os nós internos têm grau 2.

• Árvore binária em que todas as folhas estão em uma mesmaprofundidade e todos os nós internos têm grau 2.

7

3 4

12 8 11 2

O número de nós internos de uma árvore binária completa é 2h

– 1, onde h é a altura da árvore.


Árvore k-ária Completa

• Em uma árvore posicional, os filhos de um nó são rotuladoscomo inteiros distintos.

• Árvore k-ária é uma árvore posicional onde os filhos com rótulos maiores do que k são ausentes.

• Árvore k-ária completa é uma árvore k-ária onde todas as folhas têm a mesma profundidade e todos os nós internostêm grau k.

• Uma árvore binária é uma árvore k-ária com k = 2.

• Em uma árvore posicional, os filhos de um nó são rotuladoscomo inteiros distintos.

• Árvore k-ária é uma árvore posicional onde os filhos com rótulos maiores do que k são ausentes.

• Árvore k-ária completa é uma árvore k-ária onde todas as folhas têm a mesma profundidade e todos os nós internostêm grau k.

• Uma árvore binária é uma árvore k-ária com k = 2.

O número de nós internos de uma árvore k-ária completa é kh

– 1/ k - 1, onde h é a altura da árvore.


Aplicação: Árvores de Expressões

•Seja a expressão (a+b*c)+((d*e+f)*g):–Folhas são operandos.–Nós internos são operadores.

•Seja a expressão (a+b*c)+((d*e+f)*g):–Folhas são operandos.–Nós internos são operadores.


Árvores de Expressões

• Caminhamento em ordem:– produz expressão na notação infixa.

• Caminhamento em ordem:– produz expressão na notação infixa.

((a+(b*c))+(((d*e)+f)*g))

38


Árvores de Expressões

• Caminhamento em pós-ordem:– produz expressão na notação pósfixa.

• Caminhamento em pós-ordem:– produz expressão na notação pósfixa.

Expressão pósfixa:abc*+de*f+g*+


Árvore Binária de Pesquisa - ABP

• Árvore binária em que cada nó tem uma chave que não é menor do que as chaves dos nós de sua sub-árvore esquerda e não é maior do que as chaves dos nós da sub-árvore direita.

• Árvore binária em que cada nó tem uma chave que não é menor do que as chaves dos nós de sua sub-árvore esquerda e não é maior do que as chaves dos nós da sub-árvore direita.

ABP Não é ABP


Heap Binário

• Árvore binária com duas propriedades:– Estrutura: árvore binária quase completa. O último nível

pode não ser completado.– Ordem: todo filho é maior (ou igual) do que o pai.

• Árvore binária com duas propriedades:– Estrutura: árvore binária quase completa. O último nível

pode não ser completado.– Ordem: todo filho é maior (ou igual) do que o pai.

06

14

78 18

81 7791

45

5347

6484 9983


Implementação de Heap Binário

• Usar um array:– Parent(i) = ⎣i/2⎦– Left(i) = 2i– Right(i) = 2i + 1

• Usar um array:– Parent(i) = ⎣i/2⎦– Left(i) = 2i– Right(i) = 2i + 1

06

14

78 18

81 7791

45

5347

6484 9983

1

2 3

4 5 6 7

8 9 10 11 12 13 14


Inserção em Heap Binário

• Manter propriedades de ordem e estrutura.• Inserir no slot livre e depois procurar lugar correto.

• Manter propriedades de ordem e estrutura.• Inserir no slot livre e depois procurar lugar correto.

06

14

78 18

81 7791

45

5347

6484 9983 42 Próximo slot livre



06

14

78 18

81 7791

45

5347

6484 9983 42

Trocar com o pai, se necessário

39



06

14

78 18

81 7791

45

4247

6484 9983 53



06

14

78 18

81 7791

42

4547

6484 9983 53

Propriedade de ordem OK!!



06

14

78 18

81 7791

42

4547

6484 9983 53


Remoção em Heap Binário

• Manter propriedades de ordem e estrutura.• Sempre remove o menor elemento.


06

14

78 18

81 7791

42

4547

6484 9983 53





06

14

78 18

81 7791

42

4547

6484 9983 53





53

14

78 18

81 7791

42

4547

6484 9983 06

40





53

14

78 18

81 7791

42

4547

6484 9983





14

53

78 18

81 7791

42

4547

6484 9983





14

18

78 53

81 7791

42

4547

6484 9983

Propriedade de ordem OK!!





14

18

78 53

81 7791

42

4547

6484 9983


Aplicação em Ordenação: HeapSort

• Inserir N itens no heap.• executar N operações de remoção.• O(N log N).• Não é necessário armazenamento extra.

• Inserir N itens no heap.• executar N operações de remoção.• O(N log N).• Não é necessário armazenamento extra.


Teoria dos Grafos

Árvore de Cobertura Mínima

41


Árvore de Cobertura - Introdução

• Problema 1: Os pinos de uma placa de circuito impressodevem ser conectados com a menor quantidade de fio.• Problema 1: Os pinos de uma placa de circuito impressodevem ser conectados com a menor quantidade de fio.

• Problema 2: No sistema de abastecimento de água de Campina Grande, existem vários tanques de armazenamento e tratamento da água que vem do Açude de Boqueirão. Como interligar os tanques (em princípio, qulalquer par de tanques podeser interligado), de modo a garantir o correto abastecimento e que o custo seja mínimo?



Árvore de Cobertura - Introdução

• Problema 1: Os pinos de uma placa de circuito impressodevem ser conectados com a menor quantidade de fio.• Problema 1: Os pinos de uma placa de circuito impressodevem ser conectados com a menor quantidade de fio.



Os dois problemas acima são conhecidos como o problema da conexão mínima.Na Teoria dos Grafos é o problema de encontrar a árvore de cobertura (geradora) mínima para o grafo.


O que é uma árvore de cobertura?

• Uma árvore de cobertura de um grafo não dirigido G=(V,E) éum subgrafo de G que é uma árvore e contém todos osvértices de G.

• Uma árvore de cobertura de um grafo não dirigido G=(V,E) éum subgrafo de G que é uma árvore e contém todos osvértices de G.

Grafo Árvore de Cobertura


Árvore de cobertura

• Um grafo pode ter mais de uma árvore de cobertura?• Um grafo não conectado pode ter uma árvore de cobertura?



Árvore de cobertura




Como Encontrar uma Árvore de Cobertura?

• Para encontrar uma árvore de cobertura:– Se o grafo G não tem ciclos, G é uma árvore de

cobertura.– Se G tem ciclo, é necessário remover

recursivamente arestas (até achar uma árvore), mantendo o grafo conectado.

• Para encontrar uma árvore de cobertura:– Se o grafo G não tem ciclos, G é uma árvore de

cobertura.– Se G tem ciclo, é necessário remover

recursivamente arestas (até achar uma árvore), mantendo o grafo conectado.

42


Árvore de Cobertura Mínima (MST)

• O custo de um subgrafo (de um grafo não dirigidoponderado) é a soma dos pesos de suas arestas.

• Uma árvore de cobertura mínima de um grafo não dirigidoponderado é uma árvore de cobertura com menor custo.

• Um grafo pode ter mais de uma árvore de cobertura mínima?




b d

fgh

ia

c

e

4

8

2

10

21

78

4

9

67

1411


Árvore de Cobertura Mínima (MST)







b d

fgh

ia

c

e

4

8

2

10

21

78

4

9

67

1411


Como Encontrar uma MST?

Algoritmo Genérico

1. A ← ∅2. while A não é uma árvore de cobertura3. do encontre uma aresta (u,v) que é segura para A4. A ← A ∪ {(u,v)}5. return A

Algoritmo Genérico

1. A ← ∅2. while A não é uma árvore de cobertura3. do encontre uma aresta (u,v) que é segura para A4. A ← A ∪ {(u,v)}5. return A


Como Reconhecer uma Aresta Segura?

• Definir um corte no grafo, particionando o conjuntode vértices.

• Uma aresta cruza o corte se cada um dos vérticesque formam a aresta está em partição diferente.

• O corte deve respeitar A. Isso acontece se nenhuma aresta de A cruza o corte.

• A aresta segura é aquela de menor peso que cruza o corte.

• Definir um corte no grafo, particionando o conjuntode vértices.

• Uma aresta cruza o corte se cada um dos vérticesque formam a aresta está em partição diferente.

• O corte deve respeitar A. Isso acontece se nenhuma aresta de A cruza o corte.

• A aresta segura é aquela de menor peso que cruza o corte.


Aresta Segura

b d

fgh

ia

c

e

4

8

2

10

21

78

4

9

67

1411


Algoritmos para Encontrar MST

Kruskal: Encontra a aresta segura e adiciona a árvore de cobertura que está sendo formada. A nova aresta não devenecessariamente ter um dos vértices na árvore que estásendo formada. Ou seja, uma floresta pode existir antes daMST ter sido encontrada.

Prim: Encontra a aresta segura e um dos vérticesnecessariamente deve pertencer a árvore que está sendoconstruída. Sempre existe uma única árvore parcial.

Kruskal: Encontra a aresta segura e adiciona a árvore de cobertura que está sendo formada. A nova aresta não devenecessariamente ter um dos vértices na árvore que estásendo formada. Ou seja, uma floresta pode existir antes daMST ter sido encontrada.

Prim: Encontra a aresta segura e um dos vérticesnecessariamente deve pertencer a árvore que está sendoconstruída. Sempre existe uma única árvore parcial.

43


Algoritmo de Kruskal

1. A ← ∅2. for cada vértice v ∈ V[G]3. do Make-Set(v)4. Ordene as arestas de E (ordem crescente por peso w)5. ∀ edge (u,v) ∈ E, (considerando a ordem)6. if Find-Set(u) ≠ Find-Set(v)7. then A ← A ∪ {(u,v)}8. Union(u,v)9. return A

1. A ← ∅2. for cada vértice v ∈ V[G]3. do Make-Set(v)4. Ordene as arestas de E (ordem crescente por peso w)5. ∀ edge (u,v) ∈ E, (considerando a ordem)6. if Find-Set(u) ≠ Find-Set(v)7. then A ← A ∪ {(u,v)}8. Union(u,v)9. return A


Algoritmo de Prim

1. for cada vértice u ∈ V[G]2. do chave[u] ← ∞ // chave[u] é o custo de u para vértice da árvore

3. π[u] ← NIL4. chave[r] ← 0 // r é a raiz da árvore

5. Q ← V[G] // Q contém todos os vértices que ainda não estão na árvore

6. while Q ≠ ∅7. do u ← Extract-Min[Q]8. for cada v ∈ Adj[u]9. do if v ∈ Q ∧ w(u,v) < chave[v]10. then π[v] ← u11. chave[v] ← w(u,v)

1. for cada vértice u ∈ V[G]2. do chave[u] ← ∞ // chave[u] é o custo de u para vértice da árvore

3. π[u] ← NIL4. chave[r] ← 0 // r é a raiz da árvore

5. Q ← V[G] // Q contém todos os vértices que ainda não estão na árvore

6. while Q ≠ ∅7. do u ← Extract-Min[Q]8. for cada v ∈ Adj[u]9. do if v ∈ Q ∧ w(u,v) < chave[v]10. then π[v] ← u11. chave[v] ← w(u,v)


Teoria dos Grafos

Planaridade de Grafos


Planaridade em Grafos

• Estudos de aspectos da topologia de grafos:– Grafos planares– Coloração de grafos

• Problema das 3 casas/3 serviços• Problema de coloração de mapas• Utilidade prática

• Estudos de aspectos da topologia de grafos:– Grafos planares– Coloração de grafos

• Problema das 3 casas/3 serviços• Problema de coloração de mapas• Utilidade prática


Conceitos Básicos

• Grafo planar• Grafo plano• K4 é planar?

• Grafo planar• Grafo plano• K4 é planar?


Conceitos Básicos

• Um grafo plano divide o plano em várias regiões.• Uma delas é chamada região externa.• Cada aresta deve fazer parte da borda de alguma

região.

• Um grafo plano divide o plano em várias regiões.• Uma delas é chamada região externa.• Cada aresta deve fazer parte da borda de alguma

região.

44


Conceitos Básicos

a

bc d

4 regiões:R1: ac,cb,baR2: ab, bd,daR3: bc, cd, dbR4: ac, cd,da (externa)

a

bc d

a

b

c dTeoria dos Grafos – 2007.2 © Jorge Figueiredo, DSC/UFCG

• Uma árvore determina uma única região.• Toda aresta da árvore é parte da borda desta região.• Uma árvore determina uma única região.• Toda aresta da árvore é parte da borda desta região.

a

b

c

d

e


• Para o grafo plano abaixo indique:– Quantidade de regiões.– Conjunto de arestas de cada borda.– A região externa.

• Para o grafo plano abaixo indique:– Quantidade de regiões.– Conjunto de arestas de cada borda.– A região externa.

a

b

c

d

e

f

g


Fórmula de Euler

• Grafos planares x Poliedros.• Grafos planares x Poliedros.

TEOREMA: Seja G um grafo plano com V vértices, E arestas e R regiões. Então V – E + R = 2.


Grafos Não-Planares

• K3,3 é não-planar.– Prova por construção.– Prova por indução.

• K5 é não-planar.– Prova por construção.

• K3,3 é não-planar.– Prova por construção.– Prova por indução.

• K5 é não-planar.– Prova por construção.


TEOREMA: Seja G um grafo planar com V 3 vérticese E arestas.Então E 3V - 6.

45


Teorema de Kuratowski

• Importância do K3,3 e K5 para descobrir se um grafo é ou não planar.– Nenhum grafo que contém um destes grafos como

subgrafo não pode ser planar.– Nenhum grafo obtido através do K3,3 e K5 pela

simples adição de vértices às arestas não pode ser planar.

• Importância do K3,3 e K5 para descobrir se um grafo é ou não planar.– Nenhum grafo que contém um destes grafos como

subgrafo não pode ser planar.– Nenhum grafo obtido através do K3,3 e K5 pela

simples adição de vértices às arestas não pode ser planar.


DEFINIÇÃO: Dois grafos são homeomórficos se e somente sese eles podem ser obtidos a partir do mesmo grafo pela adição devértices (necessariamente de grau 2) às arestas.


TEOREMA (Kuratowski): Um grafo é planar se e somente seele não tem subgrafo homeomórfico a K

5 e K

3,3.


Teoria dos Grafos

Coloração em Grafos



• Qual o número mínimo de cores que devemos usar para colorir os estados do mapa do Brasil, com a restrição de que estados vizinhos não podem ter a mesma cor?

– Relação com o problema de colorir vértices de um grafo.– O Teorema das 4 Cores, provado em 1976, se constitui em um dos resultados mais importantes da matemática no Século XX. (permaneceu sem solução desde 1852)

• Aplicação em muitos problemas práticos.

• Qual o número mínimo de cores que devemos usar para colorir os estados do mapa do Brasil, com a restrição de que estados vizinhos não podem ter a mesma cor?

– Relação com o problema de colorir vértices de um grafo.– O Teorema das 4 Cores, provado em 1976, se constitui em um dos resultados mais importantes da matemática no Século XX. (permaneceu sem solução desde 1852)

• Aplicação em muitos problemas práticos.



• Uma coloração de um grafo é uma atribuição de cores aos vértices, de modo que vértices adjacentestenham cores distintas.

• Um grafo G tem k-coloração se ele pode ser coloridocom k cores.

• Se G tem k-coloração mas não pode ter (k-1)-coloração:– O número cromático de G é k.– G é k-cromático.– χ(G) = k .

• Uma coloração de um grafo é uma atribuição de cores aos vértices, de modo que vértices adjacentestenham cores distintas.

• Um grafo G tem k-coloração se ele pode ser coloridocom k cores.

• Se G tem k-coloração mas não pode ter (k-1)-coloração:– O número cromático de G é k.– G é k-cromático.– χ(G) = k .

46






Alguns Cenários Interessantes

• χ(G) = 1. O que isso significa?• χ(Kn) = ?• χ(G) = 2. Quando isso ocorre?

• χ(G) = 1. O que isso significa?• χ(Kn) = ?• χ(G) = 2. Quando isso ocorre?


Alguns Cenários Interessantes

• χ(G) = 1. Podemos afirmar que o grafo G não tem arestas.

• χ(Kn) = n. Isso implica dizer que podemos ternúmeros cromáticos grandes.

• χ(G) = 2. Se e somente se é bipartido. E no caso de uma árvore?

• χ(G) = 1. Podemos afirmar que o grafo G não tem arestas.

• χ(Kn) = n. Isso implica dizer que podemos ternúmeros cromáticos grandes.

• χ(G) = 2. Se e somente se é bipartido. E no caso de uma árvore?


Mais considerações

• Não é possível garantir que tipos de grafos são 3-cromáticos.

• Se um grafo tem n vértices, seu número cromáticonão pode ser maior do que n.

• Se Kr é subgrafo de um grafo G, o número cromáticonão pode ser menor do que r.

• Não é possível garantir que tipos de grafos são 3-cromáticos.

• Se um grafo tem n vértices, seu número cromáticonão pode ser maior do que n.

• Se Kr é subgrafo de um grafo G, o número cromáticonão pode ser menor do que r.


47


Alguns Teoremas Úteis

• Se G é um grafo e ∆ é o maior grau de seus vértices, então G tem (∆ + 1)-coloração.

• Se G é um grafo conectado que não é completo, e se o maior grau de seus vértices é ∆ (≥ 3), então G tem (∆)-coloração.

• Todo grafo planar pode ter 5-coloração.• Appel e Hasken provaram em 1976 que todo grafo

planar admite 4-coloração.• Como determinar o número cromático de um grafo?

• Se G é um grafo e ∆ é o maior grau de seus vértices, então G tem (∆ + 1)-coloração.

• Se G é um grafo conectado que não é completo, e se o maior grau de seus vértices é ∆ (≥ 3), então G tem (∆)-coloração.

• Todo grafo planar pode ter 5-coloração.• Appel e Hasken provaram em 1976 que todo grafo

planar admite 4-coloração.• Como determinar o número cromático de um grafo?


Teoria dos Grafos – 2007.2 © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos – 2007.2 © Jorge Figueiredo, DSC/UFCG


Exercício 1

1. Uma companhia manufatura os produtos químicos C1, C2, … Cn. Alguns destes produtos podem explodir se colocados em contato com outros. Como precaução contra acidentes, a companhia quer construir k armazéns para armazenar os produtos químicos de tal forma que produtos incompatíveis fiquem em armazéns diferentes. Qual é o menor número k de armazéns que devem ser construídos? Como resolver este problema com a ajuda da teoria dos Grafos?

1. Uma companhia manufatura os produtos químicos C1, C2, … Cn. Alguns destes produtos podem explodir se colocados em contato com outros. Como precaução contra acidentes, a companhia quer construir k armazéns para armazenar os produtos químicos de tal forma que produtos incompatíveis fiquem em armazéns diferentes. Qual é o menor número k de armazéns que devem ser construídos? Como resolver este problema com a ajuda da teoria dos Grafos?


Exercício 2

1. Emissoras de televisão vão ser instaladas em estações baseadas em nove cidades de nosso estado (cidades A, B, ..., I). As regulamentações do setor de telecomunicações indicam que uma mesma emissora não pode ser instalada em duas cidades com distância inferior a 150Km. Considere a tabela abaixo que indica as distâncias entre as cidades. Qual o menor número de emissoras para contemplar as nove cidades? Utilize a teoria dos grafos para resolver este problema e justificar a sua resposta.

1. Emissoras de televisão vão ser instaladas em estações baseadas em nove cidades de nosso estado (cidades A, B, ..., I). As regulamentações do setor de telecomunicações indicam que uma mesma emissora não pode ser instalada em duas cidades com distância inferior a 150Km. Considere a tabela abaixo que indica as distâncias entre as cidades. Qual o menor número de emissoras para contemplar as nove cidades? Utilize a teoria dos grafos para resolver este problema e justificar a sua resposta.

48


Teoria dos Grafos

Fluxo em Redes


Introdução

• Considere a seguinte situação modelada por um grafo:– Cada arco representa uma rua de mão única.– O peso de cada arco indica o maior fluxo possível ao

longo da rua (veículos/hora).• Qual o maior número possível de veículos que pode viajar de

v a w em uma hora?

• Considere a seguinte situação modelada por um grafo:– Cada arco representa uma rua de mão única.– O peso de cada arco indica o maior fluxo possível ao

longo da rua (veículos/hora).• Qual o maior número possível de veículos que pode viajar de

v a w em uma hora?

v

x

z

wy3

4

2

2

1

4

4

1 2


Rede (de fluxo)

• Uma rede (de fluxo) G = (V, E) é um grafo dirigido em que cada aresta (u, v) ∈ E tem um valor (não-negativo) capacidade c(u,v). Se (u, v) ∉ E, assume-se que c(u,v) = 0.

• Uma rede possui dois vértices especiais: fonte e sorvedouro.• ∀v ∈ V, assume-se que existe um caminho entre a fonte e

sorvedouro que passa por v.• O grafo é, portanto, conectado e |E| ≥ |V| - 1 .

• Uma rede (de fluxo) G = (V, E) é um grafo dirigido em que cada aresta (u, v) ∈ E tem um valor (não-negativo) capacidade c(u,v). Se (u, v) ∉ E, assume-se que c(u,v) = 0.

• Uma rede possui dois vértices especiais: fonte e sorvedouro.• ∀v ∈ V, assume-se que existe um caminho entre a fonte e

sorvedouro que passa por v.• O grafo é, portanto, conectado e |E| ≥ |V| - 1 .


v x

t

13

12

14

2016

4

7s

zy

10

9

4


Fluxo em Rede

• Sejam um grafo G = (V, E), a função capacidade c, uma fonte s e um sorvedouro t. O fluxo em G é uma função f: V×V → REAIS que satisfaz às seguintes propriedades:1. Restrição de capacidade: ∀u,v ∈ V, f(u,v) ≤ c(u,v).2. Simetria: ∀u,v ∈ V, f(u,v) = -f(v,u).3. Conservação do fluxo: ∀u ∈ V – {s, t}, ∑v∈V f(u, v) = 0.

• A quantidade f(u,v) (positiva ou negativa) indica o fluxo da rede a partir do vértice u até o vértice v.

• O fluxo total da rede é |f| = ∑v∈V f(s,v).

• Sejam um grafo G = (V, E), a função capacidade c, uma fonte s e um sorvedouro t. O fluxo em G é uma função f: V×V → REAIS que satisfaz às seguintes propriedades:1. Restrição de capacidade: ∀u,v ∈ V, f(u,v) ≤ c(u,v).2. Simetria: ∀u,v ∈ V, f(u,v) = -f(v,u).3. Conservação do fluxo: ∀u ∈ V – {s, t}, ∑v∈V f(u, v) = 0.

• A quantidade f(u,v) (positiva ou negativa) indica o fluxo da rede a partir do vértice u até o vértice v.

• O fluxo total da rede é |f| = ∑v∈V f(s,v).


v x

t

8/13

12/12

11/14

15/2011/16

4/4

7/7s

zy

10

4/9

1/4

49


• |f| = 19.• Apenas os fluxos positivos são mostrados.• Se f(u,v) > 0, mostramos f(u,v)/c(u,v). Caso contrário

mostramos apenas a capacidade.• Pode ser generalizado para redes com múltiplas fontes e

sorvedouros.• Um dos problemas é encontrar o fluxo máximo.

• |f| = 19.• Apenas os fluxos positivos são mostrados.• Se f(u,v) > 0, mostramos f(u,v)/c(u,v). Caso contrário

mostramos apenas a capacidade.• Pode ser generalizado para redes com múltiplas fontes e

sorvedouros.• Um dos problemas é encontrar o fluxo máximo.


Redes Residuais

• Sejam uma rede e um fluxo. Uma rede residual é uma rede com os arcos da rede original que comportam mais fluxo.

• Sejam um grafo G = (V, E), a função capacidade c, um fluxo f, uma fonte s e um sorvedouro t:– Capacidade residual de (u,v):

• cf(u,v) = c(u,v) – f(u,v).• A rede residual induzida por f é Gf = (V, Ef), em que

– Ef = {(u,v) ∈ V×V : cf(u,v) >0}.

• Sejam uma rede e um fluxo. Uma rede residual é uma rede com os arcos da rede original que comportam mais fluxo.

• Sejam um grafo G = (V, E), a função capacidade c, um fluxo f, uma fonte s e um sorvedouro t:– Capacidade residual de (u,v):

• cf(u,v) = c(u,v) – f(u,v).• A rede residual induzida por f é Gf = (V, Ef), em que

– Ef = {(u,v) ∈ V×V : cf(u,v) >0}.


Rede Residual (exemplo)

v x

t8

12

11

15

5

4

7s

zy

11

4

3

11

5

5

3

5


Caminho Expandível

• Seja uma rede G = (V, E) e um fluxo f , um caminho expandível p é um caminho de s para t na rede residual Gf.

• A capacidade residual de um caminho expandível é definida como: – cf(p) = min{cf(u,v) : (u,v) ∈ p}.

• Seja uma rede G = (V, E) e um fluxo f , um caminho expandível p é um caminho de s para t na rede residual Gf.

• A capacidade residual de um caminho expandível é definida como: – cf(p) = min{cf(u,v) : (u,v) ∈ p}.


Caminho Expandível (exemplo)

v x

t8

12

11

15

5

4

7s

zy

11

4

3

11

5

5

3

5


O Método de Ford-Fulkerson

• Como determinar o fluxo máximo?– Utilizar os conceitos de grafo residual e caminho

expandível.

• Como determinar o fluxo máximo?– Utilizar os conceitos de grafo residual e caminho

expandível.

BFS(G, s, t)for ∀e ∈ E[G] do

fluxo[e] ← 0

while exisitr um caminho expandível p doaumentar f ao longo de p

return f

50


Cortes

• Um corte é uma partição de V em S e T = V – S, emque s ∈ S e t ∈ T

• O fluxo da rede (f(S,T)) através do corte é a soma dos fluxos f(u,v), em que u ∈ S e v ∈ T

• A capacidade (c(S,T)) do corte é a soma dascapacidades c(u,v), em que u ∈ S e v ∈ T

• Corte mínimo – um corte com a menor capacidade• |f|= f(S,T)

• Um corte é uma partição de V em S e T = V – S, emque s ∈ S e t ∈ T

• O fluxo da rede (f(S,T)) através do corte é a soma dos fluxos f(u,v), em que u ∈ S e v ∈ T

• A capacidade (c(S,T)) do corte é a soma dascapacidades c(u,v), em que u ∈ S e v ∈ T

• Corte mínimo – um corte com a menor capacidade• |f|= f(S,T)


v x

t

12/12

11/14

15/2011/16

4/4

7/7s

zy

104/9

1/4

8/13

S T


Teorema do Fluxo Máximo-Corte Mínimo

• Se f é o fluxo de G, as seguintes condições sãoequivalentes:1. f é um fluxo máximo de G2. A rede residual Gf não contém caminhos

expandíveis3. |f| = c(S,T) para algum corte (S,T) de G

• Se f é o fluxo de G, as seguintes condições sãoequivalentes:1. f é um fluxo máximo de G2. A rede residual Gf não contém caminhos

expandíveis3. |f| = c(S,T) para algum corte (S,T) de G


Teoria dos Grafos

Emparelhamento


Introdução

• Conjunto de arestas M ⊆ E, em que nenhum vértice éincidente a mais de uma aresta.

• Emparelhamento Maximal– Nenhuma aresta e, com M ∪ {e} também formando

um emparelhamento.• Emparelhamento Máximo

– Emparelhamento com o maior |M| possível.

• Emparelhamento Perfeito

– |M| = n/2: cada vértice é incidente a alguma arestade M.

• Emparelhamento com custo mínimo: cada aresta tem um custo associado.

• Conjunto de arestas M ⊆ E, em que nenhum vértice éincidente a mais de uma aresta.

• Emparelhamento Maximal– Nenhuma aresta e, com M ∪ {e} também formando

um emparelhamento.• Emparelhamento Máximo

– Emparelhamento com o maior |M| possível.

• Emparelhamento Perfeito

– |M| = n/2: cada vértice é incidente a alguma arestade M.

• Emparelhamento com custo mínimo: cada aresta tem um custo associado.


Introdução

• Principais problemas:– Seja um grafo G, encontrar:

• Emparelhamento Maximal: fácil (algoritmo guloso)• Emparelhamento Máximo:

– Não é fácil encontrar em tempo polinomial.– Caso mais simples é no caso de grafos bipartidos.

• Emparelhamento perfeito:– Caso especial de emparelhamento máximo

• Aplicações:– Atribuições pessoais: tarefas e competências.– Escalonamento.– Seleção de adversários em competições esportivas.

• Principais problemas:– Seja um grafo G, encontrar:

• Emparelhamento Maximal: fácil (algoritmo guloso)• Emparelhamento Máximo:

– Não é fácil encontrar em tempo polinomial.– Caso mais simples é no caso de grafos bipartidos.

• Emparelhamento perfeito:– Caso especial de emparelhamento máximo

• Aplicações:– Atribuições pessoais: tarefas e competências.– Escalonamento.– Seleção de adversários em competições esportivas.

51


Emparelhamento em Grafos Bipartidos

1 2 3

a b c

X

Y

Vértices emparelhados: 2, 3, a, b.Vértices não-emparelhados: 1, c. É um emparelhamento maximal?


Emparelhamento em Grafos Bipartidos

1 2 3

a b c

X

Y

Emparelhamento máximo.Emparelhamento perfeito.


Como encontrar um emparelhamento máximo?

• Utilizar o método de Ford-Fulkerson para fluxo em rede.• A idéia é determinar um fluxo em rede, em que os fluxos

correspondem aos emparelhamentos.• Definir a rede correspondente G’= (V’, E’), a partir do grafo

bipartido G= (L ∪ R, E):– V’= V ∪ {s, t}.– E’= {(s,u): u ∈ L} ∪ {(u,v): u ∈ L, v ∈ R, (u,v) ∈ E}∪ {(v,t): v ∈ R}

• Assinalar peso 1 para cada aresta em E’.

• Utilizar o método de Ford-Fulkerson para fluxo em rede.• A idéia é determinar um fluxo em rede, em que os fluxos

correspondem aos emparelhamentos.• Definir a rede correspondente G’= (V’, E’), a partir do grafo

bipartido G= (L ∪ R, E):– V’= V ∪ {s, t}.– E’= {(s,u): u ∈ L} ∪ {(u,v): u ∈ L, v ∈ R, (u,v) ∈ E}∪ {(v,t): v ∈ R}

• Assinalar peso 1 para cada aresta em E’.


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte

52


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Exemplo

1 2 3 4 5 6

sorvedouro

a b c d e f

fonte


Excercício

1

2

3

a

b

c

d

e

4

Documents

Apresentação do Curso - dsc.ufcg.edu.brabrantes/CursosAnteriores/TG072/slidesTG072.pdf · As Pontes de Königsberg ... – Diminua o ritmo de apresentação dos slides, se for o