Coloración fraccional de un gráfico
Muchos problemas modernos que cubren campos tan diversos como la clasificación de páginas web, el diseño de circuitos electrónicos, el análisis de redes sociales y la gestión de distribución se pueden formular y resolver utilizando las herramientas de la teoría de gráficos. Además de un amplio conjunto de funciones para construir, computar y operar en gráficos, Wolfram Language incluye una serie de colecciones de gráficos.
El dominio de entidad "Graph" intenta catalogar gráficos interesantes no dirigidos, junto con tantas de sus propiedades como se conozcan o se puedan calcular. Las entidades "Graph" proporciona una colección creciente de más de 6000 gráficos simples y 500 propiedades precalculadas.
La estructura de la entidad "Graph" también incluye inclusiones "agradables" precalculadas para la mayoría de los gráficos.
Tenga en cuenta que los objetos devueltos por la propiedad "Graph" no son simplemente gráficos, sino objetos reales de Wolfram Language Graph.
Cada entidad gráfica contiene una lista detallada de clases matemáticas a las que pertenece.
También hay dos funciones que conectan el mundo de las entidades gráficas con los objetos gráficos de nivel superior. ToEntity Convierte un gráfico simple desconocido en una entidad (si existe).
Lo contrario es proporcionado por FromEntity (que es equivalente a usar la propiedad "Graph").
Para tener una idea de la amplitud de los datos disponibles en el dominio de la entidad "Graph", considere el llamado número cromático fraccional de un gráfico. El número cromático fraccional generaliza el número cromático habitual, en el caso de colorantes en los que se permiten múltiples colores en cada vértice, cada uno con una fracción de peso especificado, de modo que los vértices adyacentes no contengan dos colores iguales.
Por ejemplo, mientras que el número cromático del gráfico dodecaédrico es 3 (se necesita un mínimo de tres colores para colorear los vértices de modo que no haya dos vértices adyacentes que compartan un color), el uso de coloración fraccional da un número cromático fraccional de 5/2 (una instanciación de los cuales, que se discutirán más adelante, consisten en cinco colores asignados a cada nodo con pesos de 1/2).
El dominio de entidad de gráfico contiene los números cromáticos habituales y fraccionales para muchos gráficos, así como coloraciones concretas que alcanzan estos valores mínimos. Por ejemplo, el gráfico dodecaédrico tiene el número cromático 3.
Un color que alcanza este valor se puede recuperar de la siguiente manera.
Es bastante sencillo utilizar estos datos de inclusión y coloración junto con la funcionalidad gráfica integrada para crear una visualización.
Como se puede verificar visualmente (o programáticamente), no hay dos vértices adyacentes que compartan el mismo color en el diagrama anterior.
El caso de la coloración fraccional es un poco más complicado, pero esencialmente relaja la restricción de que cada vértice tiene un color único al permitir que los vértices contengan porciones fraccionarias de diferentes colores. El número cromático fraccional se define sumando las porciones fraccionarias sobre todos los vértices. Esto a menudo permite colorear con "menos" (aunque no necesariamente un número entero) de colores. Por ejemplo, el número cromático fraccional del gráfico dodecaédrico es 
, que es menor que su número cromático de 3.
Para obtener el color fraccionario, use la propiedad "MinimumWeightFractionalColoring" para obtener una lista de vértices y pesos para diferentes colores.
Por ejemplo, la salida anterior indica que es posible una coloración fraccional mínima usando cinco colores, el primero de los cuales se aplica a los vértices 3, 5, 9, 12, 13, 15, 16 y 20 con peso 1/2, y así sucesivamente. Como cada color se aplica con el mismo peso de 1/2, el número cromático fraccional general es 
.
Dado que las fracciones de cada color son iguales a 1/2 en este caso, es fácil crear una visualización al encontrar primero los dos colores que contribuyen a cada vértice.
Por ejemplo, la lista anterior indica que el primer vértice usa los colores 4 y 5, el segundo también usa 4 y 5, el tercero usa los colores 1 y 5 y así sucesivamente. Ahora convierta los índices numéricos de color a colores reales.
El paso final en la visualización es definir una función de forma de vértice que consista en dos medios discos apropiadamente coloreados.
Con todas las piezas en su lugar, ahora puede mostrar una coloración fraccional mínima para el gráfico dodecaédrico.
Como se esperaba, los vértices adyacentes no comparten colores comunes en esta coloración fraccional.
Los números cromáticos fraccionales no están distribuidos uniformemente, pero tienden a agruparse alrededor de ciertos valores. Hacer un histograma utilizando los datos calculados previamente para todos los gráficos en el dominio de la entidad "Graph" muestra el agrupamiento alrededor de enteros, aunque también se pueden ver algunos otros picos prominentes.
Puede usar BubbleChart para trazar los números de gráficos que tienen cada número cromático fraccional (con numerador y denominador en los ejes x e y, respectivamente) y explorar la distribución con más detalle.
