MATEMÁTICA DISCRETA
GRAFOS (4/4)
Carlos Luz
EST Setúbal / IPS
18 - 23 Junho 2012
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
1 / 23
Coloração dos Vértices de um Grafo
Problema
Pretende-se planear o horário de seis seminários de uma hora, s1 , s2 , . . . , s6 .
Várias pessoas manisfestaram interesse em assistir a mais do que um, pelo
que os seminários não podem decorrer simultaneamente. O horário dos
seis seminários tem que obedecer à seguinte tabela de restrições,
s 1 s2 s 3 s 4 s 5 s 6
s1
s2
s3
s4
s5
s6
onde “ ” na linha i e coluna j, signi…ca que si e sj não podem decorrer
simultaneamente. Qual o número mínimo de horas necessárias para
realizar os seminários de modo a satisfazer as restrições?
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
2 / 23
Início da Resolução:
Para resolver este problema podemos considerar um grafo em que os
vértices representam os seminários (isto é, V = fs1 , s2 , . . . , s6 g), e
cada aresta um par de seminários que não podem decorrer
simultaneamente.
s1
s1
s2
s1
s2
s3
s4
s5
s6
Carlos Luz (EST Setúbal / IPS)
s3
s4
s5
s6
s2
s3
s6
s5
Grafos (4/4)
s4
18 - 23 Junho 2012
3 / 23
De…na-se uma função c : V ! f1, 2, 3, 4, 5, 6g com a seguinte
propriedade: se u e v são vértices adjacentes, então c (u ) 6= c (v );
A função c diz-se uma coloração sendo os elementos de
f1, 2, 3, 4, 5, 6g designados por cores.
Nesta linguagem, o problema original pode ser enunciado:
determinar uma coloração dos vértices de G com o menor
número de cores possível.
Por exemplo, uma coloração admissível é:
s1
s2
c ( s1 ) = c ( s3 ) = 1
c ( s2 ) = c ( s4 ) = 2
c ( s5 ) = 3
s6
c ( s6 ) = 4
s3
s5
s4
Será que esta coloração utiliza o menor número de cores?
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
4 / 23
De…nição
Dado um grafo G = (V , E ) de ordem n, uma coloração dos vértices de G
é uma função
c : V ! f1, . . . , ng
tal que, se u e v são vértices adjacentes, então c (u ) 6= c (v ).
De…nição
O número cromático de um grafo G , representado por χ (G ) , é o menor
número inteiro k tal que existe uma coloração dos vértices de G com k
cores.
Exemplo
Sendo Nn o grafo nulo (desconexo) de n vértices e Kn o grafo completo de
n vértices, tem-se
χ (Nn ) = 1 e χ (Kn ) = n.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
5 / 23
Observação
Da de…nição resulta que, para um grafo G de ordem n, χ (G ) n. Este
limite superior para χ (G ) não é útil, pois corresponde à atribuição (trivial)
de cores distintas a cada um dos vértices de G .
Dois resultados mais úteis são:
Proposição
Um grafo G é bipartido se e só se χ (G ) = 2.
G = ÝX 1 W X 2 , EÞ
eÝG Þ = 2
X1
Carlos Luz (EST Setúbal / IPS)
X2
Grafos (4/4)
18 - 23 Junho 2012
6 / 23
Proposição
Suponha-se que Kn é um subgrafo de G . Então χ (G )
s1
s2
ì eÝGÞ ³ 3
s3
s6
s5
Carlos Luz (EST Setúbal / IPS)
n.
s4
Grafos (4/4)
18 - 23 Junho 2012
7 / 23
Exemplo
Voltamos ao problema inicial. A primeira tentativa para planear o horário
dos seminários resultou numa coloração dos vértices do grafo que utiliza 4
cores. Facilmente, no entanto, se obtém uma outra coloração só com 3
cores:
s1
s2
cÝs 1 Þ = 1
s3
s6
cÝs 2 Þ = cÝs 5 Þ = 2
cÝs 3 Þ = cÝs 4 Þ = cÝs 6 Þ = 3
s5
s4
Visto que χ(G ) 3 (pois K3 é subgrafo de G ) e foi possível obter uma
coloração que utiliza 3 cores, conclui-se que χ(G ) = 3. Portanto, de forma
a respeitar as condições impostas, o conjunto dos seis seminários pode ser
realizado em 3 horas.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
8 / 23
Calcular o Número Cromático é Difícil...
Determinar o número cromático em grafos de grandes dimensões é
normalmente um problema muito difícil.
Em contraste com o exemplo acima, nos problemas reais os limites
inferiores e superiores para o número de cores não são fáceis de
calcular e, mesmo sendo o seu cálculo possível, podem não ser muito
úteis.
Dada a di…culdade computacional deste problema, existem dois
caminhos que se podem tomar:
1
Procurar algoritmos práticos (usualmente heurísticos) que determinem
colorações aproximadas, usualmente com um número de cores maior
do que χ (G ).
2
Investigar classes de grafos onde, em virtude da estrutura particular
destes, seja possível determinar χ (G ) e colorações óptimas.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
9 / 23
Algoritmo Guloso para a Coloração dos Vértices
Entrada:
Saída:
1.
2.
Um grafo G de ordem n e uma ordenação
v1 , v2 , . . . , vn dos seus vértices;
O conjunto de cores f1, 2, . . . , ng
Uma coloração c dos vértices de G
Considerar c (v1 ) = 1 e i = 2;
Enquanto i n
2.1. Determinar A(vi ) ! conjunto dos vértices da sequência
v1 , v2 , . . . , vi 1 adjacentes a vi ;
2.2. Determinar K (vi ) ! conjunto das cores dos elementos
de A(vi );
2 .3. Sendo k a primeira cor não pertencente a K (vi ),
considerar c (vi ) = k;
2.4. i = i + 1;
FimEnquanto
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
10 / 23
Aplicação do Algoritmo Guloso
Exemplo
Vamos aplicar o algoritmo guloso ao grafo do problema inicial. O quadro
seguinte resume os passos realizados:
i si
AÝs i Þ
KÝs i Þ
1 s1
?
?
?
1
?
?
?
?
?
2 s2
ás 1 â
á1â
2
1
2
?
?
?
?
3 s3
2
2
1
1
2
1
?
?
?
4 s4
ás 1 â
á1â
2
1
2
1
2
?
?
5 s5
ás 3 , s 4 â
á1, 2â
3
1
2
1
2
3
?
4
1
2
1
2
3
4
6 s 6 ás 1 , s 2 , s 5 â á1, 2, 3â
1ª cor6 KÝs i Þ cÝs 1 Þ cÝs 2 Þ cÝs 3 Þ cÝs 4 Þ cÝs 5 Þ cÝs 6 Þ
Conclui-se então que a coloração obtida utiliza 4 cores. Assim, o algoritmo
não obteve o número cromático de G , que vimos ser igual a 3.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
11 / 23
Limites Superiores para o Número Cromático
Teorema
Seja G um grafo simples e ∆ o maior dos graus dos seus vértices. Então
χ (G ) ∆ + 1 e uma coloração com ∆ + 1 cores pode ser determinada
utilizando o algoritmo guloso.
Demonstração
Seja v1 , v2 , . . . , vn uma ordenação arbitrária dos vértices de G . Por
hipótese, cada vértice vi tem, no máximo, ∆ vizinhos; então o conjunto
K (vi ) calculado no passo 2.2. do algoritmo guloso tem, quanto muito,
cardinalidade ∆. Logo, pelo menos uma das cores 1, 2, . . . , ∆ + 1 não
pertence a K (vi ), e o algoritmo atribui a vi a primeira cor nestas
condições. Deste modo, é possível colorir todos os vértices de G com, no
máximo, ∆ + 1 cores.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
12 / 23
Teorema
Seja G um grafo simples, conexo e não regular. Então, se ∆ é o maior dos
graus dos seus vértices, tem-se χ (G ) ∆ e uma coloração com ∆ cores
pode ser determinada aplicando o algoritmo guloso a uma ordenação
particular dos vértices de G .
s1
s2
s3
s6
Ideia da demonstração aplicada ao grafo
s4
s5
1. Dado que A = 3, seleccionar por exemplo v 6 = s 2 pois dÝs 2 Þ = 2 < 3.
v6 v5 v4
2. Lista dos v. adjacentes a v 6 = s 2 : v 5 = s 1 , v 4 = s 6 (lista actual: s 2 , s 1 , s 6 )
v6 v5 v4 v3
3. Lista dos v. adjacentes a v 5 = s 1 (excepto listados): v 3 = s 4 (lista actual: s 2 , s 1 , s 6 , s 4 )
v6 v5 v4 v3 v2
4. Lista dos v. adjacentes a v 4 = s 6 (excepto listados): v 2 = s 5 (lista actual: s 2 , s 1 , s 6 , s 4 , s 5 )
5. Lista dos v. adjacentes a v 3 = s 4 (excepto listados):
6. Lista dos v. adjacentes a v 2 = s 5 (excepto listados):
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
v6 v5 v4 v3 v2
2 (lista actual: s 2 , s 1 , s 6 , s 4 , s 5 )
v6 v5 v4 v3 v2 v1
v 1 = s 3 (lista final: s 2 , s 1 , s 6 , s 4 , s 5 , s 3 )
18 - 23 Junho 2012
13 / 23
Uma vez obtida a ordenação
s 2 , s1 , s 6 , s 4 , s 5 , s 3 ,
aplica-se o algoritmo guloso a partir da ordenação inversa
s 3 , s5 , s 4 , s 6 , s 1 , s 2 ,
obtendo-se uma coloração que utiliza somente 3 cores:
s1
s2
cÝs 3 Þ = cÝs 4 Þ = cÝs 6 Þ = 1
s3
s6
cÝs 1 Þ = cÝs 5 Þ = 2
cÝs 2 Þ = 3.
s5
Carlos Luz (EST Setúbal / IPS)
s4
Grafos (4/4)
18 - 23 Junho 2012
14 / 23
Teorema (Brooks, 1941)
Seja G um grafo simples conexo e ∆ o maior dos graus dos seus vértices.
Se G não é um ciclo com um número ímpar de vértices nem um grafo
completo, então χ(G ) ∆.
Aplicação:
G
Visto que o G contém K4 , tem-se χ(G ) 4.
Por outro lado, G satisfaz as condições do teorema de Brooks (com
∆ = 4), pelo que χ(G ) 4.
Por consequência, χ(G ) = 4.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
15 / 23
Coloração das Arestas de um Grafo
De…nição
Dado um grafo G = (V , E ) sem lacetes com m = jE j arestas, uma
coloração das arestas de G é uma função
c : E ! f1, . . . , m g
tal que, se quaisquer duas arestas e e f incidem no mesmo vértice,
c (e ) 6 = c (f ).
De…nição
Seja G um multigrafo sem lacetes. O índice cromático de G ,
representado por χ0 (G ), é o menor inteiro k tal que existe uma coloração
das arestas de G com k cores.
Observação
χ0 (G ) ∆ = maxfd (v ) : v 2 V g.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
16 / 23
Exemplo
Apresenta-se três atribuições de cores às arestas de um grafo G
(a) e (b) são colorações
(c) não é coloração pois a cor 2 está atribuída a duas arestas que
incidem no mesmo vértice
(a) apresenta uma coloração das arestas com 4 cores, pelo que
χ0 (G ) 4.
Por outro lado, χ0 (G ) 4 pois o maior grau dos vértices de G é 4.
Por consequência, χ0 (G ) = 4.
(a)
Carlos Luz (EST Setúbal / IPS)
(b)
Grafos (4/4)
(c)
18 - 23 Junho 2012
17 / 23
Exemplo de Aplicação
Problema
Para a realização de exames orais de meia hora cada, um conjunto de
estudantes X1 tem de se apresentar no …m do ano perante um conjunto de
examinadores X2 ; como organizar as provas de modo a concluí-las no
menor tempo possível?
Formulação:
– Consideremos o grafo bipartido G = (X 1 [ X2 , E ), onde existe uma
ligação entre a 2 X1 e b 2 X2 por uma aresta se e só se o estudante a se
deve apresentar perante o examinador b.
– Colorindo as arestas de G de maneira que duas arestas incidentes no
mesmo vértice não tenham a mesma cor, cada meia hora da jornada
poderá corresponder a uma cor.
– O problema colocado consiste então em determinar o menor número de
cores que podem colorir as arestas de G nas condições indicadas.
– Isto é, procura-se χ0 (G ).
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
18 / 23
Resolução (de um caso particular):
Apresenta-se à direita uma coloração das arestas do grafo G da
esquerda com 3 cores, pelo que χ0 (G ) 3.
Por outro lado, χ0 (G )
3, pois o maior grau dos vértices de G é 3.
χ 0 (G )
Por consequência,
= 3, donde, neste caso particular, a jornada
de exames orais pode ser realizada em hora e meia.
X1
Carlos Luz (EST Setúbal / IPS)
X2
X1
Grafos (4/4)
X2
18 - 23 Junho 2012
19 / 23
Limites Inferior e Superior para o Índice Cromático
Teorema (Vizing, 1964)
Se G é um grafo simples e ∆ é o maior dos graus dos seus vértices, tem-se
∆
χ 0 (G )
∆ + 1.
Observação
Conclui-se daqui que χ0 (G ) = ∆ ou χ0 (G ) = ∆ + 1, pelo que o limite
inferior anteriormente referido é muito mais forte do que parecia à primeira
vista.
Contudo, o valor preciso de χ0 (G ) depende da estrutura do grafo, não se
conhecendo em geral um procedimento e…ciente para decidir a qual das
classes pertence um grafo dado arbitrariamente. Além disso, tal como no
caso do número cromático, o conhecimento do valor de χ0 (G ), apesar de
útil, não implica que a construção de uma coloração válida seja fácil.
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
20 / 23
Exemplo
Para os ciclos Cn (n
3), tem-se
χ0 (Cn ) = 2 se n é par
χ0 (Cn ) = 3 se n é ímpar.
Teorema
Para um grafo completo Kn tem-se
χ 0 ( Kn ) =
n
n
1 se n é par
se n é ímpar
Demonstração
Se n ímpar, o número máximo de arestas que podem ter a mesma cor é
1
1), pois de contrário duas destas arestas incidiriam no mesmo
2 (n
vértice. Então, o número total de arestas é menor ou igual a n 2 1 χ0 (Kn ) e,
n (n 1 )
dado que Kn tem 2
Vizing, χ0 (Kn ) = n.
Carlos Luz (EST Setúbal / IPS)
arestas, tem-se n
Grafos (4/4)
χ0 (Kn ). Pelo teorema de
18 - 23 Junho 2012
21 / 23
Demonstração
[Demonstração (cont.)] Pode obter-se explicitamente uma coloração
das arestas de Kn com n cores representando gra…camente este
grafo como um polígono regular de n vértices. Notando que as arestas
interiores deste polígono, se existirem, são paralelas às arestas opostas
exteriores, podemos construir uma coloração da seguinte forma: primeiro,
as n arestas exteriores são coloridas sucessivamente com cores distintas e a
cada uma das interiores é atribuída a cor da aresta exterior que lhe é
paralela (a …gura ilustra este procedimento para o grafo K5 ).
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
22 / 23
Demonstração
[Demonstração (cont.)] Se n é par, considere-se um dos vértices de Kn ,
digamos v ; eliminando este vértice e todas as arestas que lhe são
incidentes, obtém-se o grafo Kn 1 ; utilizando o resultado anterior, pode
gerar-se uma coloração das arestas de Kn 1 com n 1 cores; voltando a
juntar v e as respectivas arestas, é possível atribuir a cada uma destas a
cor pertencente a f1, . . . , n 1g que não ocorre nas arestas incidentes no
vértice correspondente de Kn 1 ; obtém-se então uma coloração de Kn com
n 1 cores (a …gura ilustra este procedimento para o grafo K6 ).
v
Carlos Luz (EST Setúbal / IPS)
Grafos (4/4)
18 - 23 Junho 2012
23 / 23