Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como construir um grafo com o número cromático arbitrariamente grande e o número de clique fixo?

0 votos
29 visitas
perguntada Set 30 em Matemática por pedro zarur (1 ponto)  

Exercício 4.10 do capítulo 4 do livro "Combinatorial Algorithms: Generation, Enumeration and Search" de Donald L. Kreher e Douglas R. Stinson:

Sendo \(w(G)\) o número de clique e \(X(G)\) o número cromático de um grafo \(G\) e sabendo que, para qualquer grafo, é verdade que \(w(G) \leq X(G)\):

a) Mostre que a desigualdade \(w(G) \leq X(G)\) pode ser estrita. Ou seja, encontre um grafo \(G\) tal que \(w(G) < X(G)\).

b) Mostre que, para todo número inteiro \(d \geq 0\) existe um grafo \(G\) com \(X(G) - w(G) \geq d\).

Compartilhe

1 Resposta

0 votos
respondida Set 30 por pedro zarur (1 ponto)  
editado Out 1 por pedro zarur

O número cromático de um grafo \(G(V, E)\), denotado por \(X(G)\), é o número mínimo de cores necessárias para colorir os vértices desse grafo de forma que nenhum par de vértices adjacentes tenha a mesma cor.

Um clique de um grafo \(G(V, E)\) é um subconjunto de \(V\) tal que quaisquer dois vértices desse subconjunto sejam adjacentes. O número de clique de um grafo, denotado por \(w(G)\), é o número de vértices do maior clique do grafo.

a) Um exemplo de grafo que apresenta essa desigualdade estrita, no caso \(X(G) = 3\) e \(w(G) = 2\), é representado pelo seguinte código:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (1, 5), (2, 3), (3, 4), (4, 5)])
colorsnodes = ['white', 'red', 'white', 'blue', 'red']

nx.draw(G, node_color=colorsnodes, with_labels=True)
plt.show()   

A imagem será apresentada aqui.

b) Para demonstrar essa proposição temos que provar que é possível construir um grafo com um número cromático arbitrariamente grande mantendo o número de clique fixo. Para isso, usaremos um método conhecido como construção de Mycielski. Vamos ilustrar com o grafo construído no primeiro item. Para cada vértice \(x\) adicionaremos um novo vértice \(y\) adjacente a todos os vértices adjacentes a \(x\). Complementando o código já apresentado temos:

G.add_nodes_from([6, 7, 8, 9, 10])
G.add_edges_from([(6, 1), (6, 3), (7, 2), (7, 4), (8, 3),
                  (8, 5), (9, 4), (9, 1), (10, 5), (10, 2)])
colorsnewnodes = ['red', 'white', 'blue', 'red', 'white']

nx.draw(G, node_color=colorsnodes+colorsnewnodes, with_labels=True)
plt.show()

A imagem será apresentada aqui.

Note que colorimos o novo grafo de maneira ótima e o número cromático manteve-se inalterado. Note também que, como o antigo grafo não apresentava triângulos, o novo grafo também não apresenta. Ou seja, o número de clique não mudou, continuando igual a 2.

Agora, adicionaremos mais um vértice adjacente apenas aos cinco vértices que acabamos de adicionar:

G.add_node(11)
G.add_edges_from([(11, 6), (11, 7), (11, 8), (11, 9), (11, 10)])
finalcoloring = colorsnodes + colorsnewnodes + ['green']

nx.draw(G, node_color=finalcoloring, with_labels=True)
plt.show()

A imagem será apresentada aqui.

Assim, construímos um grafo de número cromático \(4\) a partir de um grafo de número cromático \(3\). A propriedade de ser livre de triângulos foi preservada até o fim da construção, ou seja, \(w(G) = 2\) manteve-se constante.

Podemos generalizar esse procedimento para qualquer grafo:
Sejam \(G\) um grafo com \(n\) vértices \(\{x_{1}, ..., x_{n}\}\), \(Y = \{y_{1}, y_{2}, ..., y_{n}\}\) o conjunto de vértices que adicionamos no primeiro passo da construção, \(z\) o último vértice a ser adicionado e \(M(G)\) o grafo resultante. Definimos também a função \(c : \{x_{1}, ..., x_{n}, y_{1}, ..., y_{n}\} \rightarrow \{1, 2, ..., k\}\) que atribui a cada vértice de \(M(G) - \{z\}\) uma das \(k\) cores em questão. Assim temos que

i) Ao aplicarmos a construção de Mycielski em um grafo \(G\) com \(X(G) = k\), temos que \(X(M(G)) = k + 1\). Isso ocorre pois \(M(G) - \{z\}\) necessariamente tem número cromático igual a \(k\). Percebemos isso ao considerarmos que \(X(M(G) - \{z\}) = k - 1\). Nesse caso, seria possível encontrar uma coloração ótima com \(X(G) = k - 1\) ao aplicarmos uma nova função \(c'\)

\(c'(x_{i}) = c(y_{i})\), se \(c(x_{i}) = k \)
\(c'(x_{i}) = c(x_{i})\), caso contrário

o que seria uma contradição. Logo, como \(X(M(G) - \{z\}) = k\), então \(X(M(G)) = k + 1\) pois \(z\) é adjacente a todos os vértices de \(Y\).

ii) Se \(G\) não apresenta triângulos, então \(M(G)\) também não apresentará. Isso é consequência do fato que todo triângulo formado em \(M(G)\) teria o formato \(x_{i}x_{j}y_{k}\) onde \(x_{i}x_{j}x_{k}\) é um triângulo em \(G\). É fácil perceber isso com as seguintes imagens

A imagem será apresentada aqui.

A imagem será apresentada aqui.

Note que a formação de novos triângulos seguiu o padrão descrito.

Assim, ao aplicarmos a construção de Mycielski sucessivamente em um grafo livre de triângulos, podemos construir grafos com o número cromático tão grande quanto quisermos e o número de clique constante. Logo, para todo inteiro \(d \geq 0\) existe um grafo \(G\) tal que \(X(G) - w(G) \geq d\).

...