XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
CIRCUITOS EULERIANOS COM RESTRIÇÕES DE CONVERSÃO
Hassan Sherafat – [email protected]
Departamento de Matemática – UFS, Campus Universitário, São Cristóvão, SE
Resumo. Nesse trabalho é abordado o problema de construção de Circuitos Eulerianos na
presença de restrições nos vértices. O estudo das propriedades de circuitos e sub-circuitos
eulerianos, bem como uma transformação no grafo, conduzem a um algoritmo eficiente que
encontra um circuito euleriano viável, ou detecta a sua inexistência.
Palavras-chave: Circuito Euleriano, Restrições de Conversão, Penalidades de Conversão,
Problema do Carteiro Chinês.
1.
INTRODUÇÃO
A construção de circuitos eulerianos é o passo final na solução do Problema do Carteiro
Chinês quando o grafo é transformado em euleriano, com acréscimo de cópias dos arcos. Tal
construção não é uma tarefa trivial quando existem restrições de conversão nos vértices.
Exemplos práticos destas restrições são as de trânsito nos cruzamentos das malhas urbanas.
Considera-se um grafo orientado conexo G = ( X , A) , onde X é o conjunto de vértices e
A o seu conjunto de arcos. G é um grafo euleriano se, e somente se, o grau de entrada é igual
ao grau de saída em todo vértice xi ∈ X . Um conjunto de circuitos C = {C1 , C2 ,L , Cn } em
que cada arco aparece uma única vez e, apenas em um dos circuitos, é chamado de Conjunto
de Sub-Circuitos Eulerianos. Se o conjunto tem um único circuito, ele é simplesmente
chamado de Circuito Euleriano. Um grafo que contém um circuito euleriano é dito unicursal.
Se aij , e a jk são dois arcos incidentes ao vértice j, e a seqüência aij , a jk não é permitida no
traçado do circuito euleriano, então a referida seqüência é denominada de uma Restrição de
Conversão atribuída ao vértice j. Um grafo com restrições nos vértices pode ser denotado por
G = ( X , A, R ) , onde R é o conjunto de pares de arcos que formam seqüências proibidas.
É fácil verificar que todo grafo euleriano é unicursal. Porém, se houver alguma restrição
de conversão nos vértices, o grafo pode não ser mais unicursal. Define-se um Circuito
Euleriano Viável, quando este satisfaz, também, todas as restrições nos vértices. Portanto os
termos grafo euleriano e grafo unicursal não são tidos como sinônimos neste trabalho.
O objetivo desse trabalho é abordar o problema de construção de circuitos eulerianos
sujeitos às restrições nos vértices, num grafo euleriano. A solução dada por Edmonds e
Johnson (1973), usando um procedimento de criação de arborescência em G, não funcionaria
na presença de tais restrições.
2. FORMULAÇÃO COM GRAFO LINHA
Uma possível formulação desse problema é através de grafo linha. Dado um grafo
euleriano G = ( X , A, R ) , onde R é o conjunto de pares de arcos que formam seqüências
proibidas, o Grafo Linha L(G) associado a G é obtido pela substituição de cada arco de G por
um vértice em L(G) (Christofides, 1975, Harary & Nash-Williams, 1965). Existe um arco
orientado do vértice k para 1 em L(G), se, e somente se, o par de arcos ak , al é uma seqüência
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
permitida de arcos em G (isto é, ak , al ∉ R ). Desta forma, um circuito euleriano viável em G
passa a ser um Circuito Hamiltoniano em L(G).
A figura 1 mostra um grafo euleriano G com o conjunto de seqüências proibidas
R={(d,c), (f,d)} e, o grafo L(G) correspondente.
Grafo G
Grafo L(G)
Figura 1
No exemplo acima, o circuito hamiltoniano a,c,d,e,f,b,a em L(G) corresponde a um
circuito euleriano viável em G. A construção de circuitos hamiltonianos constitui-se como um
caso particular do Problema do Caixeiro Viajante. Uma solução razoável de enumeração é
dada por Selby (1970) e Christofides (1975), a qual apresenta ineficiência quando tal circuito
não existe.
3. FORMULAÇÃO COMO UM PROBLEMA DE CIRCULAÇÃO
3.1. Decomposição de Vértices
Nesse trabalho é usada uma outra abordagem a partir de decomposição dos vértices do
grafo G = ( X , A, R ) . Cada vértice xi do grafo pode ser substituído por um Subgrafo Bipartido
Bi = ( Si , Ti , Pi ) , onde Si e Ti são conjuntos de vértices tais que sk ∈ Si , se, e somente se, o arco
ak ∈ A termina no vértice xi e, tl ∈ Ti , se, e somente se, o arco al ∈ A se inicia em xi . Pi é o
conjunto dos arcos, tal que pkl ∈ Pi , se, e somente se, (ak , al ) ∉ R (é uma seqüência permitida
em G). Por outras palavras, para cada arco ak em G são criados dois vértices sk e t k . O
próprio arco ak que ligava o vértice xi para x j (nesta ordem) em G, passa a conectar o
vértice t k a sk no grafo expandido.
O subgrafo bipartido Bi é completo se não houver nenhuma restrição de conversão para
o vértice xi . Com cada seqüência não-permitida imposta a xi o arco correspondente em Bi é
removido. A figura 2 mostra o exemplo de um vértice com seqüências (d,f), (d,c) e (a,b)
impedidas e, o subgrafo bipartido correspondente.
A decomposição de todo vértice do grafo em um subgrafo bipartido, transforma o grafo
G = ( X , A, R ) no grafo expandido GT = ( B, A ∪ P ) , onde B = {Bi } , P = {Pi } , e A é o mesmo
conjunto original de arcos, embora seus vértices terminais tenham sido decompostos. O grafo
GT permite abordar, de forma explícita as restrições nos vértices de G. Um circuito em GT
que use todos os arcos de A uma única vez, é um circuito euleriano viável em G. Tal circuito
em GT é denominado de Circuito Básico.
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
Um vértice x com restrições e o subgrafo bipartido correspondente.
Figura 2
Dados um grafo euleriano G = ( X , A, R ) e o grafo expandido correspondente
GT = ( B, A ∪ P) . Se existe um circuito euleriano viável em G, então existe circuito básico em
GT . Por conseguinte, é possível circular uma unidade de fluxo em todo arco ak ∈ A em GT ,
obedecendo à regra de continuidade. Isto sugere a formulação do problema de construção de
circuito euleriano como um de circulação em GT . Para isso bastaria fixar o limite inferior de
fluxo lk = 1 em todo arco ak ∈ A , e zero nos demais arcos em GT , e em seguida achar uma
circulação de custo mínimo, usando o método Out-of-kilter (Fulkerson, 1961). Os caminhos
de fluxo identificam alguns circuitos em GT . De fato, as seguintes situações podem ocorrer:
i - Um único circuito é construído. Como foi visto, este corresponde a um circuito
euleriano viável em G. Isto é, um circuito euleriano que satisfaz as restrições nos vértices;
ii - Um conjunto de n sub-circuitos eulerianos, n>1, é construído;
iii- Não há circulação viável em GT , portanto, não há nenhuma alternativa de construir
um conjunto de sub-circuitos eulerianos em G.
Na solução de circulação de custo mínimo o fluxo em alguns arcos poderá ser,
eventualmente, maior que uma unidade. Isto indica que o grafo original não continha nenhum
circuito euleriano, devido às restrições nos vértices. Porém, com a multiplicação de arcos,
conforme a solução de circulação poderá vir a ter tal circuito. Na situação (iii), não há circuito
euleriano, mesmo admitindo novas duplicações, no contexto da solução de um problema do
Carteiro Chinês em G. Isto, por força das restrições de conversão. A situação (ii) indica a
existência de uma circulação viável em GT , o que é apenas uma condição necessária (ver-se-á
mais adiante que não é suficiente) para que haja um circuito euleriano viável em G.
As situações (i) e (iii) são as extremas e que indicam a existência, ou a inexistência de
um circuito euleriano viável em G. A situação (ii) precisa ser estudada melhor.
3.2 Vértice Elo
Considere dois circuitos C1 e C2 que têm um vértice xi em comum, o qual é
representado pelo grafo bipartido Bi . Eliminando os vértices de Bi que não participam em C1
e C2 , se o restante for um sub-grafo bipartido completo, então xi é um Vértice Elo entre C1 e
C2 (Figura 3-a).
Um vértice é definido como Semi-Elo, se um dos arcos do elo, de C1 para C2 ou de C2
para C1 estiver ausente. Desta forma o semi-elo é orientado de um dos circuitos para o outro,
a depender do sentido do seu arco excedente. A figura 3-b mostra um semi-elo orientado de
C2 para C1 .
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
a) Vértice Elo
b) Vértice Semi-Elo
Figura 3
Teorema 1.
Dois circuitos C1 e C2 de um conjunto de sub-circuitos eulerianos podem ser unidos
num único circuito C = C1 ∪ C2 , se, e somente se, há um vértice elo entre eles.
Prova.
Considera-se a figura 3-a, onde os circuitos C1 e C2 têm um vértice elo em comum. Os
circuitos usam os arcos p11 e p22 , respectivamente. É obvio que a troca destes arcos pelos
arcos p12 e p21 uniria os dois circuitos num único circuito C.
Por outro lado, a única forma de unir dois circuitos (sem repetição dos arcos e sem usar
arcos dos outros circuitos) é a através de um vértice elo. Para provar isto, considere-se dois
circuitos C1 e C2 de um conjunto de sub-circuitos eulerianos. Se C1 e C2 são unificáveis em
um único circuito C, então devem ter pelo menos um vértice xi em comum, através do qual
possa se passar de C1 para C2 . Se xi não é elo, então deve ser pelo menos um semi-elo. Pois,se não for elo, nem semi-elo, não há como passar de C1 para C2 . Mais precisamente, xi deve
ser um semi-elo orientado de C1 para C2 . Como a união de C1 com C2 deve gerar um novo
sub-circuito euleriano, então deve haver pelo menos um outro semi-elo x j , orientado de C2
para C1 para completar o circuito. Dois semi-elos xi e x j dividem C1 e C2 em 4 cadeias
distintas: C1 = d1 ∪ d1′ e C2 = d 2 ∪ d 2′ (figura 4). Uma vez passando de C1 para C2 (usando
semi-elo xi ), então é usada uma das cadeias, por exemplo, a d 2 . Seja qual for a cadeia
subseqüente, mais adiante o circuito deve passar, obrigatoriamente, por d 2′ e como d 2′
termina novamente em xi e este não permite passagem de volta para C1 , então o circuito deve
passar novamente por d 2 , o que não é possível, uma vez que com a união os sub-circuitos
devem permanecer eulerianos. Logo, a única forma de unir dois sub-circuitos eulerianos C1 e
C2 é por intermédio de um vértice elo.
Desta forma, se dois sub-circuitos eulerianos têm um elo em comum, eles podem ser
unidos num único, com a simples mudança de casamento no vértice elo. A repetição desse
processo pode fundir diversos sub-circuitos em um único circuito.
Corolário.
Se num grafo euleriano existe um conjunto de n sub-circuitos eulerianos, n> 1, e se há
pelo menos um circuito que não possui nenhum elo com os demais circuitos, então o grafo
não é unicursal.
A prova é uma conseqüência imediata do Teorema 1, uma vez que tal circuito não pode
se unir a nenhum outro.
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
Figura 4
Teorema 2.
Suponha que um circuito C1 de um conjunto de sub-circuitos eulerianos não possui
nenhum vértice elo com os demais circuitos do conjunto, a não ser dois semi-elos com o
circuito C2 , os quais são contrariamente orientados entre C1 e C2 . É possível construir um
circuito contendo C1 e C2 com duplicação de partes de ambos os circuitos C1 e C2 .
Prova.
Suponha que C1 = d1 ∪ d1′ , onde d1 e d1′ são as cadeias delimitadas pelos semi-elos e,
analogamente, C2 = d 2 ∪ d 2′ . A figura 4 simboliza a situação. Uma vez que os semi-elos são
contrariamente orientados, é possível construir um circuito d contendo partes de ambos os
circuitos C1 e C2 . A priori existem 4 alternativas: d1 ∪ d 2 , d1 ∪ d 2′ , d1′ ∪ d 2 e d1′ ∪ d 2′ , dentre
elas apenas uma viável, obedecendo o sentido dos semi-elos. Para o exemplo da figura 4
d1′ ∪ d 2 .
Com a duplicação dos arcos em d têm-se 3 circuitos C1 , C2 e d , cuja união produz um
único circuito. Esta união é possível, pois a duplicação de d na verdade transforma ambos os
semi-elos em elos. Com isso, os três circuitos C1 , C2 e d passam a ser conectados por dois
elos e, portanto, pelo Teorema 1, os três podem ser transformados num único circuito. Para o
exemplo da figura 4, tal circuito é d 2 , d1′, d1 , d1′, d 2 , d 2′ .
Vale ressaltar que o Teorema 2 trata de semi-elos contrariamente orientados. Os
circuitos não seriam unificáveis, se ambos os semi-elos tivessem a mesma orientação. O
teorema pode ser reeditado para o caso em que diversos circuitos são interligados por semielos. O teorema a seguir é a generalização desta propriedade.
Teorema 3.
Suponha que os circuitos C1 , C2 ,L , Cm pertencem a um conjunto de sub-circuitos
eulerianos, tais que não possuem nenhum elo entre si, nem com os demais circuitos do
conjunto, a não ser por m semi-elos (ou mais) que conectam C1 a C2 (neste sentido), C2 a C3
, ..., Cm a C1 . Então é possível construir um circuito que contenha C1 , C2 ,L , Cm e mais
algumas duplicações dos arcos que pertencentes aos mesmos sub-circuitos.
Prova.
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
A prova deste teorema se dá nas mesmas condições do Teorema 2. Os arcos duplicados
formariam um circuito d que passaria por todos os semi-elos, contendo cadeias de cada um
dos circuitos C1 , C2 ,L , Cm . A duplicação do circuito d transformaria todos os semi-elos em
elos. Os m+1 circuitos ( C1 , C2 ,L , Cm , d) com m elos de interligação podem ser unidos num
único circuito, pelo Teorema 1.
Se num conjunto de sub-circuitos eulerianos não há elos, nem semi-elos que preencham
as condições dos Teoremas 2 e 3, então o grafo não contém nenhum circuito (euleriano ou
não) que contenha todos os arcos do grafo. Tal situação é ligada ao conceito de acessibilidade.
Um vértice xi é acessível por outro x j , se existe no grafo um caminho de xi a x j . Um grafo é
acessível, se qualquer vértice xi do grafo é acessível por qualquer outro. Na condição acima,
devido às restrições de conversão, uma parte do grafo se torna inacessível pelo resto.
É fácil verificar ainda a veracidade dos seguintes teoremas, embora sua demonstração é
omitida neste artigo:
Teorema 4
Uma condição necessária para que um grafo euleriano G, com restrições nos vértices,
seja unicursal é que o grafo GT associado a G seja acessível.
Teorema 5
Uma condição necessária e suficiente para que um grafo G, com restrições nos vértices,
possua um circuito contendo todos os seus arcos (com ou sem repetições), é que o grafo GT
associado a G seja acessível.
3.3. Algoritmo para a Construção de Circuitos Eulerianos
Como foi visto, o Teorema 1 fornece uma maneira prática de unir diversos sub-circuitos
eulerianos em um único, começando unir um circuito com outro que têm um elo em comum, e
depois ampliando o novo circuito, detectando um novo elo e, assim por diante. O processo
pode ter dois desfechos: ou todos os circuitos se uniriam num único circuito euleriano viável,
ou então, em determinado estágio de ampliação do circuito, não se encontraria nenhum vértice
elo para prosseguir, significando que o grafo não é unicursal.
Os Teoremas 2 e 3 estabelecem condições em que um grafo euleriano não é unicursal
(devido às restrições de conversão), mas que pode se tornar unicursal, admitindo novas
duplicações. Afirmam ainda, que tais duplicações ocorrem, obrigatoriamente, em circuitos
inteiros. Entretanto, eles não estabelecem um critério de escolha, quando o número de semielos é maior que o número de sub-circuitos. Por isso, seria difícil abordar as duplicações,
principalmente nas condições do Teorema 3.
Os teoremas 4 e 5 estabelecem as condições de inexistência de um circuito euleriano na
presença de restrições de conversão. Como foi visto, tais restrições podem gerar subgrafos
inacessíveis pelo resto do grafo.
O algoritmo descrito a seguir começa a partir de um grafo euleriano com restrições de
conversão associadas aos vértices e constrói um circuito euleriano viável, ou detecta a sua
inexistência.
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
Algoritmo
0. Dado o grafo euleriano G = ( X , A, R ) e o grafo expandido correspondente
GT = ( B, A ∪ P) . A cada arco ak ∈ A é associado um custo qk . Inicialize GT com o
limite inferior de fluxo igual a um para todo arco em A, e zero para os arcos dos subgrafos bipartidos P. O custo associado aos arcos em B é igual a zero.
1. Aplique o método Out-of-kilter para achar a circulação de custo mínimo em GT . Se
não há circulação viável, pare. Não há circuito euleriano viável em G.
2. Se o fluxo é maior que 1 em alguns arcos, então o grafo G não é unicursal, porém
pode ter um circuito euleriano admitindo acréscimos. Multiplique os arcos em GT
conforme a quantidade de fluxo adicional em cada arco.
3. Identifique o conjunto E de sub-circuitos eulerianos, conforme a solução de
circulação. Seja n o número de tais circuitos e C um dos sub-circuitos eulerianos.
3.1 Se n=1, pare. C é um circuito euleriano viável.
3.2 Encontre um vértice elo xk entre C e um outro Ci ∈ E . Se não existe nenhum Ci
possuindo elo com C, pare! O grafo não contém nenhum circuito euleriano.
3.3 Seja Bk o sub-grafo bipartido associado ao vértice elo xk . Faça C = C ∪ Ci a partir
de mudança de casamento em Bk . Faça n=n-1 e atualize o conjunto E. Volte ao passo
3.1.
4. Fim.
O algoritmo encontra, no passo 3.1, um circuito euleriano que satisfaz as restrições nos
vértices. Porém, em duas outras instâncias detecta a sua inexistência, com significados
diferentes; no passo 1 pode não haver tal circuito, devido a inacessibilidade de alguns vértices
do grafo por outros. No entanto, a ausência de um circuito euleriano viável no passo 3.2 pode
ser reavaliada, com a possibilidade de acréscimo de cópias de alguns arcos (em circuito), de
modo a transformar os semi-elos em elos. Tal possibilidade, também, é vinculada à
acessibilidade do grafo.
A acessibilidade de um grafo pode ser testado facilmente com a construção de uma
matriz de acessibilidade (Christofides 1975). Acrescentando tal teste ao inicio do algoritmo,
pode se certificar da natureza da inexistência do circuito euleriano.
O algoritmo é aplicável a grafos completamente orientados. Vale ressaltar que se o grafo
não for euleriano, os passos 1 e 2 do algoritmo o transformariam em euleriano. Se o grafo for
misto, isto é, alguns arcos orientados e outros não-orientados, o algoritmo poderá ser
combinado com um outro, descrito por Sherafat (1988), o qual constrói o grafo euleriano, a
partir de um grafo misto, por intermédio de uma rotina de "Branch-and-bound".
4. CONCLUSÕES
Nesse trabalho foi apresentado um estudo original sobre circuitos eulerianos na presença
de restrições de conversão nos vértices. Foi visto que um grafo, mesmo euleriano, pode não
conter um circuito euleriano, na existência de tais restrições. Desta forma foi feita uma
distinção entre um grafo euleriano e um grafo unicursal. Alguns teoremas que estabelecem as
condições de unicursalidade foram estabelecidos, e foi apresentado um algoritmo, baseado em
fluxo em redes, que num dado grafo euleriano com restrições de conversão acha um circuito
euleriano viável, ou detecta a sua inexistência.
XVII Encontro de Modelagem Computacional
V Encontro de Ciência e Tecnologia de Materiais
Universidade Católica de Petrópolis (UCP), Petrópolis/RJ, Brasil. 15-17 out. 2014
O algoritmo é muito útil na solução do Problema do Carteiro Chinês nas aplicações em
que o circuito deve ser construído nas malhas urbanas, onde as restrições de conversão nos
cruzamentos são bastante fortes.
REFERÊNCIAS
Christofides, N. (1975), Graph Theory, An Algorithmic Approach, Academic Press, London.
Edmonds,J. And Johnson, E.L. (1973), Matching, Euler Tours And The Chinese Postman , Math. Programming,
5, pag.88-124.
Fulkerson, D.R. (1961), An Out-of-kilter Method for Minimal Cost Flow Problems, SIAM J., Appl. Math., 9,
pag.18-27.
Harary F. And Nash-Williams C. St. J.A. (1965), On The Eulerian and Hamiltonian Graphs and Line Graphs,
Canadian Math. Bulletin 8, pag.701.
Selby, G.R. (1970), The Use Of Topological Methods In Computer-aided Circuit Layout, Ph.D. Thesis, London
University.
Sherafat, H. (1988), Uma Solução Para o Problema do Carteiro Chinês no Grafo Misto, Anais do XXI SBPO,
vol. 1, pag. 157-170.
EULERIAN CIRCUITS WITH TURN RESTRICTIONS
Abstract. In the present paper we discuss the construction of Eulerian Circuits with presence
of node restrictions. A survey on the properties of eulerian circuits and sub-circuits, as well as
a graph expansion, conduct to an efficient algorithm, which finds either an eulerian circuit, or
detect its inexistence.
Key Words: Eulerian Circuits, Turn Restrictions, Turn Penalties, Chinese Postman Problem.