Baixe o app para aproveitar ainda mais
Prévia do material em texto
Teoria dos Grafos Valeriano A. de Oliveira So orro Rangel Silvio A. de Araujo Departamento de Matemáti a Apli ada antunes�ibil e.unesp.br, so orro�ibil e.unesp.br, saraujo�ibil e.unesp.br AULA 14 Coloração de Vérti es Preparado a partir do texto: Rangel, So orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013. Coloração de Vérti es Coloração de Vérti es Partição Cromáti a Introdução Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 3 Considere ada um dos grafos abaixo: a) Quantas ores são ne essárias para olorir os vérti es de um grafo de maneira que dois vérti es adja entes não re ebam a mesma or? b) Qual é o número mínimo de ores ne essárias? ) Considerando as ores usadas no item (a) agrupe os vérti es que re eberam a mesma or. d) Pense em algum problema práti o que vo e pudesse resolver usando a partição dos vérti es obtidas a ima. Apli ações Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 4 Coloração de mapas - Considere os mapas abaixo: Qual é o menor número de ores ne essário para pintar os mapas de forma que duas regiões adja entes não re ebam a mesma or? Duas regiões são adja entes se elas possuem uma linha de fronteira em omum. Note que no mapa 1 as regiões A e D possuem apenas um ponto em omum e portanto não são adja entes. Vamos representar os mapas através de grafos. Vérti es - regiões do mapa. Arestas - existe uma aresta se duas regiões são adja entes. Apli ações Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 5 Problema das 4 ores - Quatro ores são su� ientes para olorir as regiões de qualquer mapa sem que duas regiões adja entes re ebam a mesma or. Este resultado foi provado omputa ionalmemte em 1976. Foi um problema proposto em 1852. (Wilson, 1990). Apli ações Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 6 Problema da Coleta de lixo - Uma prefeitura determinou um onjunto de rotas para a oleta de lixo da idade. O problema é que as rotas pré-de�nidas possuem pontos de oleta em omum. Considere, por exemplo o onjunto de rotas a seguir: O problema onsiste em determinar omo dividir o onjunto de 6 rotas em três dias da semana de tal forma que nenhum ponto de oleta é visitado mais que uma vez no mesmo dia. Apli ações Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 7 Representando o problema através de grafos, temos: - Vérti es: rotas - Aresta - existe uma aresta entre duas rotas que possuam pontos de oleta em omum. Para esta onjunto de rotas temos o seguinte grafo: A partição satisfaz as ondições do problema: {A,D}, {B,E}, {C,F}. Existem outras? É possível fazer a oleta em dois dias da semana? O que muda na solução do problema se as rotas A e F se tornarem uma rota úni a? Para formalizar as idéias expostas a ima onsidere: De�nições Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 8 De�nição 1. Coloração - Seja G(V,A) um grafo e C= {c1, c2, c3, ..., cm} um onjunto de ores. Uma oloração de G é uma atribuição de ores aos vérti es de G de tal forma que dois vérti es adja entes re ebam ores diferentes. O número romáti o de um grafo G é o menor número de ores ne essário para obter uma oloração de G. Se o número romáti o é χ(G) dizemos que o grafo é χ(G)- romáti o. Como determinar o número romáti o de um grafo? Não é uma tarefa muito fá il. Na verdade este é um problema de difí il resolução no aso de grafos quaisquer, no entanto, para alguns tipos de grafos é possível resolver o problema fa ilmente. De�nições Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 9 Exemplo: Considere os seguintes asos: 1. Grafo nulo; 2. Grafo Completo; 3. Grafo ir uito: n ≥ 3, se n é par G é 2- romáti o e se n é ímpar G é 3- romáti o; 4. Uma árvore é 2- romáti o - De�na um vérti e vj do grafo e atribua a or 1. A partir deste vérti e, todos os vérti es que estiverem a uma distân ia par atribua a or 2 e os que estiverem a uma distân ia ímpar atribua a or 1. Como existe um e apenas um aminho entre ada par de vérti es não teremos dois vérti es adja entes om a mesma or. De�nições e Teoremas Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 10 Teorema 2. Um grafo é 2- romáti o se e somente se for bipartido. De�nição 3. Um Clique é um subgrafo ompleto de G. Teorema 4. O número romáti o de um grafo é maior ou igual do que o tamanho do maior lique de G (o tamanho de um lique é dado pelo seu número de vérti es). Ou seja, o número de vérti es do maior lique do grafo, Kmax , forne e um limite inferior para o número romáti o de G. Exemplo: O grafo a seguir ontém um lique de tamanho 3. Qual é o seu número romáti o? De�nições e Teoremas Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 11 E um limite superior, omo pode ser determinado? Teorema 5. Se ∆ é grau máximo dos vérti es de G então o número romáti o de G é menor ou igual a ∆+1. Isto é: Kmax ≤ χ(G) ≤ ∆+1 Observação: Observe que para mostrar que um grafo é χ(G)- romáti o, é ne essário mostrar que usar (χ(G)− 1) ores força dois vérti es adja entes a re eberem a mesma or. Exer í io Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 12 En ontre o numero romáti o dos grafos a seguir. a) b) K7 ) K3,5 Partição Cromáti a Coloração de Vérti es Partição Cromáti a De�nição Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 14 Seja o grafo G1: De�nição Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 15 Uma oloração deste grafo, pode ser: Esta oloração parti iona o onjunto de vérti es do grafo em: a) {v1}, {v2}, {v3, v4}, {v5} Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 16 Mas vimos ainda que o número romáti o deste grafo é 3 e uma oloração pode ser: E a partição asso iada é: b) {v1, v5}, {v2}, {v3, v4} Observe que estes onjuntos de vérti es tem em omum o fato que os vérti es de um mesmo onjunto não são adja entes. De�nição Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 17 De�nição 6. Conjunto Independente - Um sub onjunto de vérti es de um grafo é hamado de onjunto independente de vérti e se não existem dois vérti es adja entes neste onjunto. Um Conjunto independente de vérti es é maximal se nenhum vérti e pude ser adi ionado ao onjunto. Exemplo: Em relação a G1: onjunto independente: {v1, v5}, {v1} onjunto independente de vérti es maximal: {v1, v5}. Apli ação Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 18 Suponha que o grafo G2: des reve o seguinte problema. Cada um dos sete vérti es é uma palavra ódigo a ser usada em algum tipo de omuni ação. Algumas dessas palavras são pare idas om outras (por exemplo, em relação ao som) e podem ser onfundidas. Tais pares de palavras são ligadas por arestas. En ontre o maior onjunto possível de palavras ódigo que podem ser usadas para se obter uma omuni ação segura. {a, c, d, f} é uma solução: onjunto independente de vérti es maximal.Apli ação Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 19 Este grafo possue 5 onjuntos independentes de vérti es maximais: {a, c, d, f}, {a, c, d, g}, {b, g}, {b, f}, {a, e} qual é o número romáti o do grafo? É o menor número de onjuntos independentes uja união ontém todos os vérti es do grafo. Por exemplo: {a, c, d, f}, {b, g}, {a, e}. Assim o problema de determinar uma oloração mínima de G pode ser formulado em termos de parti ionar V em um número mínimo de onjuntos independentes. De�nição Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 20 De�nição 7. Partição Cromáti a Dado um grafo onexo, simples, a partição do onjunto de vérti es no menor número possível de onjuntos independentes de vérti es é hamada de partição romáti a. Exemplo: {(a, c, d, f), (b, g), (e)} {(a, c, d, g), (b, f), (e)} {(c, d, f), (b, g), (a, e)} {(c, d, g), (b, f), (a, e)} São 4 exemplos de partições romáti as do grafo G2. Algoritmo Guloso de Coloração Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 21 Como en ontrar uma partição romáti a de um grafo? Vamos ver a seguir um algoritmo guloso (ou míope) baseado na idéia de onstrução de onjuntos independentes. 1. Dado um grafo G(V,A). 2. Iní io 3. Ordene o onjunto de vérti es em ordem não res ente de graus: v1, v2, ..., vn. 4. Faça S1 = S2 = ... = Sn = ∅ 5. In lua v1 em S1. 6. Para j = 2, ..., n faça: en ontre o onjunto Sr, tal que o vérti e vj não seja adja ente a nenhum vérti e já in luído a ele e r = min{i, i = 1, ..., n}. In lua o vérti e vj em Sr. 7. Fim Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 22 Note que ao �m do algoritmo teremos obtido no máximo n onjuntos independentes de vérti es. Vamos usar esta idéia para obter uma partição romáti a do grafo G3. Ordenação dos vérti es: {2, 3, 5, 6, 7, 8, 1, 4, 8, 10} Partição: S1 = {2, 5, 9}; S2 = {3, 7, 1}; S3 = {6, 10}; S4 = {8, 4} Outra partição: S1 = {2, 4, 9}; S2 = {1, 3, 7}; S2 = {6, 10}; S4 = {5, 8}. Apli ação Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 23 O senado possui várias omissões que se reúnem durante uma hora por semana. Deseja-se fazer um alendário de reuniões que minimiza o número total de horas de reuniões e tal que duas omissões que possuam membros em omum não se reúnam no mesmo horário. Supondo que existem 10 omissões mostre que este problema pode ser resolvido omo um problema de oloração. Se as omissões não possuíssem membros em omum elas poderiam se reunir simultaneamente. Como resolver então? A informação have é o fato de que um mesmo membro perten em a mais de uma omissão. Para representar o problema através de um grafo, pre isamos de�nir os vérti es e as arestas. Sejam as omissões os vérti es. E as arestas vão ligar omissões que possuem membros em omum. Vamos supor que o grafo abaixo representa uma situação parti ular Apli ação Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 24 Para de�nir um alendário de reuniões basta en ontrar o número romáti o deste grafo e uma oloração asso iada. Exer í ios Coloração de Vérti es Partição Cromáti a Teoria dos Grafos (Antunes Rangel&Araujo) � 25 1) Modele o problema de en ontrar o número romáti o de G utilizando variáveis 0/1. 2) En ontre um grafo tal que o número romáti o seja 2 mas que a oloração obtida através do algoritmo guloso des rito a ima é maior ou igual a 3. 3) Qual é o número romáti o do mapa do Brasil? (ver em: A. Rabelo, M. Moreira e S. Rangel, O número romáti o do Brasil, Anais do CNMAC 2010, SBMAC, disponível em http://www.sbma .org.br/eventos/ nma /xxxiiicnmac/pdf/691.pdf (última visita 08/01/2015). Coloração de Vértices Introdução Aplicações Aplicações Aplicações Aplicações Definições Definições Definições e Teoremas Definições e Teoremas Exercício Partição Cromática Definição Definição Definição Aplicação Aplicação Definição Algoritmo Guloso de Coloração Aplicação Aplicação Exercícios
Compartilhar