Gráfico mixto

Un gráfico mixto G = ( V , E , A ) es un objeto matemático que consiste en un conjunto de vértices (o nodos ) V , un conjunto de (no dirigida) bordes E , y un conjunto de aristas dirigidas (o arcos) A . ^[1]

Definiciones y notación

Más información: Graph (matemáticas discretas)

Ejemplo de gráfico mixto

Considere los vértices adyacentes . Un borde dirigido , llamado arco , es un borde con una orientación y se puede denotar como o (tenga en cuenta que es la cola y es la cabeza del arco). ^[2] Además, un borde no dirigido , o borde , es un borde sin orientación y se puede denotar como o . ^[2]${\displaystyle u,v\in V}$${\displaystyle {\overrightarrow {uv}}}$${\displaystyle (u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle uv}$${\displaystyle [u,v]}$

Más información: múltiples bordes

Más información: Bucle (teoría de grafos)

Para el propósito de nuestro ejemplo de aplicación, no consideraremos bucles o bordes múltiples de gráficos mixtos.

Un paseo en un gráfico mixto es una secuencia de vértices y aristas / arcos tal que para todos los índices , es un borde del gráfico o es un arco del gráfico. Este paseo es un camino si no repite ningún borde, arco o vértice, excepto posiblemente el primer y último vértice. Una ruta está cerrada si su primer y último vértice son iguales, y una ruta cerrada es un ciclo si no repite los vértices, excepto el primero y el último. Un gráfico mixto es acíclico si no contiene un ciclo.${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$${\displaystyle i}$${\displaystyle c_{i}=v_{i}v_{i+1}}$${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$

Colorear

Más información: Coloración de gráficos

Ejemplo de gráfico mixto

La coloración de gráficos mixtos se puede considerar como un etiquetado o una asignación de k colores diferentes (donde k es un número entero positivo) a los vértices de un gráfico mixto. ^[3] Se deben asignar diferentes colores a los vértices que están conectados por un borde. Los colores pueden estar representados por los números del 1 al k , y para un arco dirigido, la cola del arco debe estar coloreada con un número menor que la cabeza del arco. ^[3]

Ejemplo

Por ejemplo, considere la figura de la derecha. Nuestros colores k disponibles para colorear nuestro gráfico mixto son . Dado que y están conectados por un borde, deben recibir diferentes colores o etiquetas ( y están etiquetados como 1 y 2, respectivamente). También tenemos un arco de a . Dado que la orientación asigna un orden, debemos etiquetar la cola ( ) con un color más pequeño (o entero de nuestro conjunto) que la cabeza ( ) de nuestro arco.${\displaystyle \{1,2,3\}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$

Coloración fuerte y débil

Una coloración k (fuerte) adecuada de un gráfico mixto es una función

${\displaystyle c:V\rightarrow [k]}$donde tal que si y si . ^[1]${\displaystyle [k]:={1,2,\dots ,k}}$${\displaystyle c(u)\neq c(v)}$${\displaystyle uv\in E}$${\displaystyle c(u)<c(v)}$${\displaystyle {\overrightarrow {uv}}\in A}$

Se puede aplicar una condición más débil en nuestros arcos y podemos considerar que un color k adecuado débil de un gráfico mixto es una función

${\displaystyle c:V\rightarrow [k]}$donde tal que si y si . ^[1] Volviendo a nuestro ejemplo, esto significa que podemos etiquetar tanto la cabeza como la cola de con el entero positivo 2.${\displaystyle [k]:={1,2,\dots ,k}}$${\displaystyle c(u)\neq c(v)}$${\displaystyle uv\in E}$${\displaystyle c(u)\leq c(v)}$${\displaystyle {\overrightarrow {uv}}\in A}$${\displaystyle (v,w)}$

Existencia

Puede que exista o no un color para un gráfico mixto. Para que un gráfico mixto tenga un color k, el gráfico no puede contener ciclos dirigidos. ^[2] Si existe tal coloración k, entonces nos referimos a la k más pequeña necesaria para colorear correctamente nuestra gráfica como el número cromático , denotado . ^[2] Podemos contar el número de k-coloraciones propias como una función polinomial de k. Esto se llama polinomio cromático de nuestro gráfico G (por analogía con el polinomio cromático de gráficos no dirigidos) y se puede denotar como . ^[1]${\displaystyle \chi (G)}$${\displaystyle \chi _{G}(k)}$

Calcular polinomios cromáticos débiles

El método de eliminación-contracción se puede utilizar para calcular polinomios cromáticos débiles de gráficos mixtos. Este método implica eliminar (o quitar) una arista o arco y contraer (o unir) los vértices restantes incidentes a esa arista (o arco) para formar un vértice. ^[4] Después de eliminar un borde, de un gráfico mixto obtenemos el gráfico mixto . ^[4] Podemos denotar esta supresión del borde , como . De manera similar, al eliminar un arco, de un gráfico mixto, obtenemos donde podemos denotar la eliminación de como . ^[4] Además, podemos denotar la contracción de y como y , respectivamente.${\displaystyle e}$${\displaystyle G=(V,E,A)}$${\displaystyle (V,E-e,A)}$${\displaystyle e}$${\displaystyle G-e}$${\displaystyle a}$${\displaystyle (V,E,A-a)}$${\displaystyle a}$${\displaystyle G-a}$${\displaystyle e}$${\displaystyle a}$${\displaystyle G/e}$${\displaystyle G/a}$^[4] De las proposiciones dadas en, ^[4] obtenemos las siguientes ecuaciones para calcular el polinomio cromático de un gráfico mixto:

1. ${\displaystyle \chi _{G}(k)=\chi _{G-e}(k)-\chi _{G/e}(k)}$, ^[5]
2. ${\displaystyle \chi _{G}(k)=\chi _{G-a}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)}$. ^[5]

Aplicaciones

Problema de programación

Artículo principal: Gráfico disyuntivo

Se pueden usar gráficos mixtos para modelar los problemas de programación del taller de trabajo en los que se realizará una colección de tareas, sujeto a ciertas restricciones de tiempo. En este tipo de problema, los bordes no dirigidos pueden usarse para modelar una restricción de que dos tareas son incompatibles (no se pueden realizar simultáneamente). Los bordes dirigidos se pueden utilizar para modelar restricciones de precedencia, en las que una tarea debe realizarse antes que otra. Un gráfico definido de esta manera a partir de un problema de programación se denomina gráfico disyuntivo . El problema de coloración de gráficos mixtos se puede utilizar para encontrar un horario de duración mínima para realizar todas las tareas. ^[2]

Inferencia bayesiana

Los gráficos mixtos también se utilizan como modelos gráficos para la inferencia bayesiana . En este contexto, un gráfico mixto acíclico (uno sin ciclos de bordes dirigidos) también se denomina gráfico de cadena . Los bordes dirigidos de estos gráficos se utilizan para indicar una conexión causal entre dos eventos, en la que el resultado del primer evento influye en la probabilidad del segundo evento. Los bordes no dirigidos, en cambio, indican una correlación no causal entre dos eventos. Un componente conectado del subgrafo no dirigido de un gráfico de cadena se llama cadena. Un gráfico de cadena se puede transformar en un gráfico no dirigido construyendo su gráfico moral, un gráfico no dirigido formado a partir del gráfico de cadena agregando bordes no dirigidos entre pares de vértices que tienen bordes salientes a la misma cadena, y luego olvidando las orientaciones de los bordes dirigidos. ^[6]

Notas

1. Beck y col. (2013 , pág.1)
2. Ries (2007 , p. 1)
3. Hansen, Kuplinsky y de Werra (1997 , p. 1)
4. Beck y col. (2013 , pág.4)
5. Beck y col. (2013 , pág.5)
6. Cowell y col. (1999) .

Referencias

• Beck, M .; Blado, D .; Crawford, J .; Jean-Louis, T .; Young, M. (2013), "Sobre polinomios cromáticos débiles de gráficos mixtos", Graphs and Combinatorics , arXiv : 1210.4634 , doi : 10.1007 / s00373-013-1381-1.
• Cowell, Robert G .; Dawid, A. Philip ; Lauritzen, Steffen L .; Spiegelhalter, David J. (1999), Redes probabilísticas y sistemas expertos: métodos computacionales exactos para redes bayesianas , Springer-Verlag Nueva York, p. 27, doi : 10.1007 / 0-387-22630-3 , ISBN 0-387-98767-3
• Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique (1997), "Colores de gráficos mixtos", Métodos matemáticos de investigación de operaciones , 45 (1): 145–160, doi : 10.1007 / BF01194253 , MR  1435900.
• Ries, B. (2007), "Colorear algunas clases de gráficos mixtos", Matemáticas aplicadas discretas , 155 (1): 1–6, doi : 10.1016 / j.dam.2006.05.004 , MR  2281351.

Enlaces externos

• Weisstein, Eric W. "Gráfico mixto" . MathWorld .