Coloração
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Número cromático (χ(G))
• Um grafo que requere k cores diferentes
para a sua coloração própria e nenhuma a
menos possui número cromático χ(G) = k
b
3-cromático
a
c
e
f
d
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Um exemplo de aplicação
• Problema dos exames: alocação de um
grupo de alunos aos exames de
recuperação que eles devem prestar em
um colégio
» Restrição: Duas disciplinas só podem ter
exames realizados simultaneamente se
não envolverem alunos em comum
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Um exemplo de aplicação
Alunos
Disciplinas
1
Mat.
x
Port.
x
2
3
4
5
8
9
10
11
Hist.
x
Física
x
x
x
14
15
x
x
x
x
x
x
x
x
x
x
x
Teoria dos Grafos
(INF 5037/INF2781)
x
16
x
x
x
x
x
13
x
x
x
12
x
x
Geog.
Biologia
7
x
Ingl.
Química
6
x
x
x
CC/EC/PPGI/UFES
Um exemplo de aplicação
M
P
B
I
Q
G
F
H
São necessários apenas dois horários
para realização dos exames: um para
os exames de Matemática, Geografia,
Biologia e História e outro, para os
exames de Português, Inglês, Física e
Química.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Algumas considerações...
•
•
•
•
•
Coloração de vértices: considerado em
grafos simples e conexos
Grafo nulo: 1-cromático
Grafo com uma ou mais arestas: pelo
menos 2-cromático
Grafo com clique de tamanho k: pelo
menos k-cromático
Grafo cíclico: 2-cromático ou 3-cromático
CC/EC/PPGI/UFES
Teorema
Toda árvore com dois ou mais vértices
é 2-cromática
Obs: toda árvore é 2-cromática mas nem todo grafo 2cromático é uma árvore
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema
Um grafo com pelo menos uma aresta é
2-cromático
sss
não possui ciclos com comprimento
ímpar
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Corolário
Um grafo G é bipartido
sss
G é 2-cromático
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema
Seja Δ o grau máximo dos
vértices de G. Então
χ(G)  1 + Δ
Exercício!
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Coloração de arestas
Exemplo de aplicação:
Em um laboratório, uma lista de
tarefas deve ser cumprida o mais
rápido possível. Cada tarefa deve
ser realizada por uma dupla de
f
integrantes do laboratório e
necessita de 1 hora para ser
executada. Qual é o menor
Índice cromático:
número de horas necessárias
Menor número de cores para
para que todas
as tarefas
sejam
colorir
propriamente
cumpridas?as arestas de um grafo
a
b
c
e
d
CC/EC/PPGI/UFES
Partição Cromática
• Um grafo G k-cromático é p-partido sss k  p.
• Em um grafo p-partido, vértices de uma
mesma partição não são adjacentes.
• Um conjunto de vértices de um grafo é dito
independente se não possui vértices
adjacentes.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conjunto Independente de
vértices
c
a
g
e
b
d
f
Exemplos:
{a, c, d, g},
{e}, {a,d}
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conjunto Independente de
vértices
• Incompatibilidade de horários entre
professores que devem aplicar prova final:
deseja-se obter o maior número possível de
turmas que realizarão prova final de várias
disciplinas em um mesmo horário. Turmas
com alunos em comum que farão prova final
de disciplinas diferentes não podem ser
alocadas no mesmo horário.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conjunto independente
maximal de vértices
Um conjunto independente
maximal é um conjunto
independente no qual não
se pode adicionar mais
nenhum vértice sem destruir
a propriedade de independência.
c
Exemplos:
{a,c,d,g},
{b,f}
a
e
b
d
Teoria dos Grafos
(INF 5037/INF2781)
g
f
CC/EC/PPGI/UFES
Conjunto Independente de
vértices maximal
• Existem vários conjuntos independentes
maximais em um grafo que podem ter
diferentes tamanhos.
• Qual é o de maior tamanho?
• (G) = número de independência de G
(cardinalidade do conjunto independente
de vértices de maior tamanho de G)
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
χ(G) X (G)
•
Seja G um grafo com n vértices e χ(G) =
k
•
Número de vértices coloridos com a
mesma cor  (G)
(G) ≥ n/ χ(G)
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Como achar um conjunto
independente maximal?
• Comece com um vértice qualquer.
• Selecione os próximos vértices sempre
testando se o conjunto ao qual eles estão
sendo inseridos continua independente
• Atenção: encontra-se um conjunto
maximal e não o maior de todos!
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
χ(G) X (G)
• Encontrar (G): consiste em encontrar
todos os conjuntos independentes
maximais e obter o maior;
• Encontrar χ(G): número mínimo de
conjuntos independentes maximais cuja
união resulta em V
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Partição cromática
• Dado um grafo simples e conexo G, os
vértices de G são particionados no menor
número possível de conjuntos
independentes de vértices disjuntos.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matchings
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplo
• Sejam a1, a2, a3 e a4 candidatos a
preencher 6 vagas p1, p2, p3, p4, p5 e p6
de uma empresa. A qualificação de cada
candidato o possibilita a se candidatar
para um certo subconjunto de vagas,
conforme a figura a seguir:
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplo
É possível empregar
todos os candidatos em
posições nas quais eles
são qualificados?
a1
p1
p2
a2
a3
p3
p4
a4
p5
Qual é o número máximo
de posições que podem
ser preenchidas pelo grupo
de candidatos?
p6
Problema de Matching
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matching
• Um matching em um grafo é um
subconjunto de arestas não adjacentes.
Uma única aresta já é considerada um
matching.
• Um matching maximal é um matching no
qual nenhuma aresta a mais pode ser
adicionada sem ferir a propriedade de
matching
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplos
a
b
a
b
a
b
d
c
d
c
d
c
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplo de aplicação
Em um laboratório, cada
tarefa de uma lista de
tarefas especificadas,
deve ser realizada por
uma dupla de integrantes
do laboratório e necessita
de 1 hora para ser executada.
Qual é o maior número de
tarefas que podem ser
executadas em um
mesmo horário?
a
b
f
c
e
d
CC/EC/PPGI/UFES
Número de matching
• Um grafo pode ter muitos matchings
maximais;
• n° de matching: o número de arestas do
maior deles.
• qual é o número de matching do grafo do
slide anterior?
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matching Perfeito
• Um matching perfeito é um matching no
qual todo vértice do grafo é um extremo de
algum elemento do matching
• Nem todo grafo contém um matching
a
b
perfeito:
e
d
Teoria dos Grafos
(INF 5037/INF2781)
c
CC/EC/PPGI/UFES
Observação
Todo matching perfeito é maximal
mas
nem todo matching maximal é perfeito
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matching completo
• Definição válida para grafos bipartidos
• Em um grafo bipartido com subconjuntos
de vértices V1 e V2, um matching completo
de V1 em V2 é um matching no qual existe
uma aresta incidente a cada aresta de V1.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Observação
um matching completo é o maior matching
maximal mas um matching maximal pode
não ser completo
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplo
p1
a1
p2
a2
p3
a3
p4
a4
p5
p6
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Condições para existência de
um matching completo
• |V1|  |V2|;
• todo subconjunto de r vértices em V1 deve
ser adjacente a pelo menos r vértices em
V2, para r = 1, 2, ..., |V1|.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Problema de representantes
distintos
Cinco senadores (s1, s2, s3, s4 e s5) são
membros de três comitês (c1, c2 e c3)
Um membro diferente
de cada comitê deve
participar de uma
comissão geral. É
possível realizar esse
matching?
c1
c2
c3
s1
s2
s3
s4
s5
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema
Em um grafo bipartido, se existe
um inteiro positivo m tal que
d(v1) ≥ m ≥ d(v2) ,
com v1 de V1 e v2 de V2,
então
existe um matching completo de V1 para V2
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Prova
• Considere um subconjunto de r vértices em V1
• Cada um dos r vértices tem pelo menos m vértices de V2 incidentes
a ele. Assim esses r vértices tem pelo menos m.r arestas incidentes
• Cada uma das m.r arestas é incidente a algum vértice de V2
• Por sup. d(vi) ≤ m, vi de V2
• Então as m.r arestas são incidentes a pelo menos m.r/m = r vértices
• Assim, qualquer subconjunto de r vértices de V1 é adjacente a r ou
mais vértices de V2.
• Logo, G possui um matching completo
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Cobertura de vértices
• Um conjunto de vértices K de V é uma
cobertura de G se toda aresta de G possui
pelo menos um extremo em K
• Cobertura mínima: aquela que possui o
menor número possível de vértices
• Aplicações:
– Vigilância: menor número possível de câmeras de
segurança em lugares públicos.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Exemplo
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Observações
• Se K é uma cobertura de vértices e M um
matching de G então K contém pelo menos
um extremo de cada aresta de M
• Para quaisquer K e M em G tem-se
|M|  |K|
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Cobertura de arestas
• Em um grafo G, um conjunto g de arestas
cobre G se todo vértice em G é incidente a
pelo menos uma aresta em g. O conjunto g
é chamado cobertura de G.
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Observações
• G consiste na sua própria cobertura
• Uma árvore geradora é uma cobertura
• Um ciclo hamiltoniano, se ele existe, é uma
cobertura
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Cobertura minimal
• Conjunto de arestas que cobre G de forma
que a retirada de uma única aresta destrói
essa propriedade
Teoria dos Grafos
(INF 5037/INF2781)
a
b
d
c
CC/EC/PPGI/UFES
Exemplo
Garantir a alocação
de todas as disciplinas
da oferta de um curso
aos professores do
departamento
CC/EC/PPGI/UFES
Observações
• G possui uma cobertura se não possui vértices isolados
• Uma cobertura de um grafo com n vértices possui pelo
menos n/2 arestas
• Toda aresta pendente de um grafo faz parte de toda
cobertura de G
• Toda cobertura contém uma cobertura minimal
• Nenhuma cobertura minimal contém um ciclo. Assim,
uma cobertura minimal contém no máximo n-1 arestas
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Nº de cobertura de G
• Número de arestas da cobertura minimal
de menor tamanho de G
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema
Uma cobertura g de um grafo é minimal
se e somente se
g não contém caminhos
de comprimento 3 ou mais
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES