3,a - Universidade dos Açores

Universidade dos Açores
Departamento de Matemática
Grafos, Problemas de Optimização Combinatória
e Algoritmos
Elaboração: Abel Carneiro
Orientação: Armando Mendes
Ponta Delgada
Junho de 2001
“When I was a Boy of 14 my father was so ignorant
I could hardly stand to have the old man around. But
when I got to be 21, I was astonished at how much
the old man had learned in 7 years.”
Mark Twain
Agradecimentos
Ao meu orientador Armando Mendes pela
atenção e orientação na elaboração desta
monografia.
Ao pessoal dos Serviços Académicos da
Universidade dos Açores, pela colaboração
prestada.
Aos meus familiares e amigos que sempre me
apoiaram ao longo destes oito meses de
trabalho.
Índice
Introdução................................................................................................................................... 1
Capítulo 1 – Noções Básicas sobre Grafos................................................................................. 2
1.1. Definições sobre nós, vértices, arcos e arestas. ............................................................... 2
1.2. Subgrafos e Grafos Parciais............................................................................................. 6
1.3. Operações com Grafos..................................................................................................... 7
1.4. Caracterização de Grafos............................................................................................... 13
1.5. Isomorfismos de Grafos ................................................................................................ 15
1.6. Tipos de Grafos ............................................................................................................. 16
1.7. Representação matricial de Grafos ................................................................................ 20
Capítulo 2 - Problemas de Optimização Combinatória e Grafos: Algoritmos. ........................ 22
2.1. Problemas dos Circuitos e ciclos de Euler .................................................................... 24
2.2. Problemas de colorações ............................................................................................... 27
2.6. Desenho de Grafos ........................................................................................................ 32
2.3. Árvore geradora mínima ou árvore de ligações mínimas.............................................. 34
2.4. Caminho mais curto....................................................................................................... 37
2.5. Caixeiro viajante............................................................................................................ 43
2.7. Problema de fluxo máximo numa rede de capacidades limitadas. ................................ 46
2.8. Outros Problemas .......................................................................................................... 52
Capítulo 3 – Caso de Estudo ....................................................................................................55
Conclusão ................................................................................................................................. 62
Referências Bibliográficas........................................................................................................ 63
Introdução
Esta monografia foi elaborada segundo uma proposta de trabalho e acompanhamento do
orientador Armando Mendes, estando estruturada em três capítulos.
O primeiro capítulo consta de breves noções sobre grafos, a meu ver, necessárias a uma
melhor compreensão desta monografia no seu todo. Neste capítulo, foram utilizados
essencialmente os livros “Graph Theory” de Frank Harary (1969) e “Tópicos de Matemática
Finita” de Ilda Silva (1992).
No segundo capítulo estão descritos alguns problemas de optimização combinatória em
grafos e os seus processos de resolução segundo um algoritmo ou uma heurística. As
consultas bibliográficas neste capítulo já foram mais diversificadas sendo referenciadas no
final de cada sub-capítulo.
Finalmente no terceiro capítulo, é apresentado um caso de estudo como forma de
exemplificar a aplicação prática dos problemas de optimização combinatória utilizando os
grafos.
Assim, sem esquecer que foi mais um importante momento de aprendizagem, pretendo
com esta monografia corresponder às propostas e sugestões do meu orientador.
1
Capítulo 1 – Noções Básicas sobre Grafos
Quando analisamos um conjunto de elementos de dados (não necessariamente dados
computacionais), podemos estar preocupados com o seu conteúdo ou com as relações
existentes entre eles, por vezes estas relações entre elementos de dados podem ser vistas
através de um grafo. Os grafos servem como modelo matemático para representar o mundo
real e o seu estudo é importante pois qualquer relação binária pode ser representado num
grafo.
A Teoria dos Grafos, preocupa-se com o estudo das relações existentes entre diversos
objectos em análise, podendo ser utilizada em qualquer área que necessite de organização de
dados: sociologia, investigação operacional, química, etc.
A tecnologia actual impõe um grande número de problemas que requerem a construção de
sistemas complexos através de arranjos específicos dos seus elementos. Isto inclui problemas
de planeamento no tempo ou scheduling de processos industriais, redes eléctricas, economia e
muitas outras áreas.
Baseada na simples ideia de pontos interligados por linhas, a Teoria dos Grafos combina
estes factores básicos numa rica e útil teoria, que fornece métodos poderosos de elaboração de
modelos e solução de problemas tendo em conta arranjos discretos de objectos.
1.1. Definições sobre nós, vértices, arcos e arestas.
Um grafo dirigido, digrafo ou grafo orientado é um par G = (V , A) em que V é um
conjunto (finito não vazio) e A ⊆ V × V uma família (finita) de pares ordenados de elementos
de V. Chamam-se nós ou nodos aos elementos v1 , v2 ∈ V e aos elementos (v1 , v2 ) ∈ A
chamam-se arcos. Quando se escreve (v1 , v2 ) está-se a denotar o arco que vai de v1 para v2 ,
assim a ordem em que aparecem os nós de cada arco de A é relevante.
Para facilitar o estudo de um grafo podem ser atribuídos rótulos aos seus nós e arcos.
Sendo assim, um rotulador de nós (respectivamente arcos) é uma função f : A → D para
arcos e g : V → D para nós, em que D é um domínio de rótulos qualquer (por ex. um valor
numérico). O peso de um arco ou de um nó é o valor que lhe está atribuído no seu domínio de
2
rótulos. Uma rede é um grafo rotulado, ou seja, um grafo com um rotulador para arcos e/ou
nós.
Um grafo não orientado é um par G = (V,A) onde V é um conjunto (finito não vazio) e A é
uma família de pares não ordenados de elementos de V.
Os elementos v1 , v2 ∈ V chamam-se vértices e quando falamos de grafos não orientados,
os elementos {v1 , v 2 } ∈ A chamam-se arestas e denotam-se {v1,v2}.
Na figura 1 é apresentado o exemplo da representação sagital de um grafo orientado em
que V = {1,2,3,4} e A = {(1,2), (1,3), ( 2,3), (3,4), ( 4,1)} .
Na figura 2 temos um exemplo de um grafo não orientado, em que V = {1,2,3,4} e
A = {{1,2}, {1,3}, {1,4}, {2,3}, {3,4}} .
2
2
3
3
1
1
4
Figura 1 - Grafo orientado
4
Figura 2 - Grafo não orientado
Note-se que num grafo não orientado tem-se (v1 , v2 ) ∈ A ⇒ (v2 , v1 ) ∈ A, ∀ v1 , v2 ∈V .
Chama-se grafo fundamental a um grafo não orientado construído a partir de um grafo
originalmente orientado.
Dois vértices (nós) v1 , v 2 ∈ V , num grafo não orientado, são adjacentes se existe uma
aresta que os una, ou seja {v1 , v 2 } ∈ A , caso se trate de um grafo orientado, se (v1 , v2 ) ∈ A
então v1 é adjacente a v2 e v2 é adjacente de v1 . Uma aresta {v1 , v 2 } ∈ A (arco (v1 , v2 ) ∈ A ) é
incidente aos vértices v1 e v2 . Caso duas arestas (arcos) distintas sejam incidentes a um
mesmo vértice então dizem-se arestas (arcos) adjacentes. Um lacete é uma aresta do tipo
{v1 , v1 } ∈ A .
3
Num grafo não orientado o grau de um vértice v, grau (v), é o número de arestas incidentes
ao vértice v, os lacetes contam como incidindo duas vezes no vértice v. No caso de G ser um
grafo orientado chamamos grau exterior de v e denotamos grau + (v) , ao número de arcos de
que v é extremidade inicial (neste caso os lacetes contam uma única vez). Analogamente,
chamamos grau interior de v e denotamos grau − (v) , ao número de arcos de que v é
extremidade final. Assim temos que:
em grafos não orientados
grau(v 2 ) = #{∀ v ∈ V : {v, v 2 } ∈ A};
e em grafos orientados
grau + (v 2 ) = #{∀ v ∈ V : (v 2 , v) ∈ A} (arcos que partem do nó v2 );
grau − (v 2 ) = #{∀ v ∈ V : (v, v 2 ) ∈ A} (arcos que chegam ao nó v2 );
grau (v 2 ) = grau + (v 2 ) + grau − (v 2 )
Por exemplo, na figura 1 temos grau+(1) = 2 , grau-(1) = 1 e grau(1) = 3. No caso da
figura 2 temos grau(1) = 3.
Torna-se conveniente dar nomes a vértices de baixo grau, assim um vértice é isolado se
grau (v ) = 0 . Um grafo diz-se completo de ordem n, se e só se #V = n e (vi , v j ) ∈ A ,
∀vi , v j ∈ V com v i ≠ v j . Um grafo é de ordem n quando #V = n e de tamanho m quando #A
= m. Na figura 2 temos um grafo de ordem 4 e tamanho 5. Num grafo completo de ordem n
tem-se #A = (n(n-1))/2 onde n é o número de vértices
Teorema
Sejam G = (V,A) um grafo e v ∈ V .
i)
Se G for um grafo orientado então
∑ grau
v∈V
ii)
Se G for um grafo não orientado então
−
(v) = ∑ grau + (v) =# A
v∈V
∑ grau (v) = 2# A
v∈V
(a demonstração resulta do facto de todos os arcos serem simultaneamente incidentes
para o interior de um nó e para o exterior de outro)
4
Dado que num grafo orientado grau (v) = grau + (v) + grau − (v) , podemos reformular este
teorema dizendo que em qualquer grafo
∑ grau(v) = 2 # A . Assim, o grau de um vértice é o
v ∈V
número de arestas incidentes a ele, no entanto, cada aresta é incidente a dois vértices (ou no
caso de lacetes duas vezes o mesmo vértice).
Teorema de Euler (1736)
Em qualquer grafo, há um número par de vértices de grau impar (eventualmente zero)
Demonstração: Seja G um grafo, então pelo teorema anterior
∑ grau(v) = 2 # A .
v ∈V
O resultado da soma entre dois números pares ou entre dois números ímpares é sempre um
número par, sendo impossível obter como resultado um número ímpar. Assim, uma vez que
∑ grau (v)
é um número par só podemos ter um número par de vértices de grau ímpar
v∈V
(eventualmente zero). ■
Num grafo G = (V,A) temos δ (G ) = min{grau(v) : v ∈ V } que corresponde ao menor grau
de G e ∆ (G ) = máx{grau(v) : v ∈ V } que corresponde ao maior grau de G.
Se δ(G ) = ∆ (G ) = r , então todos os vértices de G têm o mesmo grau e G é chamado grafo
regular de grau r, podemos então falar no grau de G e escrever grau (G ) = r .
Um grafo regular de grau 0 não tem arestas. Se G é regular de grau 1, então cada vértice v1
é adjacente a um único vértice v2 ; se for regular de grau 2, uma aresta é adjacente a
exactamente duas outras arestas. Os primeiros grafos regulares com interesse são chamados
cúbicos e têm grau 3.
Corolário
Cada grafo cúbico tem um número par de vértices.
Demonstração: Seja G um grafo cúbico qualquer. Então se G é cúbico temos que
grau (G ) = 3 , ou seja, ∀v ∈ V , grau (v ) = 3 . Como já vimos em qualquer grafo há um número
5
par de vértices de grau ímpar. Como todos os vértices de G são de grau ímpar conclui-se que
G tem um número par de vértices. ■
1.2. Subgrafos e Grafos Parciais
Quando estamos a trabalhar com um grafo pode ser necessário considerar apenas uma
parte desse mesmo grafo. Sendo assim, se retirarmos ao grafo original G = (V,A) uma ou mais
arestas ficamos com G’ = (V,A’) em que A' ⊂ A . Temos então um grafo parcial de G gerado
por A’ ou simplesmente um grafo parcial de G. Diz-se que G' tem a extensão de G sempre que
V ' = V , no entanto, note-se que necessariamente A' ⊂ A logo A' ≠ A como se exemplifica na
figura 3.
2
2
3
1
4
3
1
4
Figura 3 - Grafo Original e Grafo Parcial gerado a partir do original
Um subgrafo de G gerado por V’, ou apenas subgrafo de G é um grafo GV ' = (V ' , A' ) com
V ' ⊂ V e A' ⊆ A tais que (v1 , v2 ) ∈ A' ⇒ v1 , v 2 ∈ V ' , ou seja, um subgrafo não é mais que uma
parte do grafo original depois de retirados alguns vértices e as respectivas arestas incidentes.
Se GV ' é um subgrafo de G então G é chamado supergrafo ou grafo gerador de GV ' . Ao
retirarmos uma aresta a uma subgrafo ficamos então com um subgrafo parcial, ou seja,
GV ' = (V ' , A' ) um subgrafo de G = (V,A), então um subgrafo parcial é um grafo
G 'V ' = (V ' , A' ' ) com A' ' ⊂ A' .
6
2
1
3
1
3
1
4
3
4
4
Figura 4 - Grafo Original, Subgrafo e Subgrafo Parcial
1.3. Operações com Grafos
Podem-se definir operações sobre um grafo para que ele represente melhor as alterações
que sofrem os seus componentes: os dados correspondentes.
As operações elementares unárias definidas sobre grafos estão representadas nas figuras 5
e6.
2
2
3
1
3
1
4
4
Inserção de uma aresta ou vértice
Figura 5 - Exemplos de operações elementares unárias definidas sobre grafos
7
2
2
3
1
1
4
4
Eliminar arestas e/ou vértices
2
1
3
1
2
4
4
3
Rotação dos vértices adjacentes num dos sentidos
2
2
3
1
5
4
3
1
4/ 5
Fusão ou junção de dois vértices num
2
2
3
1
4
3
1
4
Inversão ou troca do sentido dos arcos
Figura 6 - Exemplos de operações elementares unárias definidas sobre grafos
8
Como podemos ver em Harary (1969) também podemos definir operações binárias, estas
são operações baseadas nas utilizadas na Teoria dos Conjuntos. O seu objectivo é fazer
operações sobre os elementos dos grafos (vértices e arestas) de modo a obterem-se novos
grafos.
2
3
1
3
4
6
5
G1
9
7
8
G2
a
b
c
G4
G3
Figura 7 - Grafos utilizados nos exemplos de operações binárias
Considerando os grafos G1 = (V1 , A1 ) , G2 = (V2 , A2 ) e G3 = (V3 , A3 ) representados na
figura 7, podemos definir a união de grafos, G ∪ G' = ( V ∪ V ' , A ∪ A' ), como a junção de
dois grafos através de vértices em comum se estes existirem, como se pode verificar nos
exemplos apresentados na figura 8, a união de G1 com G2 em que existem vértices em
comum e a união de G2 com G3 em que não existem vértices em comum.
2
1
3
3
4
5
G1 ∪ G2
5
9
7
6
8
G 2 ∪ G3
Figura 8 – Exemplos de união de grafos
9
A intersecção de grafos, G ∩ G' = ( V ∩ V ' , A ∩ A' ), tem como resultado os elementos em
comum entre os dois grafos.
3
∅
G1 ∩ G2
G 2 ∩ G3
Figura 9 - Intersecção de grafos
A adição de grafos, G + G ' , definida por Zykov (1949), consiste em G ∪ G' acrescentando
todas as arestas unindo vértices de G com vértices de G’.
Por seu turno, a diferença de grafos, G − G' , consiste na eliminação de elementos comuns
do grafo G em relação a G’.
Assim, G(V,A) – G’(V’,A’) = G’’(V’’, A’’), onde V’’ = V – V’ e A’’ = A – A’.
2
2
1
3
4
G1 + G2
5
3
1
4
5
G1 − G2
G 2 − G3
Figura 10 – Adição e diferença de grafos
Como já foi dito podem-se retirar vértices e/ou arestas a um grafo. Assim, considerando
um grafo G = (V,A), v ∈ V , a ∈ A e F ⊆ A , a eliminação de arestas de um grafo G
representa-se por G − a = (V , A − a ) e a eliminação de vértices de um grafo G representa-se
por G − v = (V − v, F ) tal que F contenha todas as arestas de A não incidentes a v. Usamos a
notação G − {a1 , K , a m } para eliminar mais do que uma aresta e G − {v1 , K, v n } para eliminar
mais do que um vértice.
É possível definir várias operações entre dois grafos G = (V,A) e G’ = (V’,A’) que resultam
num grafo G’’ = (V’’,A’’) em que o conjunto dos vértices V’’ é o produto cartesiano V × V ' ,
10
desde que V ∩ V ' = ∅ e A ∩ A' = ∅. Sendo assim podemos definir o produto e a composição
de dois grafos, outras operações deste tipo estão desenvolvidas em Harary e Wilcox (1967).
Para definir o produto G × G' , consideremos dois vértices quaisquer u , v ∈ V ' ' = V × V ' , ou
seja, u = (u1 , u 2 ) e v = (v1 , v2 ) . Assim, u e v são adjacentes em G × G' sempre que se
verifique [ u1 = v1 e u 2 adjacente a v2 ] ou [ u 2 = v2 e u1 adjacente a v1 ].
(3,a)
(3,b)
(3,c)
(5,a)
(5,b)
(5,c)
G2 × G4
Figura 11 – Grafo produto
A composição G’’ = G[G’] também tem V ' ' = V × V ' como conjunto de vértices e u e v são
adjacentes sempre que [ u1 adjacente a v1 ] ou [ u1 = v1 e u 2 adjacente a v2 ].
(3,a)
(3,b)
(3,c) (a,5)
(b,5)
(c,5)
(5,a)
(5,b)
(5,c) (a,3)
(b,3)
(c,3)
G2 [ G4 ]
G4 [ G2 ]
Figura 12 – Grafo composto
Considerando dois grafos G = (V,A) e G’ = (V’,A’), em que #V=n, #A=m, #V’=p, #A’=q,
V ∩ V ' = ∅ e A ∩ A' = ∅, podemos calcular o número de vértices e de arestas do grafo
resultado das operações, como se mostra na tabela 1.
11
Tabela 1 – Cálculo do número de arestas e vértices, do grafo resultado de algumas operações
binárias
Operação
Número de vértices
Número de arestas
G ∪ G'
n+p
m+q
G ∩ G'
0
0
G + G'
n+p
m + q + np
G − G'
n
m
G × G'
np
nq + pm
G[G’]
np
2
nq + p m
O complementar de um grafo G = (V,A), é um grafo G = (V , A' ) em que A ∩ A' = ∅ e
G ∪ G é um grafo completo, ou seja, se G é o complementar de um grafo G então G tem os
mesmos vértices de G e dois vértices de G são adjacentes se e só se não o são em G. Na
figura 13 temos um exemplo de um grafo G e do seu complementar G .
G
G
Figura 13 – Exemplo de um grafo e do seu complementar
12
1.4. Caracterização de Grafos
Para melhor compreender as características dos grafos, é apresentado um pequeno conjunto
de conceitos que expressam a peculiaridade de cada grafo.
Vamos então considerar G = (V,A) um grafo com vi ∈ V , 0 ≤ i ≤#V e a j ∈ A , 1 ≤ j ≤ # A .
Temos assim que, num grafo G não orientado chama-se caminho, enquanto num grafo
orientado chama-se trajectória, a toda a sequência alternada de vértices (nós) e arestas (arcos)
que começa e acaba com vértices (nós), v0 , x1 , v1 ,K , v k −1 , x k , v k , em que cada aresta (arco) é
incidente a dois vértices (nós), o antecessor e o sucessor. Este caminho (trajectória) une v0 a
vk e também pode ser denotado v0 v1v 2 K v k −1v k visto que as arestas (arcos) são evidentes do
contexto.
O comprimento de um caminho é o valor de k, i.e., o número de arestas que o constituem.
Um caminho é simples se não utiliza duas vezes a mesma aresta e diz-se elementar se não
passa duas vezes pelo mesmo vértice.
Um circuito é um caminho v0 v1v 2 K v k −1v k , tal que v0 e vk coincidem, i.e., um caminho
fechado. Segundo este conceito um lacete é um circuito de comprimento 1.
Um ciclo é um circuito simples v0 v1v 2 K v k −1v k , tal que v0 e vk coincidem e k > 0 , i.e., um
caminho fechado não trivial (mais que um vértice) e que não passa pela mesma aresta mais do
que uma vez. Um ciclo é de ordem n se e só se #V = #A = n e as suas arestas formam um ciclo
de comprimento n, quando um grafo não tem ciclos diz-se acíclico.
Num grafo um ciclo de Hamilton é um ciclo que passa por todos os vértices do grafo; um
grafo é chamado hamiltoniano se possui pelo menos um ciclo de Hamilton.
O fecho transitivo directo de um vértice v é o conjunto de todos os vértices que podem ser
atingidos por algum caminho iniciando em v, o fecho transitivo inverso de um vértice v é o
conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho. O
próprio vértice v faz parte do seu fecho directo e inverso.
Dois vértices são conexos se são adjacentes ou possuem uma relação de adjacência, ou
seja, dados dois vértices v1 e v2, existe um vértice v'1 que é adjacente a v1, outro v'2 que é
13
adjacente a v'1, e assim sucessivamente até v2 . Isto é o mesmo que dizer que existe um
caminho entre eles. Na figura 14 o vértice C é conexo com o vértice D.
B
C
A
D
Figura 14 - Grafo com todos os vértices conexos
Dois vértices v1 e v2 são chamados de:
•
debilmente conexos se e só se existe um caminho não orientado desde v1 até v2 ;
•
unilateralmente conexos se e só se existe uma trajectória orientada desde v1 até
v2 , ou vice-versa;
•
fortemente conexos se e só se existe uma trajectória orientada desde v1 até v2 , e
vice-versa.
Existindo vértices conexos, também podemos falar em grafos conexos. Sendo assim um
grafo orientado diz-se:
•
debilmente conexo se e só se ∀v1 , v2 ∈ V existe um caminho não orientado desde
v1 até v2 ;
•
unilateralmente conexo se e só se ∀v1 , v2 ∈ V existe uma trajectória orientada
desde v1 até v2 , ou vice-versa;
•
fortemente conexo se e só se ∀v1 , v2 ∈ V existe uma trajectória orientada desde v1
até v2 , e vice-versa.
Um grafo não orientado diz-se conexo se ∀v1 , v2 ∈ V existe um caminho desde v1 até v2 ,
como é exemplo o grafo da figura 14.
14
Teorema
Um grafo orientado G é debilmente conexo se e só se o seu grafo fundamental (não
orientado) é conexo.
Demonstração: Seja G um grafo orientado e G* o seu grafo fundamental.
⇒
Dado que G é debilmente conexo então ∀v1 , v2 ∈ V existe um caminho não
orientado desde v1 até v2 e como G* é não orientado temos que G* é conexo.
⇐
Sendo G* um grafo fundamental conexo então ∀v1 , v2 ∈ V existe um caminho desde
v1 até v2 . Assim G o grafo originalmente orientado é debilmente conexo. ■
Temos ainda que GV ' é um subgrafo conexo maximal ou componente conexo de G se e só
se GV ' é conexo e não existe outro subgrafo de G, GV '' ⊃ GV ' , tal que GV '' também é conexo.
A união de todos os componentes conexos de G é o próprio grafo G original.
Dado um grafo conexo G e a ∈ A uma aresta (respectivamente v ∈ V um vértice) de G,
diz-se que a é uma aresta de corte (respectivamente v é um vértice de corte) se e só se G − a
não é conexo (respectivamente G − v não é conexo). Note-se que na maioria das vezes um
corte é constituído por um conjunto de arestas ou vértices superior a um elemento.
1.5. Isomorfismos de Grafos
Dados dois grafos G = (V,A) e G’ = (V',A'), diz-se que G ≅ G ' , ou seja, G e G' são
isomorfos
se
e
só
se
existe
uma
função
bijectiva
ϕ :V → V '
tal
que
(v1 , v2 ) ∈ A ⇔ (ϕ (v1 ), ϕ (v2 )) ∈ A' ∀v1 , v 2 ∈ V . Uma invariante de um grafo G é um número
associado a G que tem o mesmo valor para todos os grafos isomorfos a G, assim dados G =
(V,A) e G’ = (V',A') dois grafos, uma invariante é toda a função do tipo η : {Grafos} → IN tal
que G ≅ G ' ⇒ η (G ) = η (G ' ) .
Até agora foram mencionados alguns invariantes, tais como #V, #A, grau+(v), grau-(v),
grau(v), δ (G ) e ∆ (G ).
O problema geral de, dados dois grafos, saber se eles são ou não isomorfos é um problema
difícil porque pode implicar um grande número de verificações. Há, no entanto, condições
15
necessárias óbvias que G e G' têm que satisfazer para serem isomorfos. Por exemplo, G e G'
têm que ter o mesmo número de vértices, G e G' têm de ter o mesmo número de arestas e G e
G' têm que ter o mesmo número de componentes conexas. A proposição seguinte permite-nos
obter mais algumas condições necessárias.
Proposição
Sejam G = (V,A) e G’ = (V',A') dois grafos isomorfos e f : V → V ' um isomorfismo.
Então:
iii)
∀v ∈ V , grau(v) = grau(f(v))
iv)
∀U ⊆ V o subgrafo de G gerado por U é isomorfo ao subgrafo de G' gerado
por f(U), denota-se GU ≅ G ' f (U )
Existe uma conjectura, de certo modo o reciproco da proposição anterior, que diz:
Conjectura de Ulam (1960)
Suponhamos que G e G' são dois grafos da ordem n com n ≥ 3 .
Sejam V = {v1, ... ,vn} e V’ ={u1, ... ,un} os conjuntos de vértices, respectivamente de G e
G'.
Se para cada i = 1, K , n os subgrafos Gi = G − vi e G ' i = G '−u i forem isomorfos então G e
G' são isomorfos.
1.6. Tipos de Grafos
Vamos agora atribuir alguns nomes a grafos, o que facilita a sua identificação. Podemos
então dizer que dado um grafo G = (V,A), diz-se que G é:
•
nulo de ordem n se só se #V = n e grau(v) = 0, ∀v ∈ V ;
•
planar quando a sua representação sagital é possível sem cruzamentos entre arcos;
•
uma árvore se e só se é um grafo simples e ∀v1 , v2 ∈ V existe um único caminho
simples desde v1 até v2 ;
16
•
uma árvore com raiz ou Rooted-Tree se e só se existe um vértice designado como
raiz ou origem do(s) caminho(s) como é exemplo a figura 15;
•
uma árvore com raiz orientada se e só se for uma árvore com uma trajectória
orientada desde a raiz até cada vértice da árvore;
Figura 15 - Árvore com raiz
Existem algumas propriedades conhecidas sobre estes grafos. Por exemplo, toda a árvore não
trivial (dois ou mais vértices) tem pelos menos um vértice de grau 1.
Note-se que todo o vértice de uma árvore pode ser a sua raiz, no entanto uma rooted-tree
orientada só possui uma única raiz. Numa rooted-tree define-se o nível de um vértice v como
o comprimento dum caminho desde a raiz até v e todo o vértice de grau 1 chama-se de folha
desde que não seja a raiz.
Inserindo em G um vértice a um ciclo de ordem n-1 ao qual se une mediante n-1 novas
arestas a todos os vértices originais obtém-se uma roda de ordem n, representada por Wn .
Numa roda de ordem n tem-se que #V = n e #A = 2.(n - 1).
W7
Figura 16 - Roda de ordem 7
17
Um grafo G = (V,A) com arestas em paralelo, um par de vértices é ligado por duas ou mais
arestas, mas que não possui lacetes chama-se multigrafo. Na figura 17 temos um exemplo de
um multigrafo em que os vértices 2 e 4 são ligados por arestas em paralelo.
2
4
1
3
Figura 17 - Multigrafo
Sempre que um grafo não possua lacetes nem arestas em paralelo chama-se grafo simples.
Quando um grafo possui lacetes e arestas em paralelo então temos um pseudografo, como se
exemplifica na figura 18.
Figura 18 – Pseudografo
Um grafo G = (V,A) diz-se bipartido se e só se existem X ⊆ V e Y ⊆ V tais que:
•
X ∪Y = V ;
•
X ∩Y = ∅ ;
•
(vi , v j ) ∈ A ⇒ vi ∈ X ∧ v j ∈ Y (ou vice-versa).
O grafo representado na figura 19 é bipartido. Considerando para partição dos vértices
X = {1,2} e Y = {a, b, c} , qualquer aresta de G tem uma extremidade em X e a outra em Y.
18
Figura 19 - Exemplo de grafo bipartido
Por outras palavras um grafo é bipartido se e só se podem colorir os vértices com duas
cores de modo a que cada aresta tenha uma extremidade de cada cor e logo nenhuma aresta
possa ligar dois vértices da mesma cor.
Diz-se que um grafo, K m , n = (V , A) com m, n ∈ IN , é bipartido completo se e só se
existem X ⊆ V e Y ⊆ V tais que:
•
X = {x1 ,K, x m } e Y = { y1 ,K , y n } ;
•
X ∪Y = V ;
•
X ∩Y = ∅ ;
•
vi ∈ X ∧ v j ∈ Y ⇒ (vi , v j ) ∈ A, ∀vi , v j ∈ V com v i ≠ v j .
a
1
b
2
c
K 2,3
Figura 20 – Grafo bipartido completo
19
Teorema
Um grafo G é bipartido se e só se todo o ciclo em G tem comprimento par.
Demonstração: Se G for bipartido então o seu conjunto de vértices pode ser escrito como
V = X ∪ Y de forma que cada aresta de G una um vértice de X com um de Y. Assim qualquer
ciclo v1v 2 K v n v1 em G tem os seus vértices alternadamente em X e em Y, como no ciclo os
índices dos vértices alternam entre impares e pares temos que n é um número par. Como já foi
dito antes o índice n é que dá o comprimento do ciclo, logo todo o ciclo é de comprimento
par. ■
Teorema
Toda a árvore é um grafo bipartido.
Demonstração: Uma árvore não tem ciclos, sendo assim é possível colorir todos os seus
vértices utilizando apenas duas cores, por exemplo azul e vermelho, de forma que todas as
arestas são incidentes a um vértice azul e a um vértice vermelho. Sendo assim é possível
definir um grafo G em que o conjunto dos vértices é formado pela união de dois conjuntos de
vértices disjuntos, cada um composto por vértices de uma única cor e em que qualquer aresta
apenas une vértices de cores diferentes. Logo G é um grafo bipartido. ■
1.7. Representação matricial de Grafos
Uma representação alternativa à sagital de grafos é feita recorrendo a matrizes de
adjacência e matrizes de incidência.
Como podemos ver em Harary (1969) dado um grafo G = (V,A), a matriz quadrada de
ordem n, definida por AG = ( a i j ) em que a i j = 1 , se vi é adjacente a v j , e zero caso contrário,
∀ i ∈{1, ... , n}, j ∈{1, ... , n} , chama-se matriz associada ou de adjacência de G. Se o grafo for
rotulado em arestas, em vez de 1, aparece o peso de cada aresta.
Consideremos o grafo orientado utilizado anteriormente na figura 1, em que #V=4 logo a
respectiva matriz de adjacência, representada na figura 21, é de ordem 4. Para o grafo não
orientado utilizado anteriormente na figura 2, temos a matriz de adjacência da figura 22, a
qual é simétrica já que as arestas têm os dois sentidos em simultâneo.
20
1
2
3
4
1 0
1
1
0
2 0
0
1
0
3 0
0
0
1
4 1
0
0
0
Figura 21 – Matriz de adjacência da representação sagital da figura 1
1
2
3
4
1 0
1
1
1
2 1
0
1
0
3 1
1
0
1
4 1
0
1
0
Figura 22 –Matriz de adjacência da representação sagital da figura 2
Sendo G = (V,A) em que V = {v1 , ... , v n } e A = {a1 , ... , a m } chama-se matriz de incidência de
G à matriz de ordem nxm, IG, definida por IG =( bi j ) em que ∀ i ∈{1, ... , n}, j ∈{1, ... , m} , bi j = 0
se vi não é extremidade de a j ou se a j é um lacete, bi j = 1 se vi é extremidade de a j e a j
não é um lacete.
A matriz de incidência não é tão utilizada porque esta terá uma ordem superior à da matriz
de adjacência e porque não é utilizada em grafos orientados, mas aqui fica um exemplo
relativo ao grafo já apresentado na figura 2:
{1,2} {1,3} {1,4} {2,3} {3,4}
1
1
1
1
0
0
2
1
0
0
1
0
3
0
1
0
1
1
4
0
0
1
0
1
Figura 23 – Matriz de incidência da representação sagital da figura 2
Estas definições, como já foi referido, estão de acordo com Harary (1969) no entanto
existem outras definições para este tipo de matrizes como pode ser visto em Kaufmann et
Coster (1970).
21
Capítulo 2 - Problemas de Optimização
Combinatória e Grafos: Algoritmos.
Na indústria, comércio, governo, bem como em variados outros campos, uma das
necessidades mais frequentes é baseada em questões de eficácia operacional.
A optimização combinatória é um campo da matemática aplicada que combina técnicas de
Combinatória, Programação Linear, Teoria dos Grafos, entre outras, com o objectivo de
encontrar soluções para problemas de optimização.
Por exemplo, um engenheiro de telecomunicações com o objectivo de transmitir sinais
minimizando a possibilidade de erro na recepção, um transitário ao planear o itinerário dos
seus fretes para os rentabilizar diminuindo os custos de espera no cais, a sincronização de
semáforos e um variado número de outras situações do nosso dia a dia. Inicialmente, estes
problemas eram resolvidos por métodos imprecisos dando resultados pouco fiáveis e
dispendiosos. Actualmente, a resolução destes problemas está a ser alvo de uma rigorosa
análise matemática, desenvolvida com o intuito de encontrar métodos de resolução exactos
ou estimativas confiáveis em vez de meras aproximações. A Combinatória e a Optimização
disponibilizam muitas das ferramentas matemáticas utilizadas na resolução de problemas
deste tipo. Muitos destes problemas podem ser descritos sobre um grafo. Os problemas
consistem em encontrar uma configuração óptima (máxima ou mínima, conforme o caso) de
um certo tipo no grafo. A dificuldade de todos os problemas de Optimização Combinatória
está em desenvolver algoritmos eficientes que encontrem a configuração óptima desejada.
Um dos primeiros problemas resolvido com grafos, e que pode ser visto em Reed (2001), é
o das sete pontes de Königsberg. O problema diz o seguinte:
Figura 24 - Esboço das pontes de Königsberg
Na cidade de Königsberg existe uma ilha (A), chamada Kneiphoff, no meio do rio Pregel.
22
Existem sete pontes, a, b, c, d, e, f e g, que atravessam o rio (figura 24). A questão é saber se
será possível planear um passeio de forma a passar uma e uma única vez por todas as pontes.
Em 1736, o matemático Leonard Euler (1707-1783) dando origem à Teoria dos Grafos,
representou as pontes por aresta e as zonas terrestres por vértices, como se pode ver no grafo
da figura 25.
Figura 25 - Grafo de Königsberg
O problema pode ser visto do seguinte modo: como construir o grafo da figura 25 sem
levantar o lápis do papel nem passar mais que uma vez o lápis pelo mesmo risco? Este
problema não é possível e pode ser explicado através da Teoria dos Grafos como se pode ver
na página 24 ou em Silva (1992).
As técnicas da Teoria dos Grafos cedo se mostraram úteis para além do planeamento de
travessias no rio Pregel. Os químicos descobriram uma correspondência natural entre grafos e
diagramas de moléculas, os átomos são vértices e as ligações entre átomos arestas. O físico
alemão Kirchoff analisou circuitos eléctricos em termos de grafos, em que os fios eram
arestas e os terminais vértices.
As ruas de Ponta Delgada podem ser representadas por um grafo e podemos construir
vários problemas com base nesse grafo de ruas. Por exemplo, podemos querer prever o fluxo
de automóveis nas ruas do centro da cidade, dar informações para roteiros turísticos sobre o
caminho mais curto entre dois pontos de interesse e planear uma volta pela cidade sem repetir
ruas ou até mesmo cruzamentos. São problemas como estes que são chamados problemas de
Optimização Combinatória, pois podemos fazer várias combinações de arcos ou arestas com
vista a obter um grande número de soluções podendo eventualmente uma delas ser óptima.
23
Um problema de optimização combinatória procura encontrar uma solução que minimiza
(ou maximiza) uma função objectivo num conjunto não infinito de soluções factíveis. Esta
procura é feita muitas vezes segundo um determinado processo a que se chama algoritmo.
Desenvolver um algoritmo óptimo muitas vezes não é tarefa fácil e por isso mesmo muitas
vezes basta a utilização de heurísticas de resolução. Segundo Müller (1997) heurísticas são
critérios ou métodos computacionais para decidir o caminho mais eficiente entre várias
alternativas de acção, procurando optimizar um determinado objectivo, porém nem sempre
permitem encontrar o melhor caminho entre todas as alternativas possíveis. Dado o exemplo
das ruas de Ponta Delgada, podemos tentar encontrar o caminho mais curto entre dois pontos
dados, como podemos tentar encontrar o terceiro caminho mais curto ou o caminho mais curto
mas que passe pelas portas da cidade.
Vamos então apresentar alguns exemplos de problemas de optimização combinatória em
grafos, bem como alguns algoritmos de resolução.
2.1. Problemas dos Circuitos e ciclos de Euler
Em 1736 Leonard Euler chegou à conclusão que o passeio proposto segundo as pontes da
cidade de Königsberg não era possível. Suponhamos que existia um percurso através das
pontes de Königsberg nas condições procuradas. Esse percurso começaria numa certa região
da cidade e acabaria numa outra região eventualmente a mesma. Com possível excepção
dessas duas regiões sempre que se entrasse por uma ponte numa das outras regiões (pelo
menos duas) ter-se-ia que sair por outra ponte, implicando que essas regiões (pelo menos
duas) seriam extremidade de um número par de pontes. Ora, como se vê na figura 25,
qualquer das quatro regiões da cidade é extremidade de um número ímpar de pontes, sendo
pois impossível arranjar um percurso nas condições pedidas. Um grafo orientado diz-se
euleriano se tiver um circuito de Euler, i.e., um circuito que contenha todos os seus arcos uma
e só uma vez. De acordo com o teorema de Euler, um grafo orientado admite um circuito de
Euler se e só se for fortemente conexo e qualquer nó tem grau interior igual ao grau exterior.
Um grafo não orientado diz-se euleriano se há um ciclo que contenha todas as suas arestas
uma e só uma vez (ciclo euleriano). De acordo com o teorema de Euler, um grafo não
orientado admite um ciclo de Euler se e só se for conexo e não tiver vértices de grau ímpar.
24
Veja-se, na figura 26, um circuito euleriano porque admite o circuito A, B, C e D e um ciclo
euleriano porque admite o ciclo E, F, G e H (ou ao contrário).
A
1
D
4
C
2
5
B
H
3
8
E
6
F
7
G
Figura 26 – Exemplo de um circuito euleriano e de um ciclo euleriano
Como exemplo para um problema de circuitos de Euler, vamos ter em conta a recolha de
lixo na cidade de Ponta Delgada, para isso temos de ter em atenção o sentido indicado pelo
trânsito. Considere-se que a figura seguinte representa uma zona da cidade onde uma equipa
terá de fazer recolha de lixo em todos os arruamentos existentes, passando só uma vez em
cada um dos arruamentos. Em cada um dos arruamentos está indicada a distância (centenas de
metros) entre os nós extremos. A recolha de lixo é um exemplo do problema do carteiro
chinês que consiste em passar por todos os arruamentos o menor número de vezes possível
chegando ao mesmo sítio de partida percorrendo uma distância mínima. Admitindo que se
pretende que o percurso de limpeza comece e termine em A qual é o circuito óptimo?
10
A
9
E
D
8
15
7
12
10
B
11
C
Figura 27 – Grafo de distâncias dos arruamentos da cidade
O circuito óptimo será um circuito de Euler, em que se percorrerão todos os arruamentos
uma única vez. Se existir, a distância total óptima será de 82 centenas de metros, que é o
somatório de todas as distâncias associadas a cada um dos arcos do grafo. Será que este grafo
25
é euleriano? Porque o grafo é conexo e todos os nós têm o grau interior igual ao grau exterior,
de acordo com o teorema de Euler o grafo é euleriano.
Para estabelecer um circuito de Euler, que sabemos existir, fazemos o seguinte:
1º Passo – Registar em coluna, para cada nó, os seus sucessores.
A B C D E
E A D B B
C
E D
Figura 28 – Exemplo do primeiro quadro
2º Passo – Organizar um segundo quadro para registar, sucessivamente, os arcos do circuito
(início em A por exemplo);
3º Passo – Escolher sucessivamente sucessores do último vértice atingido, impedindo
circuitos “parasitas”1.
Seleccionar o arco AE; eliminar E no 1º quadro e registar no 2º quadro; último nó é E;
Seleccionar o arco EB; eliminar B no 1º quadro e registar no 2º quadro; último nó é B;
Seleccionar o arco BA; eliminar A no 1º quadro e registar no 2º quadro; último nó é A;
A B C D E
E A D B B
C
E D
Ordem 1º 2º 3º 4º 5º 6º 7º 8º Fecho
Vértice A E B A
Figura 29 – Exemplo da existência de um circuito parasita
O nó A não tem sucessores; estabeleceu-se prematuramente o circuito “parasita” A, E, B, A.
O nó A é deslocado para a última casa livre do 2º quadro. O “último” nó do circuito é agora B.
Seleccionar o arco BC; eliminar C no 1º quadro e registar no 2º quadro; último nó é C;
Seleccionar o arco CD; eliminar D no 1º quadro e registar no 2º quadro; último nó é D;
1
Quando um nó extremo de um circuito fica sem sucessores temos um circuito parasita.
26
Seleccionar o arco DB; eliminar B no 1º quadro e registar no 2º quadro; último nó é B;
O nó B não tem sucessores pelo que se estabeleceu mais um circuito parasita por isso o nó
B será deslocado para a última casa livre no 2º quadro. O “último” nó do circuito é agora D;
Seleccionar o arco DE; eliminar E no 1º quadro e registar no 2º quadro; último nó é E;
Seleccionar o arco ED; eliminar D no 1º quadro e registar no 2º quadro; último nó é D;
A B C D E
E A D B B
C
E D
Ordem 1º 2º 3º 4º 5º 6º 7º 8º Fecho
Vértice A E B C D E D B A
Figura 30 – Quadro final
Todos os arcos foram seleccionados. Neste último quadro tem-se o circuito de Euler com
início e fim no vértice A.
No caso de querermos um ciclo de Euler o método anterior também serve pois basta tornar
o grafo em orientado e que satisfaça as condições necessárias à existência de um circuito de
Euler.
Podemos encontrar diversa informação sobre circuitos e ciclos de Euler em Caldwell
(1995) e Morais da Silva (2001)
2.2. Problemas de colorações
Um problema de coloração consiste na ideia de que dado um grafo sem lacetes determinar
o menor número de cores necessário para colorir todos os vértices (respectivamente arestas)
em que dois vértices (respectivamente arestas) adjacentes não possam ter a mesma cor, este
número é chamado número (respectivamente índice) cromático. Este problema está na origem
de um dos mais famosos teoremas da Matemática, o teorema das 4 cores.
Teorema das 4 cores
O número máximo de cores necessário para colorir os vértices de qualquer grafo planar, de
modo a que vértices adjacentes tenham cores diferentes, é 4.
27
Podemos encontrar mais informações sobre a história deste teorema e sobre algoritmos de
colorações em Toft (2000), Trick (1994), Thomas et al (1995), Felsner (1992), Harary (1969)
e Silva (1992).
Considere-se, como exemplo, o seguinte problema: Um aluno da U.A. necessita de
frequentar as cadeiras A, B e C. Quantos momentos diferentes necessitam de ser reservados no
horário para que o aluno possa estar presente às aulas das referidas cadeiras?
Dada a simplicidade da questão é fácil concluir serem necessários 3 momentos distintos. A
mesma conclusão pode obter-se recorrendo a um grafo não orientado em que os vértices
representam as cadeiras e as arestas ligam cadeiras que não podem ter lugar em simultâneo.
Vamos considerar o grafo da figura 31.
C
A
B
Figura 31 – Grafo representativo das disciplinas
Organizado o grafo, o objectivo é minimizar o número de cores necessárias para colorir
todos os vértices para que, vértices adjacentes, não tenham a mesma cor.
C
A
B
Figura 32 – Grafo colorido
Considere-se a relação dos exames requeridos, na mesma época, por alunos do
Departamento de Matemática da U.A..
28
Tabela 2 – Relação de exames
Aluno Cadeiras
1
A,B
2
A,D
3
D,E,F
4
B,C
5
A,C
6
B,E
7
C,F
8
E,G
Admitindo que um aluno só pode executar, no máximo, um exame por dia, qual é o menor
número de dias necessário para executar todos os exames?
O grafo com a coloração óptima dos vértices para este problema é o seguinte:
D
A
C
B
E
G
F
Figura 33 – Grafo de exames colorido
O número cromático é 3. São necessários, no mínimo, 3 dias para realizar os subconjuntos
de exames {A, E}, {C, D} e {B, F, G}.
Existem vários métodos para calcular o número cromático de um grafo. A heurística a
seguir apresentada baseia-se no nível de saturação e grau de cada vértice. A primeira cor é
atribuída ao vértice de maior grau e a análise de cada um dos vértices restantes é efectuada
por ordem decrescente do respectivo grau de saturação2.
Veja-se a aplicação do método ao grafo anterior em que a matriz de adjacências é a
seguinte.
2
Número de cores distintas nos vértices adjacentes.
29
A
B
C
D
E
F
G
A B C D
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
0 1 0 1
0 0 1 1
0 0 0 0
E
0
1
0
1
0
1
1
F
0
0
1
1
1
0
0
G
0
0
0
0
1
0
0
Figura 34 – Matriz de adjacência da representação sagital da figura 33
1º Passo: Ordenar os vértices por ordem decrescente de grau;
E
A
B
C
D
F
G
4
3
3
3
3
3
1
2º Passo: Atribuir cor ao 1º vértice: exame “E” com cor 1 (preto na figura 33);
3º Passo: Ordenar os vértices não coloridos por ordem decrescente do grau de saturação.
Os vértices B,D,F e G têm grau de saturação 1 pois são adjacentes de “E” que já tem cor.
Como os três primeiros são do mesmo grau a sua ordenação é arbitrária ficando “G” a seguir a
eles. Os restantes vértices têm grau de saturação nulo ficando ordenados de forma arbitrária:
Vector
B
D
F
G
A
C
ordenado:
4º Passo: Atribuir cor a “B” (1º vértice do vector ordenado). É adjacente de “E” com cor 1,
pelo que recebe cor 2 (azul na figura 33);
A partir de agora repetem-se os passos 3 e 4 até ter colorido todos os vértices.
Em síntese os passos são os apresentados em seguida:
Cor atribuída
Vector ordenado
A
C
D
F
C
D
F
G
F
D
G
D
G
G
G
Colorir “A” com cor 1 (adjacente da cor 2)
Colorir “C” com cor 3 (adjacente das cores 1 e 2)
Colorir “F” com cor 2 (adjacente das cores 1 e 3)
Colorir “D” com cor 3 (adjacente das cores 1 e 2)
Colorir “G” com cor 2 (adjacente da cor 1)
30
Pelo que o número cromático é 3. Os exames necessitam de 3 dias para serem realizados e,
por exemplo, podem ser assim distribuídos:
1º dia
2º dia
3º dia
“A” e “E” “B”, “F” e “G” “C” e “D”
Um outro método descrito em Gondran e Minoux (1979), também utiliza o grau de cada
vértice mas em vez de colorir vértices um a um com cores diferentes, esta heurística vai
colorir subconjuntos de vértices. Vamos definir primeiro alguns parâmetros que vamos
utilizar.
Seja G = (V,A) um grafo com #V = n; k o número de cores a utilizar; dx o grau do vértice x;
Vx o conjunto dos vértices adjacentes ao vértice x; j (i ) = x, com i = 1, K , n posição do
vértice x num conjunto ordenado e j (i ) o vértice que está na posição i.
1º Passo: Calcular d x = # V x ; k =1;
2º Passo: Ordenar V por ordem decrescente do grau dos vértices (V é conjunto dos vértices
que estão por colorir);
Fazer S = V
3º Passo: Determinar r = min i ; l = j (r ) ; V = V − l ; n = n − 1 ; f (l ) = k ;
j ( i )∈S
Para cada x ∈ Vl fazer ( V x = V x − l ; d x = d x − 1 ; S = S − x );
S = S −l ;
se S ≠ ∅ repetir o 3º Passo caso contrário ir para o 4º Passo;
4º Passo: Se n = 0 termina-se, caso contrário, k = k + 1 e voltar ao 2º Passo.
No fim deste método f (x ) dá o número da cor a utilizar no vértice x.
Vejamos uma aplicação desta heurística no grafo de exames da tabela 2. Assim temos:
1º V = { A, B, C , D, E , F , G}, n = 7, d A = 3, d B = 3, d C = 3, d D = 3, d E = 4, d F = 3, d G = 1, k=1;
2º S = {E , A, B, C , D, F , G};
3º r = min i = 1, l = j (1) = E , V = { A, B, C , D, F , G}, n = 6, f ( E ) = 1, VE = {B, D, F , G} ,
j ( i )∈S
31
Vértice x
Vx
dx
S
B
{A, C}
2
{E, A, C, D, F, G}
D
{A, F}
2
{E, A, C, F, G}
F
{C, D}
2
{E, A, C, G}
G
∅
0
{E, A, C}
S = S − E = { A, C} , como S ≠ {} repito o 3º passo vindo
r = min i = 1, l = j (1) = A, V = {B, C , D, F , G}, n = 5 , f ( A) = 1, V A = {B, C , D}
j ( i )∈S
Vértice x
Vx
dx
S
B
{C}
1
{A, C}
C
{B}
1
{A}
D
∅
0
{A}
S = S − A = ∅;
Neste momento já tenho A e E com cor 1 e não há hipótese de mais vértices com a cor 1,
pelo que vou procurar vértices para a cor 2.
4º K=2 e volto a repetir o procedimento do 2º passo até que n = 0.
No fim deste processo vou obter igualmente o grafo da figura 33.
2.6. Desenho de Grafos
A própria representação sagital de grafos é um problema de optimização dado que perante
um determinado grafo podemos querer saber se é possível desenhar o mesmo grafo sem haver
cruzamento de arestas, ou no menor espaço possível de forma que continue legível, etc. O
próprio tempo de construção de um grafo é um problema sempre em aberto e alvo de muitos
desafios pois se um programa é capaz de construir um grafo com um milhão de vértices e
cinco milhões de arestas em trinta segundos, é lançado de imediato o desafio de encontrar um
novo algoritmo capaz de aumentar o número de vértices e arestas e diminuir o tempo de
execução. Existem diferentes tipos de heurísticas que permitem melhorar a representação
sagital de grafos como nos diz Bridgeman et al. (1999) e Six et al. (2000).
32
Por exemplo, podemos desejar minimizar o número de cruzamentos de arcos num grafo,
para esse efeito podemos utilizar o algoritmo de Demucron. Em primeiro lugar precisamos da
matriz de adjacência do grafo, depois fazemos o seguinte:
1º - Calcular o grau de cada vértice na matriz de adjacência e eliminar a coluna e a linha do
vértice origem que constituirá o nível 0 da representação do grafo;
2º - Recalcular o grau dos vértices em que se verificar variação de grau com a eliminação
efectuada no 1º passo;
3º - De entre os vértices com variação, seleccionar os com menor grau recalculado,
constituindo este o nível seguinte da representação;
4º - Eliminar a linha e a coluna dos vértices seleccionados no ponto anterior e voltar ao 2º
passo.
Vejamos a aplicação deste método no grafo da figura 47.
A B C D
A
1 1
B 1
1
C 1 1
D
E
1 1 1
F
1 1
G
1
1
E F G
1
1
1 1
1 1 1
1
1
Figura 47 – Matriz de adjacência
O desenvolvimento do algoritmo é o apresentado na figura 48:
A B C D
A
1 1
B 1
1
C 1 1
D
E
1 1 1
F
1 1
G
1
1
E F G
A B C D
A
1 1
B 1
1
C 1 1
D
E
1 1 1
F
1 1
G
1
1
E F G
1
1
1 1
1 1 1
1
1
1
1
1 1
1 1 1
1
1
A
2
4
4
3
3
3
3
A
2
4
4
3
3
3
3
A B C D
A
1 1
B 1
1
C 1 1
D
E
1 1 1
F
1 1
G
1
1
B,C E D
3
3
= = 2
= 1
= 2 =
= 2 =
E F G
A
2
4
4
3
3
3
3
1
1
1 1
1 1 1
1
1
A B C
A
1 1
B 1
1
C 1 1
D
E
1 1
F
1
G
1
D
1
1
1
B,C
3
3
=
=
=
=
E F
G
1
1
1
1
1
1
1
1
1
A
A
B 1
C 1
D
E
F
G
B C D E F
1 1
1
1
1
1 1
1 1
1 1 1
1 1
1
1
1
A
2
4
4
3
3
3
3
= 2
1
2 =
2 =
G
1
1
1
A
2
4
4
3
3
3
3
B,C E
3
3
=
=
=
=
=
1
2
2
B,C E D G, F
3
3
=
=
=
=
1
1
Figura 48 – Aplicação do algoritmo de Demucron
33
Pelo que no nível 0 temos o nó A, no nível 1 os nós B e C, no nível 2 o nó E, no nível 3 o
nó D e no nível 5 os nós G e F. Ordenando os nós da melhor forma é possível obter a
representação sagital da figura 49.
G
B
A
E
D
C
F
Figura 49 – Grafo resultado
2.3. Árvore geradora mínima ou árvore de ligações mínimas
Problemas deste tipo são muito usados na construção de redes de comunicações, como é o
caso da instalação de uma rede telefónica com o intuito de minimizar os metros de fio
utilizados. Um problema do tipo árvore geradora mínima pode ser visto como um sistema de
rega num jardim da cidade de Ponta Delgada. A Câmara Municipal pretende, a partir de um
sistema de captação de água montar um sistema de rega do jardim com aspersão em locais
predefinidos. A resolução deste tipo de problemas requer um grafo rotulado em arestas,
vejamos o exemplo da figura 35, em que as arestas representam as condutas entre os
diferentes pontos da rede e o peso de cada aresta os custos da instalação (possível) de
condutas. Que condutas devem ser instaladas minimizando o custo total da instalação?
A
B
C
D
E
A B
1
1
6 3
6 3
10 6
C D E
6 6 10
3 3 6
2 7
7
2
7 7
Figura 35 – Matriz de adjacência de um grafo hipotético
A solução do problema é a Árvore Geradora Mínima do último grafo da figura 36. Existem
diferentes métodos de resolução para estes problemas, tais como o método gráfico, o de
Kruscal e o de Prim.
34
O algoritmo óptimo de Kruskal consiste em analisar as arestas por ordem crescente de peso
e aceitar as que não fecham ciclos. Para o exemplo da figura 35 podemos ver a evolução do
algoritmo de Kruskal na figura 36.
D
A
C
C
C
D
A
C
D
A
E
E
E
D
A
E
B
B
B
C
D
A
B
E
B
Figura 36 – Evolução do algoritmo de Kruskal
Somando os pesos das arestas escolhidas, temos a soma dos pesos total 0+1+2+3+6=12,
valor este que é óptimo.
Quanto ao método gráfico é uma heurística que consiste no seguinte, tendo em conta o
grafo da figura 35:
1º Seleccionar a aresta de menor peso que é AB;
2º Seleccionar a aresta de menor peso que ligue a A ou a B. Não seleccionar uma aresta
que estabeleça ciclo(s). A aresta a seleccionar é BC (ou BD pois temos empate nos pesos);
3º Seleccionar a aresta de menor peso que ligue a A, B ou C. Não seleccionar uma aresta
que estabeleça ciclo(s). A aresta a seleccionar é CD;
4º Seleccionar a aresta de menor custo que ligue a A, B, C ou D. Não seleccionar uma
aresta que estabeleça ciclo(s). A aresta a seleccionar é BE.
Na figura 37 temos a Árvore Geradora Mínima igualmente com l = 12.
C
D
A
E
B
Figura 37 – Árvore geradora mínima
35
Outro método de resolução é o algoritmo de Prim que utiliza a matriz de adjacência do
grafo. Novamente, tendo em conta a figura 35, como o grafo é não orientado a matriz é
simétrica sendo por isso suficiente a metade inferior ou superior para aplicar o método de
Prim. A sequência dos passos é a mesma do método gráfico, assim:
1º Seleccionar a aresta de menor peso AB; (para ligar outra aresta a
A B C D
“A” ou “B”, a mesma tem que ter extremos em “A” ou “B”; estes
A
extremos podem ser visualizados cortando com rectas as linhas e
B
colunas de “A” e “B”. As intersecções das rectas indicam as arestas que
C
fecham ciclo(s). Deste modo a escolha seguinte fica facilitada pois será
D
feita sobre as rectas e evitando as intersecções destas;
E
E
7
A B C D E
2º Seleccionar, nas rectas traçadas, a aresta de menor peso que ligue
A
a A ou B. Nas rectas traçadas o menor peso é 3. Sendo assim posso
B
1
escolher BC ou BD. Assinalar a escolha que foi BC e cortar com as
C
6
3
D
6
3
2
E 10 6
7
rectas a linha e coluna de C;
7
A B C D E
3º Seleccionar, nas rectas traçadas, a aresta de menor peso (que
A
ligue a A, B ou C). Nas rectas traçadas o menor peso é 2, com a aresta
B
1
CD. Assinalar a escolha e cortar com rectas a linha e coluna de D;
C
6
3
D
6
3
2
E 10 6
7
7
Figura 38 – Aplicação da heurística de Prim
36
4º Seleccionar, nas rectas traçadas, a aresta de menor peso (que ligue
A B C D E
a A, B, C ou D). Nas rectas traçadas o menor peso é 6 que corresponde a A
BE (note-se que AC, AD e BD originavam ciclos). Assinalar a escolha e B
1
cortar com as rectas a linha e a coluna de E.
C
6
3
D
6
3
2
E
10 6
7
7
Figura 39 - Aplicação algoritmo de Prim
Na matriz as arestas não escolhidas estão em intersecções de rectas pelo que se
seleccionadas formam ciclo(s), estão seleccionadas quatro arestas, igual ao número de vértices
menos um, a Árvore Geradora Mínima está calculada constituída pelo conjunto de arestas AB,
BC, CD e BE com l = 12 sendo a mesma já apresentada na figura 37.
Como subproblema das árvores mínimas podemos querer a árvore geradora máxima,
podemos aplicar todos os métodos utilizados em árvores mínimas bastando para isso
considerar o simétrico dos pesos correspondentes ou então alterar os algoritmos trocando
mínimo por máximo e ordenação dos pesos decrescente por ordenação dos pesos crescente.
Como observação podemos afirmar que, como uma árvore não tem ciclos, são suficientes
duas cores caso se pretenda colorir os seus vértices. O mesmo não se pode dizer para a
coloração de arestas que necessita no máximo de um número igual ao maior grau de entre
todos os vértices.
Para encontrar outros métodos consulte Moret e Shapiro (1991), Karger et al. (1994),
Eppstein (2001), Pradenas (2001) e Drakos (1998).
2.4. Caminho mais curto
Recorrendo ao exemplo das ruas do Ponta Delgada, um problema de caminho mais curto
consiste em, dado um ponto de partida, encontrar um caminho mínimo até um ponto de
destino. Podemos ter um grafo orientado ou não e, mais uma vez, ao tentar minimizar um
caminho temos de ter um grafo rotulado com um peso. Este problema pode parecer idêntico
ao das árvores geradoras mínimas mas, um problema de caminho mais curto não obriga a
passagem por todos os vértices. Também é possível fazer com que um caminho não passe por
37
determinadas arestas bastando para tal atribuir um peso muito elevado a essas arestas. Poderse-ia pensar como métodos de resolução nos mesmos métodos da árvore geradora mínima
mas depressa se chega à conclusão que os resultados não são satisfatórios. Certo é que
existem diversos algoritmos para obter uma solução óptima deste tipo de problema, tais como
os criados por Dijkstra, Floyd, Ford, Faure, Bellman, Hasse entre outros, envolvendo maior
ou menor complexidade de cálculo.
O algoritmo de Dijkstra requer uma matriz de adjacência, com pesos não negativos, de um
grafo. Vamos considerar como pesos as distâncias entre nós adjacentes. Segundo Moura da
Silva (1995) o algoritmo de Dijkstra consiste em, partindo do nó origem, ir em cada iteração
determinando o nó que está a menor distância do nó origem (que passará a ser o nó original)
até se alcançar o nó destino. Por outras palavras, as distâncias dos nós originais ao nó origem
formarão uma sucessão não decrescente uma vez que em cada iteração a distância ao nó
origem é superior ou igual à obtida na iteração anterior. Quando um nó passa a ser um nó
original, todas as ligações directas3 que o têm como destino deixam de ter utilidade e são
eliminadas.
Passemos, agora, à descrição pormenorizada deste algoritmo, utilizando a matriz da figura
35, vamos determinar o caminho mais curto entre A e E. Como forma de ordenar os cálculos
vamos utilizar a tabela da figura 40.
O\D A B C D E
A
B 1
C 6
D 6
E 10
*
1 6
3
3
3 2
6 7
*
*
Dist. Min.
Origem Dist.
6 10
3 6
2 7
7
7
*
*
Figura 40 - Tabela utilizada no Algoritmo Dijkstra
1ª iteração – Dado que o nó A é o nó origem, será por definição o primeiro nó original, pelo
que se podem, desde logo, eliminar todas as ligações que o têm por destino, inscrevendo na
coluna de distâncias a A um zero;
3
Diz-se que existe uma ligação directa entre X e Y se o nó X for adjacente ao nó Y.
38
2ª iteração – A partir do nó A, determina-se qual será o novo nó original seguinte, que, como
se pode verificar na matriz, é o nó B a uma distância de 1, marcando-se com um circulo a
posição correspondente ao arco que estabeleceu esta ligação. Se o nó B passou a ser nó
original, eliminam-se todas as ligações que o têm como destino e inscreve-se na coluna das
distâncias a A o valor 1.
3ª iteração – A partir dos nós originais A e B, vão-se determinar as mínimas distâncias a A.
Origem Destino Distância
A
CeD
0+6=6
B
CeD
1+3=4
Como se pretende o menor valor, o novo nó original será C (também podia ser escolhido D),
eliminando-se todas as ligações com destino a C, marcando com um circulo o arco que
estabeleceu a ligação BC, inscrevendo-se na coluna das distâncias a A o valor 4.
Este processo iterativo vai-se repetindo até se atingir o nó E, destino final do caminho mais
curto a determinar.
4ª iteração – A partir dos nós originais A, B e C determinar as mínimas distâncias a A.
Origem Destino Distância
A
D
0+6=6
B
D
1+3=4
C
D
4+2=6
pelo que o novo nó original será o nó D a uma distância de 4 de A, valor que se inscreve na
coluna respectiva, marcando o arco BD e eliminando-se as ligações com destino D.
5ª iteração – A partir dos nós originais A, B, C e D determinar as mínimas distância a A.
Origem Destino Distância
A
E
0+10=10
B
E
1+6=7
C
E
4+7=11
D
E
4+7=11
pelo que o novo nó original será o nó E a uma distância de 7 de A, valor que se inscreve na
respectiva coluna, marcando o arco BE e como se chegou ao nó destino vamos então ver qual
é o caminho mais curto desde A até E.
O conjunto dos arcos que fazem parte do caminho mais curto vai ser reconstituído do fim
para o princípio utilizando o quadro final. Entrando na coluna do nó E (destino) procura-se o
39
circulo que representa o arco utilizado para chegar a este nó e verifica-se que esse arco tem
origem em B (linha onde está o circulo). Passando para a coluna do nó B, constata-se que se
chegou até ele a partir do nó A, que é o nó origem. Conclui-se, portanto, que o caminho mais
curto desde o nó A até ao nó E passa pelos nós A, B e E com uma distância de 7 conforme se
verifica no último quadro na coluna das distâncias a A, como se pode ver na figura 41.
Figura 41 - Tabela final
De notar, que ao determinar o caminho mais curto de A a E, obtiveram-se, também, as
mínimas distâncias de A a todos os nós originais. Por exemplo de A a D a mínima distância é
4 e o caminho constituído pelo conjunto de nós A, B e D. O conjunto destas mínimas
distâncias é chamado árvore de distâncias mínimas gerada por A.
O grafo do caminho mais curto entre A e E é o seguinte:
B
A
E
6
1
Figura 42 – Grafo do caminho mais curto de A até E
Outro método de resolução é o Algoritmo de Floyd que apesar de ser mais complexo é de
difusão total, ou seja, quando aplicado permite obter o caminho mais curto entre qualquer par
de vértices do grafo. No entanto a aplicação do método supõe que no grafo não existam
circuitos com peso total negativo e sempre que não seja possível estabelecer uma ligação
entre dois vértices considera-se a distância “ + ∞ ” por se tratar de minimização, este método,
também utiliza uma matriz de adjacência com pesos.
O processo é o seguinte:
40
1º passo – Percorrer a matriz, por colunas, elemento a elemento e somar cada elemento c ij
(operador) aos elementos da linha com índice “j” (índice igual ao da coluna do operador); a
linha de valores obtida compara-se com a linha do operador sendo os valores desta linha
substituídos se são superiores aos calculados, ou seja, se existe uma melhoria;
2º passo – Quando se efectuam substituições, ao novo valor de distância agrega-se o índice
da coluna do operador (vértice intermédio) para posteriormente reconstituir o caminho,
3º passo – Quando o operador c ij não é finito ou i = j é desnecessário proceder como referido
no 2º passo.
Vamos considerar o grafo da figura 43 e respectiva matriz de distâncias (km) para calcular
a Matriz de Distâncias Mínimas.
Y
X
3
8
W
7
4
5
Z
14
X
X
Y
Z
W
∞
3
∞
Y
∞
4
8
Z
5
7
∞
W
14
3
∞
3
Figura 43 – Grafo e matriz de distâncias em km
Retomando o grafo proposto e respectiva matriz de distâncias, vejamos como executar os
passos.
41
Tabela 3 – Execução dos passos para a coluna de X
Operador
c XX = 0
Tarefa
Diagonal Principal (i=j) desnecessário
Desnecessário; através de X não é possível
melhorar a distância de Y aos restantes
vértices.
Somar à linha de X obtendo:
3 ∞ 8 17
Comparar com a linha corrente do operador
(linha Z)
3 4 0 ∞
Melhoria para ZW=17 Km passando por X
Registar em ZW 17x
Desnecessário; por X não é possível melhorar
a distância de W aos restantes vértices.
cYX = ∞
c ZX = 3
cWX = ∞
Após percorrida a 1ª coluna (vértice X como ponto intermédio), a matriz de distâncias
apresenta os seguintes valores:
X
X
Y
Z
W
∞
3
∞
Y
∞
4
8
Z
5
7
W
14
3
17x
∞
Figura 44 – Matriz de distâncias
De momento, o caminho mais favorável de Z para W é Z → X → W no total de 17 km.
Terminada a procura de melhores caminhos entre cada par de vértices usando X como ponto
de intermédio, passa-se à coluna seguinte em que o ponto intermédio será o vértice Y seguido
de Z e W, em que a matriz final está exemplificada na figura 45.
X
X
Y
Z
W
10Z
3
18Z
Y
9Z
4
8
Z
5
7
W
12Z
3
7Y
15Y
Figura 45 – Matriz de distâncias mínimas final
Existem outras formas e métodos de resolução deste tipo de problemas como podemos ver
em Morais da Silva (2001), Drakos (1998) e Foster (1995).
42
2.5. Caixeiro viajante
O problema do caixeiro viajante (travelling salesman probleman) é um dos mais notórios
problemas de optimização. O problema pode ser descrito do seguinte modo: um vendedor
parte de sua casa de manhã e tem um conjunto de localidades por onde tem de passar durante
o dia, regressando a casa no final do dia. Por exemplo, ele mora em Ponta Delgada e tem de
visitar Ribeira Grande, Nordeste, Lagoa, Vila Franca, Povoação e regressar a Ponta Delgada
minimizando a distância percorrida.
Um problema do caixeiro viajante (PCV) pode ser formulado tanto como um problema de
caminho mais curto, como um problema de árvore de ligações mínimas ou ambos, uma vez
que envolve as duas formulações em simultâneo.
Considere-se um grafo, em que os vértices representam os referidos concelhos e as arestas
representam as estradas de ligação, a cada aresta está associado um peso, por exemplo a
distância entre concelhos. Este problema implica calcular no grafo um ciclo de Hamilton de
encargo total mínimo. O tempo necessário para a resolução deste problema cresce
exponencialmente com o número de vértices do grafo. Só o método de enumeração, ou seja,
identificação de todos os ciclos possíveis, garante o cálculo da solução óptima do problema
mas tal método é impraticável quando o número de vértices é elevado.
Veja-se que se um computador for capaz de tratar cerca de 10.000 ciclos por segundo,
necessitará aproximadamente de 18 segundos para calcular o óptimo num grafo completo com
10 vértices, 50 dias para um grafo completo com 15 vértices, 2 anos para um grafo completo
com 16 vértices e 193.000 anos para um grafo completo com 20 vértices. É a imensidão
destes tempos que tornou este problema um dos mais famosos e “não resolvidos” problemas
matemáticos.
Sendo assim são utilizadas heurísticas de resolução, a vantagem no uso de heurísticas está
no facto de que elas aumentam a eficiência do processo de busca retornando uma solução boa,
que muitas vezes é a óptima ou próximo do óptimo, em detrimento da exploração de todas as
alternativas. Uma motivação para o seu uso é que a solução óptima do problema raramente é
requerida e as heurísticas raramente apresentam desempenho de “pior caso”4.
4
Pior desempenho possível para uma dada instância.
43
Existem diversos métodos heurísticos de resolução como por exemplo o método do vértice
adjacente mais próximo. É uma das mais simples heurísticas para resolução do PCV. É uma
heurística míope5 que tenta construir um ciclo hamiltoniano baseado na conexão dos nós
vizinhos mais próximos. É um método aproximado que é aplicado do seguinte modo:
1º- Selecciona-se arbitrariamente um vértice “ vi ” para início do ciclo;
2º- Selecciona-se dos vértices ainda não seleccionados o vértice “ vk ” que está à menor
distância de “ vi ”, ficando a cadeia vi , v k . Repete-se este procedimento para o último vértice
agregado até esgotar todos os vértices do grafo.
Veja-se a sua aplicação no grafo orientado com a matriz de distâncias da figura 46.
km
A
B
A
16 12 18 16
B
*
10
C
18
D
14 18
E
8
*
20
C
D
E
18 20 20
*
10
12 12
28 16
*
12
8
*
Figura 46 - Matriz distâncias em km
Vértice inicial: A;
Vértice, não seleccionado, mais próximo de A: C (12 km);
Vértice, não seleccionado, mais próximo de C: E (16 km);
Vértice, não seleccionado, mais próximo de E: B (12 km);
Vértice, não seleccionado, mais próximo de B: D (20 km);
Vértice, não seleccionado, mais próximo de D: A (14 km)
Assim o circuito “quase óptimo”6 é A, C, E, B, D, A com uma distância total de 74 km, para
este problema a solução óptima tem uma distância de 66 km.
5
Uma das técnicas de construção de heurísticas mais explorada é tentar obter uma boa solução, considerando a
cada iteração a melhor decisão de um passo à frente, ou seja, utilizando um critério de optimização meramente
local. Por esta razão, as heurísticas deste tipo são chamadas míopes ou gulosas (greedy).
6
Diz-se circuito quase óptimo por não resultar de um método exacto.
44
Outro método heurístico de resolução é o método da inserção com menor encargo. É mais
um método aproximado que é aplicado do seguinte modo:
•
Selecciona-se o subciclo “i, j, i” associado a Min{cij + c ji } , em caso de empate a
escolha é feita ao acaso;
•
No subciclo corrente, calcular para cada ligação do tipo (u,v) a inserção do vértice
“k” (não seleccionado anteriormente) a que corresponda o aumento mínimo de
distância dado por Min{cuk + c kv − cuv } . Repetir este procedimento até ter
seleccionado todos os vértices do grafo.
Vejamos agora um exemplo de aplicação deste método no grafo orientado com a matriz de
distâncias da figura 46.
Escolha do subciclo inicial
A
B
C
D
ABA=26 ACA=30 ADA=32 AEA=24
BCB=38 BDB=38 BEB=32
CDC=38 CEC=28
DED=20*
O subciclo a estudar é DED com a distância total de 20 km e as inserções possíveis são no
par D, E ou no par E, D. Num segundo passo, tendo em conta a regra Min{cuk + c kv − cuv } sai
que o menor encargo de inserção resulta da escolha do vértice A para inserir no par E, D
ficando o subciclo DEAD com distância total de 34 km. Assim o subciclo DEAD é o novo a
ser estudado vindo como resultado da aplicação desta heurística o circuito “quase óptimo”:
DCEBAD com distância total 66 km.
O método do vértice adjacente mais próximo e o método da inserção com menor encargo
são heurísticas de construção pois constroem uma solução passo a passo, onde para cada
passo se adicionam componentes individuais até encontrar uma solução aceitável. Nem
sempre as heurísticas de construção são satisfatórias se aplicadas em determinados problemas
que requerem uma precisão maior na qualidade da solução obtida. Neste caso, pode-se partir
de uma solução encontrada por uma heurística de construção boa e optimizar o seu custo
usando uma heurística de melhoramento como, por exemplo, a heurística k-opt. Esta
heurística assenta no seguinte, inicia-se com uma solução factível gerada por uma heurística
de construção e excluem-se k arcos, produzindo k segmentos disjuntos. Então o algoritmo kopt reconecta os k segmentos de todas as formas possíveis tentando encontrar circuitos mais
curtos. Se houver melhoria, executa-se o procedimento sobre a solução melhorada, caso
contrário termina-se. As heurísticas mais utilizadas são a 2-opt e a 3-opt.
45
Existem muitos outros métodos heurísticos que podem ser consultados em Marreiros e
Ruchkys (2000), Cervieri e Py (2000), Moscato (1998), Drakos (1998), Morais da Silva
(2001), Bang-Jensen et al. (1998).
2.7. Problema de fluxo máximo numa rede de capacidades limitadas.
Um problema de fluxo máximo consiste no seguinte, imagine que se quer construir uma
rede de condutas de gaz. Cada conduta tem uma capacidade de fluxo que depende
essencialmente do seu diâmetro. Qual deve ser o diâmetro das condutas de forma a maximizar
o fluxo de gás na rede?
Na prática surgem situações que podem ser representadas por um grafo orientado
associando um peso a cada um dos arcos, ou seja, uma dada capacidade que limita a
quantidade de fluxo que nele pode transitar. Assim, pretende-se calcular o fluxo máximo que
a rede suporta desde um ponto inicial – Entrada da rede, até atingir um ponto final – Saída da
rede.
O grafo da figura 50 representa um sistema viário, de uma zona urbana, entre o largo L e a
praça P. Os arcos representam o sentido obrigatório do trânsito, indicando-se para cada um
deles a capacidade máxima de tráfego em viaturas/hora. Quantas viaturas/hora podem, no
máximo, atingir a praça P?
A
70
B
L
D
30
60
70
E
30
80
60
30
40
70
70
30
C
P
20
F
Figura 50- Sistema viário
46
Como pode ser visto em Morais da Silva (2001), este problema pode ser resolvido usando
um modelo de programação linear. Para formalizar o problema é necessário atender aos
pressupostos seguintes:
O grafo tem nós Inicial e Final únicos e distintos (Entrada e Saída da rede);
•
O grafo é orientado tendo cada um dos arcos uma dada capacidade c ij finita;
•
O fluxo que percorre a rede satisfaz as condições seguintes
•
•
Não se altera com o tempo;
•
É infinitamente divisível em cada arco (i,j), tendo valor x ij tal que 0 ≤ xij ≤ cij ;
Nos nós intermédios (distintos dos nós de Entrada e Saída da rede) verifica-se o
princípio da conservação do fluxo, ou seja, o fluxo recebido em qualquer destes nós é
igual ao fluxo saído do mesmo.
Vejamos então o modelo de Programação Linear.
Variáveis de Decisão: uma por cada arco (i,j) representando o fluxo (viaturas/hora) que
nele transita;
Função Objectivo: fluxo máximo em P (número máximo de viaturas que atinge P) que é
igual à soma dos fluxos nos arcos incidentes para o interior de P:
Max f(P)= x DP + x EP + x FP
Atendendo a que o fluxo em P tem que ser igual ao fluxo saído de L, a função também
pode ser definida por Max f(L)= x LA + x LB + x LC
Restrições Técnicas: Tendo o grafo “N” nós há “N-2” nós intermédios e
consequentemente “N-2” restrições de conservação de fluxo (serão expressas na forma
geral fluxo que sai = fluxo que entra, ou seja, fluxo que sai – fluxo que entra = 0)
vértice A: x AD + x AE − x LA = 0
; vértice C: xCE + xCF − x LC = 0 ;
vértice B: x BD + x BE + x BF − x LB = 0 ; vértice D: x DP − x AD + x BD = 0 ;
vértice E: x EP − x AE − x BE − xCE = 0 ; vértice F: x FP − x BF − x CF = 0
Dado que cada uma das Variáveis de Decisão associada a cada um dos arcos do grafo, tem
limite superior igual à capacidade do arco têm-se as restrições de capacidade:
47
x LA ≤ 70; x LB ≤ 80; x LC ≤ 60;x AD ≤ 30;x AE ≤ 40;x BD ≤ 30;x BE ≤ 30;
x BF ≤ 60;xCE ≤ 30;xCF ≤ 20;x DP ≤ 70;x EP ≤ 70;x FP ≤ 70;
Restrições Lógicas de não negatividade:
x LA ,x LB ,x LC ,x AD ,x AE ,x BD ,x BE ,x BF ,xCE ,x DP ,x EP ,x FP ≥ 0
Outro algoritmo utilizado para resolver o problema do fluxo máximo é o método de FordFulkerson que data de 1962.
Para aplicar o método é necessário que a rede tenha um nó inicial único. Quando tal não
sucede, considera-se um nó inicial fictício ligando-o aos nós iniciais da rede por arcos com
capacidade igual à “oferta” dos vértices reais da rede. Na figura 51, dois depósitos de água
com capacidades de 50.000 e 20.000 litros alimentam uma rede de distribuição. Para dispor de
uma entrada única na rede, considera-se o vértice inicial fictício ligado aos depósitos por
arcos de capacidade igual à capacidade máxima dos depósitos.
50.000
Fictício
20.000
Figura 51 - Introdução de nós fictícios
Por vezes, pretende-se estudar uma rede sem que existam quaisquer origens com oferta de
fluxo à rede. Nesses casos, é necessário considerar uma entrada fictícia na rede ligada aos nós
iniciais com arcos de capacidade infinita. Quando estas situações ocorrem no final da rede
procede-se de modo idêntico com um nó final fictício.
Vejamos algumas noções necessárias à compreensão do problema de fluxo. Se num grafo o
arco (i, j) com capacidade c ij transporta o fluxo ϕ ij a sua capacidade restante é c ij − ϕ ij ,
diz-se que um arco está saturado quando a sua capacidade restante é nula. Para o cálculo do
fluxo máximo só interessa analisar trajectórias elementares com extremos inicial e final
respectivamente na entrada e saída da rede. Uma trajectória que não repete nós, com fluxo não
48
negativo em qualquer dos seus arcos e em que pelo menos um destes está saturado é chamada
trajectória elementar saturada.
Se no grafo orientado se relaxar o sentido dos arcos e definir-se uma sucessão de arestas
sem repetir vértices tem-se uma cadeia elementar. Se ao percorrer as arestas da cadeia for
reactivado o sentido dos arcos originais, haverá arcos percorridos no sentido directo e outros
no sentido inverso. Uma cadeia diz-se saturada quando se verifica, pelo menos, uma das
seguintes situações:
pelo menos um arco tem, no sentido directo, capacidade restante nula;
pelo menos um arco tem, no sentido inverso, fluxo nulo;
Resulta assim que enquanto houver no grafo uma ou mais cadeias elementares não
saturadas ligando a entrada e saída da rede é possível reencaminhar fluxo e aumentar o total
que atinge a saída da rede.
O método de Ford-Fulkerson para o cálculo do fluxo máximo é o seguinte.
1º passo – saturar todas as trajectórias elementares que ligam a entrada e a saída da rede;
2º passo – saturar todas as cadeias elementares que ligam a entrada e a saída da rede.
Vamos ver a aplicação deste método no exemplo da figura 50.
Na tabela 4 apresenta-se o 1º passo.
Tabela 4 – Saturação dos arcos
Trajectória
L-A-D–P
L-A-E-P
L-B-D-P
L-B-E-P
L-B-F-P
L-C-F-P
Arco(s) com menor capacidade
restante
(A,D)=30
(L,A)=40; (A,E)=40
(B,D)=30
(B,E)=30; (E,P)=30
(L,B)=20
(C,F)=20
Fluxo saturante Arco(s) saturado(s)
30
40
30
30
20
20
(A,D)
(L,A); (A,E)
(B,D)
(B,E); (E,P)
(L,B)
(C,F)
Todas as trajectórias elementares de L a P estão saturadas como se pode ver na figura 52,
pelas arestas a vermelho.
49
A
70
L
B
80
60
30
40
D
30
60
70
E
30
70
70
30
C
P
20
F
Figura 52 – Grafo com trajectórias elementares saturadas
Terminado o 1º passo, de L o fluxo total é 70+80+20=170 acumulando P esse fluxo.
2º passo – Para detectar uma cadeia não saturada de L a P proceda-se do seguinte modo:
em P pode atingir-se no sentido directo quer de D quer de F pois DP e FP não estão
saturados; em D não pode ser atingido no sentido directo quer de A quer de B pois são arcos
saturados; não se põe a hipótese de ser atingido no sentido inverso pois isso conduzia a P já
estudado; em F para encaminhar fluxo para P só o pode receber a partir de B no sentido
directo pois há capacidade restante em BF pelo que B deve ser analisado; em B só pode ser
atingido no sentido inverso a partir de E pois o arco BE tem fluxo pelo que devo estudar E;
não se coloca a hipótese de ser atingido no sentido inverso a partir de F pois já se concluiu
que só usando BF é possível aumentar o fluxo que atinge F; em E pode atingir-se a partir de C
no sentido directo pois CE não está saturado pelo que estudo C; C pode atingir-se a partir de L
no sentido directo pois LC não está saturado.
Porque é possível partir de L e atingir P pela cadeia elementar não saturada
L → C → E ← B → F → P o fluxo em P não é máximo. Percorrendo a cadeia e registando:
•
a capacidade restante nos arcos percorridos no sentido directo (L,C)=40, (C,E)=30,
(B,F)=40; (F,P)=30
•
o fluxo dos arcos percorridos no sentido inverso (B,E)=30
fixa-se o menor deste valores α = 30. Percorre-se agora a cadeia com o fluxo α = 30 :
50
•
somando-o nos arcos percorridos no “sentido directo”
•
subtraindo-o nos arcos percorridos no “sentido inverso”
O fluxo em P que era de 170 unidades passou a ser de 170+30=200 unidades. Será máximo?
É necessário prosseguir com a saturação das cadeias elementares de L a P. Em P o fluxo só
aumenta se recebido de D pois só DP não está saturado pelo que estudo D e em D não pode
ser recebido mais fluxo pois os arcos AD e BD estão saturados. Assim sendo, as cadeias
elementares de L e P estão saturadas terminando o 2º passo.
A solução óptima é então, atingem a praça P, 200 viaturas/hora. A título de curiosidade
veja-se que o arruamento BE, com fluxo nulo, podia ser encerrado ao trânsito pois
teoricamente é desnecessário.
No caso de apenas se querer conhecer o valor do fluxo máximo do nó origem para o nó
destino e, nomeadamente, se se tratar de uma rede de grandes dimensões, é possível resolver
este problema recorrendo ao teorema do fluxo máximo.
Teorema do Fluxo Máximo
Para toda a rede com uma só origem e um só destino o fluxo máximo é igual ao valor
mínimo de corte de entre todos os cortes possíveis da rede.
Um corte é um conjunto de arcos contendo, pelo menos, um arco de cada trajectória da
origem ao destino. O valor de corte é a soma das capacidades de fluxo de todos os ramos do
corte, no sentido da orientação definida pelo corte.
Na figura 53, apresentam-se alguns dos cortes da rede dada na figura 50 (não se traçaram
os restantes de modo a que a figura não ficasse incompreensível). Note-se que, a figura está
desenhada de tal modo que nenhum destes cortes indica o fluxo máximo da rede, ou seja não
é fácil identificar o que tem menor valor de corte.
51
200
B
80
60
30
40
70
L
250
A
210
D
30
60
70
E
30
P
70
70
30
C
210
20
F
Figura 53 – Exemplos dos cortes da rede
Podemos encontrar mais informação sobre fluxo em Drakos (1998), Morais da Silva
(2001) e Moura da Silva (1995)
2.8. Outros Problemas
Existem muitos outros tipos de Problemas de Optimização Combinatória em Grafos e
como tal não é possível fazer referência a todos neste trabalho, no entanto é apresentado a
seguir mais uns problemas sem no entanto se estudar os seus algoritmos e heurísticas de
resolução.
Assim, os problemas de scheduling ou planeamento no tempo não são mais do que
problemas que tentam encontrar um mapeamento de tarefas óptimo. Por exemplo, num
Hipermercado nem sempre são necessárias todas as caixas estarem em funcionamento, cada
trabalhador tem um número máximo de horas de trabalho diário e semanal e existem mais do
que dois empregados por isso é necessário fazer um mapeamento dos horários de cada
trabalhador do caixa para que este esteja o número certo de horas diárias em serviço e que o
hipermercado também fique satisfeito com a presença dos funcionários nas horas em que estes
são realmente precisos.
Quem é que não ficaria confuso se uma lista telefónica não estivesse ordenada por nomes.
Como já foi visto, os próprios problemas de ordenação estão inseridos em muitos outros
problemas de optimização pois quando se quer procurar um caminho mais curto, por exemplo,
é necessário saber se uma aresta escolhida é realmente a de menor valor. Existem diversos
52
algoritmos para ordenar um conjunto de dados como podemos ver em Setzer e Carvalheiro
(1993).
Os problemas de transportes podem ser vistos como uma união de diversos problemas de
optimização em rede. Pois um padeiro ao distribuir o pão deve querer minimizar o seu
percurso, levar o maior número de pão na carrinha e tem os seus pontos de distribuição por
onde tem de passar, geralmente chama-se problema da mochila a este tipo de problema. No
entanto, um problema de transporte pode ter mais factores, é que por exemplo um padeiro não
tem o menor interesse em ficar com pão no fim do dia por isso ele também tem de optimizar a
sua produção/venda diária.
Um problema de gestão de projectos pode ser visto do seguinte modo: se um padeiro
pretende maximizar a produção diária de fabrico de pão, então é necessário fazer um
escalonamento de tarefas para que cada tarefa possa ser iniciada assim que possível, por
exemplo, deve poder aproveitar enquanto o pão está no forno para amassar nova massa. É
através da gestão de projectos que se consegue planear como vai ser o dia de trabalho, qual a
sequência das tarefas, a duração total do projecto e se se vai precisar de mais recursos para
cumprir a tarefa que foi proposta.
Um tipo de problema que pode não ser muito útil em termos económicos mas que em
termos pessoais pode ser interessante são os diversos tipos de jogos e problemas existentes
que utilizam a Optimização Combinatória e a Teoria dos Grafos. Vejamos o seguinte exemplo
que pode ser representado num grafo de estados (os nós representam diferentes estados do
sistema e os arcos transições de estados).
A banda U2 tem um concerto que começa daqui a 19 minutos e todos precisam atravessar
uma ponte para chegar lá. Todos os quatro elementos estão do mesmo lado da ponte. É de
noite, na ponte só podem passar no máximo duas pessoas de cada vez. Só há uma lanterna.
Qualquer pessoa que passe, uma ou duas, deve passar com a lanterna na mão. A lanterna deve
ser levada de um lado para o outro, e não pode ser atirada. Cada elemento da banda tem um
tempo diferente para passar de um lado para o outro de acordo com a carga. O par deve andar
junto e segundo o tempo do menos veloz.
•
Bono : 1 minuto para passar;
•
Edge: 2 minutos para passar;
53
•
Adam: 5 minutos para passar;
•
Larry: 10 minutos para passar.
Por exemplo, se o Bono e o Larry passarem juntos, vai demorar 10 minutos até que eles
cheguem ao outro lado. Se o Larry regressar com a lanterna, 20 minutos terão passado e o
concerto sofrerá um atraso. Como organizar a travessia?
Proposta de resolução:
Como tenho de chegar em menos de 19 minutos e fazer um mínimo de 5 travessias, podese concluir que o Larry só deve passar a ponte uma única vez. Como as travessias de regresso
devem ser feitas no menor espaço de tempo, o Bono é que deverá fazer todas as passagens
pela ponte, assim, será sempre o segundo elemento do par que atravessa a ponte.
Uma das possíveis sequências para a travessia é a seguinte, o Larry e o Bono vão juntos na
primeira travessia, no regresso o Bono transporta a lanterna, volta a fazer mais uma travessia,
a segunda em grupo, na companhia do Adam e regressa mais uma vez com a lanterna e faz a
terceira e última travessia em grupo com o Edge. Como é sabido as travessias são feitas
sempre segundo o tempo do mais lento, assim, somando esses tempos temos:
10+1+5+1+2=19, pelo que é possível organizar a travessia da ponte sem haver atraso no
espectáculo.
54
Capítulo 3 – Caso de Estudo
Este último capítulo tem como objectivo por em prática um pouco do trabalho teórico feito
até aqui. Como já foi visto no capítulo 2, o método de coloração de vértices de um grafo pode
ser utilizado na elaboração de mapas de exames. Uma vez que os mapas de exames geram
sempre muitos problemas e situações de discórdia por parte dos alunos, visto ser frequente
haver situações de coincidência de exames, ou seja, exames que estão agendados para o
mesmo dia, vai-se tentar obter um mapa de exames em que estas situações de coincidências
ocorram no menor número possível, dando assim uma imagem geral das dificuldades sentidas
na elaboração dos referidos mapas.
O regulamento académico em vigor na Universidade dos Açores permite aos alunos a
inscrição em cada disciplina num dos dois regime, o ordinário e o voluntário. O mapa de
exames finais de cada um dos semestres é afixado no início do semestre, durante o período de
inscrição. O mapa de exames da época de recurso é afixado no final do 2º semestre e é mais
difícil de elaborar, dado o novo regime, já que os alunos ao efectuarem a inscrição numa
disciplina ficam admitidos a exame na época de recurso no caso de não terem obtido
aproveitamento durante o semestre lectivo (alunos ordinários) ou no exame final (alunos
voluntários).
O caso de estudo é feito apenas para o curso de Matemática (ensino de) que conta com 35
disciplinas obrigatórias e mais duas de opção, estando apenas disponível este ano quatro
disciplinas para opção. Mas uma vez que não houve inscrições em Geometria Projectiva esta
disciplina não foi incluída no caso de estudo.
Podemos ver o mapa das disciplinas no Anexo 1. Para facilitar o trabalho foi atribuído um
número a cada disciplina e uma cor às disciplinas do mesmo ano. Os números e as cores
foram atribuídos sem qualquer critério de selecção pelo que não influenciam o resultado final.
Numa primeira análise podemos pensar que se um aluno pode ir a exame apenas por estar
inscrito na disciplina, que os dias necessários para o mapa de exames são tantos quantas as
disciplinas. No entanto, existem disciplinas que são precedência de outras disciplinas pelo que
um aluno não pode estar matriculado em ambas no mesmo semestre, ou seja, não pode fazer
ambos os exames o que diminui o número de dias necessários. Outro aspecto a ter em conta é
que o mapa de exames não vai considerar o caso de melhorias na época de recurso, pois isso
55
só aumentava o número de dias necessário e um aluno dispõe de três épocas de exame para
efectuar as melhorias.
Temos então um grafo em que cada uma das disciplinas corresponde a um vértice e dois
vértices são adjacentes sempre que exista pelo menos um aluno que possa efectuar exame nas
duas disciplinas correspondentes aos vértices, i.e., as duas disciplinas não podem ter exames
marcados para o mesmo dia. No Anexo 2, temos a matriz de adjacência das disciplinas,
utiliza-se não um código binário de 0 e 1 mas cores para indicar a adjacência dos vértices. As
células a branco significam a não adjacência dos vértices e as células a azul, vermelho, verde
e amarelo indicam a adjacência entre os vértices. As células a branco devem-se à existência
de precedências entre as disciplinas e como a matriz é simétrica a parte inferior não é
apresentada.
No caso da disciplina 12 esta é precedência da disciplina 14 que por sua vez é precedência
das disciplinas 26 e 28, pelo que na matriz temos que a disciplina 12 também é precedência
das disciplinas 26 e 28.
Como o grafo das disciplinas não é planar, não podemos utilizar o teorema das quatro
cores pelo que são necessárias mais do que quatro cores para colorir os vértices do grafo.
Para ajudar na elaboração dos mapas foi utilizado um programa informático elaborado por
Morais da Silva (2001) que recorre à heurística baseada no nível de saturação e grau de cada
vértice, já apresentada no capítulo 2.
Figura 54 – Janela de visualização do programa utilizado
56
No Anexo 3 pode ser consultada a matriz de adjacências das disciplinas do primeiro
semestre. O número mínimo de dias para conseguir um mapa de exames, para o primeiro
semestre, em que todo o aluno realize no máximo um exame por dia, é de 16 dias.
Tabela 5 - Resultado da coloração dos vértices do grafo do Anexo 3
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6 Cor n.º 7 Cor n.º 8
Vértices
Vértices
1
3
22
21
35
33
16
31
Cor n.º 9 Cor n.º 10 Cor n.º 11 Cor n.º 12 Cor n.º 13 Cor n.º 14 Cor n.º 15 Cor n.º 16
29
12 e 26
15
8 e 25
23
5
36
10
Este resultado não é único já que, no primeiro semestre, a disciplina 8 é precedência das
disciplinas 10 e 25 podendo cada uma delas ser agendada no dia da disciplina 8, no caso da
disciplina 12 como é precedência apenas da disciplina 26, estas vão estar sempre agendadas
no mesmo dia.
Pelo que podemos ver que as disciplinas com precedências permitem a redução no número
de dias, sendo possível realizar no mesmo dia os exames das disciplinas 12 e 26 bem como os
exames das disciplinas 8 e 25, não sendo por isso considerado uma coincidência de exames.
Este ano lectivo de 2000/2001 a época de exames do primeiro semestre decorreu entre 1 de
Fevereiro e 15 de Fevereiro dispondo de 13 dias úteis (é possível a realização de exames num
sábado), existindo no mínimo três coincidências de exames, uma vez que não devem ser
realizados mais exames nos dias das disciplinas 8, 12, 25 e 26 tendo em conta o resultado da
tabela 5.
No Anexo 4 está representado, por uma matriz de adjacências, o grafo das disciplinas do
segundo semestre e o número mínimo de dias para conseguir um mapa de exames, em que
todo o aluno realize no máximo um exame por dia, é de 18 dias.
Tabela 6 – Resultado da coloração dos vértices do grafo do Anexo 4
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6 Cor n.º 7 Cor n.º 8 Cor n.º 9
Vértices
6
2e4
17
34
30
14 e 28
27
11
13
Cor n.º 10 Cor n.º 11 Cor n.º 12 Cor n.º 13 Cor n.º 14 Cor n.º 15 Cor n.º 16 Cor n.º 17 Cor n.º 18
Vértices
32
9
20
7
38
18
37
19
24
Mais uma vez, este resultado não é único já que, no segundo semestre, a disciplina 2 é
precedência das disciplinas 4, 19 e 24 podendo cada uma delas ser agendada no dia da
57
disciplina 2, no caso da disciplina 14 como é precedência apenas da disciplina 28, estas vão
estar sempre agendadas no mesmo dia.
Os exames do segundo semestre, neste ano lectivo de 2000/2001, estão agendados para o
período que decorre entre 4 de Julho e 17 de Julho, estando disponíveis 12 dias úteis. Mais
uma vez as precedências permitiram a redução no número de dias, sendo possível realizar no
mesmo dia os exames das disciplinas 2 e 4 bem como os exames das disciplinas 14 e 28, não
sendo por isso considerado uma coincidência de exames. Como são necessários 18 dias é fácil
concluir que terão de existir no mínimo seis coincidências, já que não devem ser realizados
mais exames nos dias das disciplinas 2, 4, 14 e 28, o que vai dar exactamente dois exames
marcados em cada dia, tendo em conta o resultado da tabela 6.
À primeira vista poder-se-á afirmar que o número disponível de dias para a execução de
exames é muito inferior ao realmente necessário mas, como pode ser verificado, o facto de os
mapas de exames serem afixados no início de cada semestre ajuda os alunos na gestão da sua
matrícula nas disciplinas.
Para os exames da época de recurso e tendo em conta a matriz do Anexo 2, o número
mínimo de dias para conseguir um mapa de exames, em que todo o aluno realize no máximo
um exame por dia, é de 33 dias.
Tabela 7 - Resultado da coloração dos vértices do grafo do Anexo 2
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6 Cor n.º 7 Cor n.º 8 Cor n.º 9
Vértices
1
2 e 24
20
17
16
36
30
15
29
Cor n.º 10 Cor n.º 11 Cor n.º 12 Cor n.º 13 Cor n.º 14 Cor n.º 15 Cor n.º 16 Cor n.º 17 Cor n.º 18
Vértices 12, 14 e 28
35
27
26
22
13
8 e 25
34
10
Cor n.º 19 Cor n.º 20 Cor n.º 21 Cor n.º 22 Cor n.º 23 Cor n.º 24 Cor n.º 25 Cor n.º 26 Cor n.º 27
Vértices
9
33
7
32
3e6
11
5
38
18
Vértices
Cor n.º 28 Cor n.º 29 Cor n.º 30 Cor n.º 31 Cor n.º 32 Cor n.º 33
31
37
21
19
23
4
Este resultado não é único pois podemos alterar a colocação das disciplinas com
precedências sem alterar o número mínimo de dias. O número mínimo de dias foi reduzido
pelo facto de haver precedências entre as disciplinas e note-se que sendo a disciplina 12
precedência das disciplinas 14 e 28 foi possível agendar três exames no mesmo dia sem haver
coincidências. Os exames da época de recurso, neste ano lectivo de 2000/2001, estão
agendados para o período que decorre entre 3 de Setembro e 22 de Setembro, estando
58
disponíveis apenas 18 dias úteis, um número muito inferior ao pretendido e por essa razão
existem dias em que vão ser realizados três exames havendo coincidências, ou seja, existe a
possibilidade de um aluno ter de efectuar os três exames.
Pelo facto de não ser aceitável o mapa de exames da época de recurso e porque este é
lançado durante o segundo semestre, no Anexo 5 foi feita uma matriz com as disciplinas em
que cada aluno está realmente matriculado e não com as disciplinas que estão disponíveis para
matrícula. Com base nessa matriz foi feita uma matriz de adjacência das mesmas disciplinas
no Anexo 6, em que as células a branco significam a não adjacência dos vértices (não existem
alunos matriculados em simultâneo nas disciplinas dos vértices) e as células a azul, vermelho,
verde e amarelo indicam a adjacência entre os vértices (existe pelo menos um aluno
matriculado em simultâneo nas disciplinas dos vértices).
Como não podia deixar de ser, foi necessário ter em conta as precedências e é possível um
aluno no final do ano estar matriculado em disciplinas que tinham precedência desde que
estas sejam em semestres diferentes, por exemplo um aluno que se matricule no primeiro
semestre na disciplina 12 e que obtenha aproveitamento na disciplina pode no segundo
semestre efectuar inscrição na disciplina 14, o que já não é possível é fazer exame da
disciplina 12 e 14 pois se tem de fazer exame da disciplina 12 é porque não teve
aproveitamento e consequentemente não foi possível efectuar a inscrição na disciplina 14.
Tendo em conta este aspecto, no Anexo 7 temos uma matriz de adjacências em que as células
a branco significam a não adjacência dos vértices (não existem alunos matriculados em
simultâneo nas disciplinas dos vértices ou então uma das disciplinas é precedência da outra) e
as células a azul, vermelho, verde e amarelo indicam a adjacência entre os vértices (existe
pelo menos um aluno matriculado em simultâneo nas disciplinas dos vértices que não são
precedência).
Utilizando a matriz de adjacências do Anexo 7, temos que o número mínimo de dias para
conseguir um mapa de exames, em que todo o aluno realize no máximo um exame por dia, é
de 21 dias. Este valor é inferior aos 33 dias da primeira tentativa, em que apenas se
considerava as precedências entre disciplinas, no entanto continua a ser superior aos 18 dias
úteis realmente existentes. Um dos possíveis resultados é o que se encontra na tabela 8
realçando mais uma vez que o resultado não é único pois podemos jogar com a colocação das
disciplinas com precedência sem alterar o número mínimo de dias.
59
Tabela 8 - Resultado da coloração dos vértices do grafo do Anexo 7
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6 Cor n.º 7
Vértices
5
1
2
20
13
12
25
35
21
30
28
14
31
26
Vértices
Vértices
Cor n.º 8 Cor n.º 9 Cor n.º 10 Cor n.º 11 Cor n.º 12 Cor n.º 13 Cor n.º 14
7
18
15
9
17
29
16
8
27
22
24
36
32
33
10
Cor n.º 15 Cor n.º 16 Cor n.º 17 Cor n.º 18 Cor n.º 19 Cor n.º 20 Cor n.º 21
3
34
11
19
23
4
37
6
38
A matriz do Anexo 7 ainda pode ser dividida em duas matrizes uma para o primeiro
semestre no Anexo 8 e outra para o segundo semestre no Anexo 9. O estudo destas matrizes
pode parecer supérfluo uma vez que as matrículas são feitas depois da afixação dos mapas,
mas por outro lado, vai reforçar a importância da saída dos mapas antes das matrículas, pois
mostra que é necessário efectuar uma escolha entre a matrícula numa disciplina no regime
ordinário ou no regime voluntário, consoante a necessidade de cada aluno frequentar
determinadas cadeiras, na medida em que os resultados das tabelas 9 e 10 já não excedem o
número de dias úteis disponível para os exames de fim de semestre.
Tabela 9 - Resultado da coloração dos vértices do grafo do Anexo 8
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6
Vértices
5
1
3
8
25
12
35
16
22
31
26
Cor n.º 7 Cor n.º 8 Cor n.º 9 Cor n.º 10 Cor n.º 11
Vértices
10
15
29
23
36
21
33
Tabela 10 - Resultado da coloração dos vértices do grafo do Anexo 9
Vértices
Vértices
Cor n.º 1 Cor n.º 2 Cor n.º 3 Cor n.º 4 Cor n.º 5 Cor n.º 6
34
2
14
27
13
20
4
28
32
7
30
Cor n.º 7 Cor n.º 8 Cor n.º 9 Cor n.º 10 Cor n.º 11 Cor n.º 12
11
18
9
17
19
6
38
24
37
Poder-se-ia melhorar os valores aqui encontrados, mas para isso torna-se necessário mais
informação, o que infelizmente não foi possível, pois tendo acesso a uma lista dos alunos
60
inscritos em regime voluntário as matrizes dos Anexos 3 e 4 iriam ter muitas mais células em
branco o que implicaria uma redução no número mínimo de dias necessário para a realização
de exames no fim de cada semestre. Para que a matriz do Anexo 7 ficasse com mais células
em branco era necessário aceder a uma lista dos alunos que obtiveram aproveitamento nas
disciplinas do primeiro semestre, digo apenas do primeiro semestre pois o mapa da época de
recurso é feito durante o segundo semestre não sendo possível saber se os alunos vão ou não
ter aproveitamento durante esse semestre.
Como foi possível verificar, a elaboração de mapas de exame não é uma tarefa fácil. No
entanto, após a aplicação do método de coloração de vértices de um grafo já se tem um bom
ponto de partida em que não existem coincidências entre exames, todavia, dado o reduzido
número de dias úteis de cada uma das três épocas de exames, essas coincidências são quase
impossíveis de evitar. Por isso, sempre que haja necessidade de duas disciplinas ficarem
coincidentes deve-se ter em conta, o momento de realização de cada exame (obrigatoriamente
um de manhã e um de tarde), o número de alunos com coincidência (a escolha deve ser feita
entre as disciplinas com menor número de alunos em comum) e, acima de tudo, o interesse
dos alunos e não a disponibilidade das salas e dos professores.
61
Conclusão
No início da realização desta monografia senti dificuldades na pesquisa bibliográfica.
Recorri à internet, um dos recursos ao meu dispor, mas dado que as fontes de informação nem
sempre eram fidedignas apelei à ajuda do meu orientador que me sugeriu então um “bom”
suporte bibliográfico.
Também encontrei dificuldades em condensar toda a informação disponível dado a
diversidade de subproblemas de um mesmo problema. Assim, foi feita para cada um dos
casos uma apresentação do problema geral.
Apesar das dificuldades, também houve momentos de satisfação pelo trabalho que estava a
desenvolver, uma vez que considero este tema muito interessante e com utilidade para o
futuro.
62
Referências Bibliográficas
Consultadas
•
Gondran, M. e Minoux, M., Graphes et Algorithmes, Collection de la Direction des
Études e Recherches d’Électricité de France, 1979.
•
Harary, Frank, Graph Theory, Addison-Wesley Publishing Company, 1969.
•
Mendes, Armando, Folhas de Investigação Operacional, 2000.
•
Moura da Silva, Rui, Optimização em Redes e Grafos, Associação dos Estudantes
do Instituto Superior Técnico, 1995.
•
Silva, Ilda, Tópicos de Matemática Finita, Associação dos Estudantes da Faculdade
de Ciências de Lisboa, 1992.
•
Bang-Jensen, Jorgen; El Haddad, Mohammed; Manoussakis, Yannis e Przytycka,
Parallel algorithms for the hamiltonian cycle and hamiltonian path problems in
semicomplete bipaarty digraphs, 1998. http://citeseer.nj.nec.com/bangjensen98parallel.html
•
Bernard, M.E. Moret e Shapiro, Henry D., How to Find a Minimum Spanning Tree
in Practice, 1991. http://citeseer.nj.nec.com/moret91how.html
•
Bridgeman, Stina; Garg, Ashim e Tamassia, Roberto, A Graph Drawing and
Translation Service on the WWW, 2001. http://citesser.nj.nec.com/context/1033/0
•
Buriol, Luciana Salete, Implementação Distribuída de um A-Teams para a solução
do Problema do Caixeiro Viajante, 1997.
http://www.inf.ufsm.br/etctal/mono/1997-40.html
•
Caldwell, Chris K., http://www.utm.edu/cgibin/caldwell/tutor/departments/math/graph/intro, 1995.
•
Cervieri, Alexandre e Py, Mônica, Algoritmo para resolução do problema do
Caixeiro Viajante, 2000.
http://www.inf.ufrgs.br/procpar/disc/cmp134/trabs/T2/001/mpisalesman/
63
•
Drakos, Nikos, http://www.orie.cornell.edu/~or115/fall98/handout4/node1.html,
1998.
•
Eppstein, David, http://www.ics.uci.edu/~eppstein/, 2001.
•
Felsner, Stefan, Interval Orders: Combinatorial Structure and Algorithms, 1992.
http://www.inf.fu-berlin.de/~felsner/publist.html
•
Foster, Ian, http://www-unix.mcs.anl.gov/dbpp/text/node35.html, 1995.
•
Karger, David R.; Klein, Philip N. e Tarjan, Robert E., A Randomized Linear-Time
Algorithm, 1994. http://citeseer.nj.nec.com/karger95randomized.html
•
Marreiros, Ana e Ruchkys, Danielle, Estudo da NP-Completude e Algoritmos de
Aproximação para o Problema do Caixeiro Viajante, 2000.
http://www.ime.usp.br/~dpr/
•
Morais da Silva, António Carlos, http://www.gocities.com/ms_io, 2001.
•
Moscato, Pablo, http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html,
2000.
•
Pradenas, Lorena, http://www.udec.cl/~grafos/grafos/index.html, 2001.
•
Reed, Isaac, http://mathforum.com/~isaac/problems/bridges1.html, 2001.
•
Setzer, Valdemar W. e Carvalheiro, Fábio H., Algoritmos e sua análise – uma
introdução didática, 1993. http://www.ime.usp.br/~vwsetzer
•
Six, Janet M., Kakoulis, Konstantinos G. e Tollis, Ioannis G., Techniques for the
Refinemente of Ortogonal Graph Drawings, 2000.
http://citesser.nj.nec.com/context/1033/0
•
Thomas, Robin, http://www.math.gatech.edu/~thomas/FC/fourcolor.html, 1995.
•
Toft, Bjarne, www.imada.sdu.dk/~btoft, 2000.
•
Trick, Michael, http://mat.gsia.cmu.edu/COLOR/color.html, 1994.
64
Não consultadas
•
Harary, Frank, Wilcox, G., Boolean operations on graphs, Math. Scand. 20, 1967.
•
Kaufmann, A., Coster, D., Exercices de Combinatorique avec Solutions, Dunod,
1970.
•
Müller, Felipe M., Heurísticas e Metaheurísticas, Anais da V Escola Regional de
Informática, 1997.
•
Zykov, A. A., One some properties of linear complexes, (Russian) Mat. Sbornik 24
(1949), Amer. Math. Soc. Translation N. 79, 1952.
DEPARTAMENTO DE MATEMÁTICA
Secção de Estatística e Investigação Operacional
Abel Carneiro ©
Carneiro, Abel (2001) “Grafos, Problemas de Optimização
Combinatória e Algoritmos” Monografias da SEIO. Depto.
Matemática da Univ. dos Açores: Ponta Delgada,
www.uac.pt/~amendes (ID 54.505)
O trabalho apresentado é da exclusiva responsabilidade do aluno que o assina. O Departamento
de Matemática e a Universidade dos Açores não se responsabilizam por eventuais erros
existentes no mesmo.
Os textos podem ser descarregados livremente, impressos e utilizados para ensino ou estudo
dos temas a que se referem. No entanto, não podem ser copiados ou incluídos noutros trabalhos
académicos ou de qualquer outra natureza, sem o consentimento do autor e a devida referência
completa. Para autorização de cópia parcial ou integral, utilize o endereço de correio electrónico:
[email protected]
65