Wolfram Language™

Coloração fracionária de um grafo

Muitos problemas modernos que abrangem campos tão diversos como classificação de páginas da Web, design de circuitos eletrônicos, análise de redes sociais e gerenciamento de distribuição podem ser formulados e resolvidos usando as ferramentas da teoria dos grafos. Além de um grande número de funções para criar, calcular e trabalhar com grafos, a Wolfram Language contém várias coleções de grafos.

O domínio da entidade "Graph" tenta catalogar grafos não direcionados interessantes, junto com suas propriedades conhecidas ou que podem ser calculadas. Entidades "Graph" fornece uma coleção crescente de mais de 6.000 grafos simples e 500 propriedades pré-calculadas.

O framework da entidade "Graph" também inclui incorporações pré-calculadas para a maioria dos grafos.

Observe que os objetos retornados pela propriedade "Graph" não são apenas gráficos, mas objetos de Graph reais da Wolfram Language.

Cada entidade de grafo contém uma lista detalhada de classes matemáticas às quais pertence.

Existem também duas funções que conectam o mundo das entidades de grafos aos objetos de grafos de nível superior. ToEntity converte um grafo simples desconhecido em uma entidade (se houver).

O inverso é fornecido por FromEntity (que é equivalente ao uso da propriedade "Graph").

Para ter uma idéia da amplitude de dados disponíveis no domínio da entidade"Graph", considere o chamado número cromático fracionário de um grafo. O número cromático fracionário generaliza o número cromático usual nos casos em que várias cores são permitidas em cada vértice, cada uma com uma fração de peso especificada, de modo que os vértices adjacentes não contenham duas cores iguais.

Por exemplo, enquanto o número cromático do grafo dodecaédrico é 3 (são necessárias no mínimo três cores para colorir os vértices, de modo que não haja dois vértices adjacentes com a mesma cor), o uso de cores fracionadas fornece um número cromático fracionário de 5/2 (uma representação que, a ser discutido mais adiante, consiste em cinco cores atribuídas a cada nó com pesos de 1/2).

O domínio da entidade do grafo contém os números cromáticos usuais e fracionários de muitos grafos, assim como colorações concretas que atingem esses valores mínimos. Por exemplo, o grafo dodecaédrico tem o número cromático 3.

Uma coloração atingindo esse valor pode ser extraída da seguinte maneira.

É bastante simples usar esses dados de incorporação e coloração junto com a funcionalidade de grafo integrada para criar uma visualização.

Como pode ser verificado visualmente (ou programaticamente), dois vértices adjacentes compartilham a mesma cor no diagrama acima.

O caso da coloração fracionária é um pouco mais complicado, mas essencialmente flexibiliza a restrição de que cada vértice tenha uma cor única, permitindo que os vértices contenham partes fracionárias de cores diferentes. O número cromático fracionário é então definido pela soma das partes fracionárias em todos os vértices. Isso geralmente permite uma coloração usando um número "menor" (embora não necessariamente um número inteiro) de cores. Por exemplo, o número cromático fracionário do gráfico dodecaédrico é , que é menor que o número cromático 3.

Para obter a coloração fracionária, use a propriedade "MinimumWeightFractionalColoring" para obter uma lista de vértices e pesos para cores diferentes.

Por exemplo, o resultado anterior indica que é possível uma coloração fracionária mínima usando cinco cores, a primeira aplicada aos vértices 3, 5, 9, 12, 13, 15, 16 e 20 com peso 1/2, e assim por diante. Como cada cor é aplicada com o mesmo peso de 1/2, o número cromático fracionado geral é .

Como as frações de cada cor são iguais a 1/2 nesse caso, é fácil criar uma visualização encontrando primeiro as duas cores que contribuem para cada vértice.

Por exemplo, o vértice anterior usa as cores 4 e 5, o segundo também usa 4 e 5, o terceiro usa as cores 1 e 5 e assim por diante. Agora converta índices de cores numéricos em cores reais.

A etapa final da visualização é definir uma função de formato de vértice que consiste em dois meios-discos de cores apropriadas.

Com todas as peças no lugar, agora você pode exibir uma coloração fracionária mínima para o grafo dodecaédrico.

Como esperado, os vértices adjacentes não compartilham cores comuns nessa coloração fracionária.

Os números cromáticos fracionários não são distribuídos uniformemente, mas tendem a se agrupar em torno de certos valores. Criar um histograma usando os dados pré-calculados para todos os grafos no domínio da entidade "Graph" mostra o agrupamento em torno de números inteiros, embora alguns outros picos importantes também sejam visíveis.

Você pode usar BubbleChart para fazer um gráfico dos números de grafos com cada número cromático fracionário (com numerador e denominador nos eixos e respectivamente) e explorar a distribuição com mais detalhes.