Teoria Dos Grafos - Aula 14

Prof. Dario José Aloise

Teoria dos GrafosEstudo de Problemas Clássicos

Mossoró, 19 de janeiro de 2015

DEPARTAMENTO DE INFORMÁTICA

PROBLEMAS CLÁSSICOS

Árvore Geradora Mínima

Caminho mais Curto

Matching ou emparelhamento

Coloração

Caixeiro Viajante

Roteamento de Veículos

Emparelhamento( Matching )

MATCHING OU EMPARELHAMENTO

Definição: Um matching em um grafo G é um conjunto de arestas que não

formam loops e que não compartilham vértices entre si.

Exemplo:

Um vértice incidente às arestas de um matching M é dito saturado por M.

Um matching perfeito de G satura todos os vértices de G.

MATCHING OU EMPARELHAMENTO

O tamanho de um matching M é igual a quantidade de arestas de M.

Um matching M de um grafo G é maximal se toda aresta que não participa

de M é incidente a alguma aresta em M.

Se M for o matching de maior cardinalidade de G então ele é chamado

matching máximo.

MATCHING OU EMPARELHAMENTO Um caminho alternante em um matching M é um caminho cujas arestas alternam entre

aquelas que estão em M e aquelas que não estão em M.

Um caminho alternante, cujos vértices extremos não são saturados por M, é um

caminho de aumento de M.

Quando M possuir um caminho de aumento P podemos trocar as arestas deste

caminho, substituindo aquelas que não estão em M pelas que estão. Isto irá aumentar

em uma (1) unidade o tamanho do matching.

Observação: o matching máximo é caracterizado pela ausência de caminhos de

aumento.

MATCHING OU EMPARELHAMENTO

Matching Máximo X Matching Maximal

Um matching M é máximo se não existe um matching M' tal que |M‘ | > |M |.

A propósito, um matching M é maximal se não existe um matching M' do qual M

faça parte própria (portanto, M é maximal se não existe aresta a fora de M tal

que M+{a } também é um matching).

MATCHING OU EMPARELHAMENTO

Observação: A prova de ambos os teoremas pode ser encontrada em http://www.cos.ufrj.br/~celina/cos742/jai99.pdf

FUNDAMENTAÇÃO TEÓRICA

Teorema 1 (Berge, 1957): Um matching M tem cardinalidade máxima em G se

e somente se G não possui caminho M-aumentante.

Teorema 2 (Hall, 1956): Seja G um grafo bipartido com bipartição X, Y . Então

G admite matching que satura todo vértice de X se e somente se |N(S)| |S|,

para todo S X.

Corolário 1: Seja G um grafo bipartido com bipartição X , Y. Então G admite matching

perfeito se e somente se |X| = |Y | e |N(S)| |S|, para todo S X.

Corolário 2: Um grafo bipartido tem um matching perfeito se e somente se |N(S)| |S|,

para todo S V .

Matching Perfeito

Dado um grafo G= (V,E), o problema de matching é encontrar o matchingmáximo de G. Quando a cardinalidade do matching é V 2 , afirmamos que o matching é completo ou perfeito [PAPADIMITRIOU (1998)]. Isto é todos os vértices estão casados. Em grafos bipartidos G=(U,V,E), devemos ter V = U para que um matching perfeito possa existir.

Ref.: Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization: Algorithms and

Complexity, Publisher: Dover Publications; Unabridged edition ,1998. 9

MATCHING OU EMPARELHAMENTO

MATCHING OU EMPARELHAMENTO

PRINCIPAIS ALGORITMOS:

Algoritmo Húngaro (Grafos bipartidos sem pesos)

Algoritmo de Kuhn (Grafos bipartidos com pesos)

Algoritmo de Edmonds (Caso geral sem pesos)

Observação: Maiores detalhes sobre os algoritmos pode ser encontrado em:

http://www.cos.ufrj.br/~celina/cos742/jai99.pdf

MATCHING OU EMPARELHAMENTO

APLICAÇÕES:

Problema de atribuição de pessoal

Dados n funcionários e n posições numa empresa. Cada funcionário está qualificado

para uma ou mais posições. É possível atribuir uma posição a cada funcionário, de

modo que cada funcionário ocupe exatamente uma posição na empresa? O objetivo

é encontrar uma atribuição ou uma alocação que maximize a eficiência total dos

funcionários.

Problema dos casamentos

Dada uma matriz onde cada entrada é 0 ou 1, um conjunto de entradas é independente se

não temos duas entradas na mesma linha ou na mesma coluna. Pede-se encontrar um

conjunto independente de entradas de valor 1 que tem cardinalidade máxima. Podemos

interpretar as linhas da matriz como sendo rapazes e as colunas como sendo moças. Uma

entrada i, j com valor 1 seria o caso de rapaz e moça compatíveis. O objetivo é casar um

número máximo de casais compatíveis.

MATCHING OU EMPARELHAMENTO

APLICAÇÕES: Problema de construção de amostras

Um vendedor de brinquedos educativos possui em estoque brinquedos de várias

formas geométricas (cubos, pirâmides, etc.), cada qual fabricado em várias cores.

O vendedor quer carregar consigo o menor número de objetos tal que cada cor e

cada forma estejam representadas pelo menos uma vez.

Observação: Com base nesta aplicação pode-se provar a equivalência entre o

problema de cobertura de cardinalidade mínima e o problema de emparelhamento

de cardinalidade máxima.

OUTROS PROBLEMAS

Alocação de tarefas

Elaboração de Horários

K-servos

Empacotamento

Clique máxima

Cobertura de Vértices

OTIM-SPT

Um exemplo de Aplicação

Otimização do Corte do Layout : Ênfase na Indústria de Confecções

MCC - Teoria dos Grafos 14

UM EXEMPLO DE APLICAÇÃO

Otimização do Corte do Layout na

Indústria de Confecções

Objetivo

Encontrar uma seqüência ótima de corte daspeças do enfesto, de forma a minimizar odeslocamento total (ou percurso) do braçomecânico (robô) que efetua o corte e atendero mais rápido possível o setor de montagem.

Processo de Produção

Exemplo de enfesto...

Problema do Encaixe

Um exemplo de Layout

Figura sem os rótulos

Aplicação de Grafos

Problema de Percurso:

O início dos Problemas de Roteamento em Arcos

Leonhard Euler (1736) - Publicou o primeiro artigo em grafos

C

As pontes de Königsberg e o multigrafo associado.

BA

D

Construindo um Grafo Euleriano

Teorema - O número de vértices ímpares de qualquer grafo conexo é par.

Edmonds & Johnson (1973) propôs

Algoritmo 1-Matching

Complexidade: O ( n³ )

Problema de Matching

Problema do Carteiro Chinês:===

O Problema do Carteiro Chinês é um problema de roteamento

onde se pretende achar um percurso fechado (circuito) de

comprimento mínimo que passa por cada aresta de um grafo pelo

menos uma vez.=====================================

(b)

11

22

33

4455

66

88 77

Formulação Matemática do PCC:

,

. :

0 ( 1, )

1 ,

0 e inteiro ,

ij ij

i V j V

ij ji

j V j V

ij ji

ij

Min Z c x i j

s a

x x i V

x x ij E

x ij E

cij = custo de percorrer a aresta ij ;

xij = número de vezes que a aresta ij é percorrida de i para j.

Inter-relacionamento entre Matching e o PCC:

Algoritmo do Carteiro Chinês [Edmonds (1973)

Matching Perfeito

Abordagem Exata:

Continuação:

Formulação Matemática do Problema do Layout :

1

1

1 1 1 1

( )( )

( )( )

{ , }

. . :

0 , p/

( ) ( ) 0 , p/

1 , ,

, {0,1}

O O

O O

V VV V

ij ij rs rs

i j r s

ik kj E

j ki k

ik rk kj ks O

r V j k s Vi k

ij ji

ij ij

Min Z l x d y i j r s

s a

x x k V

x y x y k V

x x i j V

x y

Abordagem Heurística:

• O método exato embora forneça a solução ótimado problema quanto a minimizar o percurso(tempo) de corte das peças no layout, do pontode vista prático,não satisfaz a condição deatender o mais rápido possível o setor demontagem.

• O objetivo inclui, portanto, a prioridade de cortar peças inteiras com a finalidade acima.

• O problema passa agora a ser semelhante ao do Carteiro Rural, o qual é NP-difícil.

Heurísticas Propostas:

HEURÍSTICA I

(sem prioridade de aresta ou vértice)

Dados iniciais

1. Posição original do braço mecânico,

2. LAYOUT desenhado, com dimensões e referências,

3. GRAFO ASSOCIADO;

ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO

Iniciar de um vértice qualquer no grafo G=(V,E,c), denominando-o de ATIVO.

ETAPA 1 – LAÇO DE CONTINUIDADE

ENQUANTO existir vértice de grau

Ø FAÇA

1. Percorrer cortando a maior aresta associada ao vértice ATIVO

1. SE encontrar um vértice de grau Ø, ENTÃO

Procurar o vértice ativo (vértice com alguma aresta associada) mais

próximo ao vértice de grau Ø (zero) .

SENÃO FINALIZE.

FIM DO ENQUANTO

HEURÍSTICA 2

(com prioridade: vértice denso por arestas)

Dados iniciais

Posição original do braço mecânico,

LAYOUT desenhado, com dimensões e referências,

GRAFO ASSOCIADO;

ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO

Iniciar de um vértice qualquer denso por arestas no grafo G=(V,E,c),

denominado de vértice ATIVO.

ETAPA 1 – LAÇO DE CONTINUIDADE

REPITA

ENQUANTO existir aresta em ATIVO FAÇA

Percorrer cortando uma aresta de maior custo associada ao vértice ATIVO.

Fixar ou tornar em evidência a figura (peça) de menor índice associada a

aresta citada.

Cortar a figura (peça) em evidência, totalmente

FIM DO ENQUANTO

Procurar por um vértice mais próximo, denominado-o de ATIVO (não

necessariamente percorrendo pelas arestas do Grafo – Problema do Carteiro

Rural).

ATÉ G=Ø;

HEURÍSTICA 3

(com prioridade: vértice denso por figuras)

Dados iniciais

Posição original do braço mecânico,

LAYOUT desenhado, com dimensões e referências,

GRAFO ASSOCIADO;

ETAPA 0 – PROCEDIMENTOS DE INICIALIZAÇÃO

Iniciar de um vértice qualquer denso, isto é, com um a quantidade razoável de

figuras (peças) associadas no grafo G=(V,E,c), denominando-o de ATIVO.

ETAPA 1 – LAÇO DE CONTINUIDADE

REPITA

ENQUANTO existir figura associada ao vértice ATIVO FAÇA

Percorrer cortando uma figura (peça), iniciando o corte pela aresta de maior

custo associada a ela.

SE existir mais de uma figura associada a essa aresta, ENTÃO

considerar em primeiro lugar aquela de menor índice.

SE grau(ATIVO) = 0 e existir figura parcialmente cortada, ENTÃO procurar

por um vértice mais próximo dentre aqueles pertencentes as figuras

associadas ao vértice ATIVO e continuar o percurso de corte a partir desse

novo vértice até que a figura fique totalmente cortada.

FIM DO ENQUANTO

SE grau (vértice ATUAL 0 ), ENTÃO faça ATUAL = ATIVO.

SENÃO procurar por um vértice de grau 0 mais próximo do vértice

atual.

ATÉ QUE G = Ø;

Pós-otimização:Caso 1 - O braço mecânico termina o procedimento de corte e volta ao ponto de partida (origem). Então

a solução ótima permanecerá como a do Carteiro Chinês sobre o grafo Euleriano. E o matching perfeito

de peso mínimo refletirá fielmente o deslocamento adicional mínimo do braço mecânico (robô).

Caso 2 - O robô ao terminar a última peça a ser cortada não retorna ao ponto de origem. Então

deveremos comparar e retirar a maior das arestas encontradas pelo matching perfeito de peso mínimo e

aquela maior aresta encontrada por um dos diversos matching maximais, mas de tal forma que a

contribuição para o deslocamento do robô fique a menor possível. Isto implica na seguinte formulação

matemática para esta situação de parada do robô:

1 2

1 2min maxiji i

ij

c i i

( *)c

Conclusões e Sugestões:

Esta pesquisa teve por mérito mostrar o quanto é

importante também o corte do Encaixe ou Layout do

enfesto na Indústria de confecções;

A verificação que o ótimo nem sempre é obtido através

do matching perfeito de peso mínimo;

A apresentação de algoritmos aproximativos polinomiais

para a resolução do problema na prática.

Como sugestão fica o desenvolvimento de um

trabalho que reconheça os pontos do grafo pelo simples

scanneamento do Encaixe.

Restrições:

a faca não pode furar o meio

a faca não pode voltar

bordas com restrições

os retalhos não podem ser cortados

há necessidade de priorizar peças no corte

há restrições para prender o enfesto

a faca não trabalha com grandes angulosidades

etc.

FIM

Reptiles, 1943. MC Escher (1898-1972).