Gráfico mixto

Por ejemplo, consideremos la figura de la derecha. Nuestros k colores disponibles para colorear nuestro grafo mixto son {1, 2, 3}. Dado que u y v están conectados por una arista, deben recibir colores o etiquetas diferentes ( u y v están etiquetados como 1 y 2, respectivamente). También tenemos un arco de v a w . Dado que la orientación asigna un orden, debemos etiquetar el extremo ( v ) con un color (o un número entero de nuestro conjunto) menor que el extremo ( w ) de nuestro arco.

Una k -coloración (fuerte) propia de un grafo mixto es una función c  : V → [ k ] donde [ k ]  := {1, 2, …, k } tal que c ( u ) ≠ c ( v ) si uv ∈ E y c ( u ) < c ( v ) si . ^{[ 1 ]}${\displaystyle {\overrightarrow {uv}}\in A}$

Se puede aplicar una condición más débil a nuestros arcos y podemos considerar que una k -coloración propia débil de un grafo mixto es una función c  : V → [ k ] donde [ k ]  := {1, 2, …, k } tal que c ( u ) ≠ c ( v ) si uv ∈ E y c ( u ) ≤ c ( v ) si . ^{[ 1 ]} Volviendo a nuestro ejemplo, esto significa que podemos etiquetar tanto la cabeza como la cola de ( v , w ) con el entero positivo 2.${\displaystyle {\overrightarrow {uv}}\in A}$

Puede existir o no una coloración para un grafo mixto. Para que un grafo mixto tenga una k -coloración, no puede contener ciclos dirigidos. ^{[ 2 ]} Si existe tal k -coloración, entonces nos referimos al k más pequeño necesario para colorear correctamente nuestro grafo como el número cromático , denotado por χ ( G ) . ^{[ 2 ]} El número de k -coloraciones adecuadas es una función polinómica de k llamada polinomio cromático de nuestro grafo G (por analogía con el polinomio cromático de grafos no dirigidos) y se puede denotar por χ _{G ( k )} . ^{[ 1 ]}

El método de eliminación-contracción se puede utilizar para calcular polinomios cromáticos débiles de grafos mixtos. Este método implica eliminar (es decir, quitar) una arista o arco y posiblemente unir los vértices restantes incidentes a esa arista o arco para formar un vértice. ^{[ 4 ]} Después de eliminar una arista e de un grafo mixto G = ( V , E , A ) obtenemos el grafo mixto ( V , E – e , A ) . Denotamos esta eliminación de la arista e por G – e . De manera similar, al eliminar un arco a de un grafo mixto, obtenemos ( V , E , A – a ) donde denotamos la eliminación de a por G – a . También denotamos la contracción de e y a por G / e y G / a , respectivamente. A partir de las proposiciones dadas en Beck et al. ^{[ 4 ]} obtenemos las siguientes ecuaciones para calcular el polinomio cromático de un grafo mixto: ^{[ 5 ]}

1. ${\displaystyle \chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)}$,
2. ${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)}$.

Los grafos mixtos pueden utilizarse para modelar problemas de programación de talleres en los que se debe realizar un conjunto de tareas, sujetas a ciertas restricciones de tiempo. En este tipo de problema, las aristas no dirigidas pueden utilizarse para modelar la restricción de que dos tareas son incompatibles (no pueden realizarse simultáneamente). Las aristas dirigidas pueden utilizarse para modelar restricciones de precedencia, en las que una tarea debe realizarse antes que otra. Un grafo definido de esta manera a partir de un problema de programación se denomina grafo disyuntivo . El problema de coloración de grafos mixtos puede utilizarse para encontrar una programación de longitud mínima para realizar todas las tareas. ^{[ 2 ]}

Los grafos mixtos también se utilizan como modelos gráficos para la inferencia bayesiana . En este contexto, un grafo mixto acíclico (sin ciclos de aristas dirigidas) se denomina grafo de cadena . Las aristas dirigidas de estos grafos se utilizan para indicar una conexión causal entre dos eventos, donde el resultado del primer evento influye en la probabilidad del segundo. Las aristas no dirigidas, en cambio, indican una correlación no causal entre dos eventos. Un componente conexo del subgrafo no dirigido de un grafo de cadena se denomina cadena. Un grafo de cadena puede transformarse en un grafo no dirigido mediante la construcción de su grafo moral , un grafo no dirigido formado a partir del grafo de cadena añadiendo aristas no dirigidas entre pares de vértices que tienen aristas salientes hacia la misma cadena, y luego ignorando las orientaciones de las aristas dirigidas. ^{[ 6 ]}

Un sistema de calles o carreteras puede representarse mediante la interconexión de aristas y nodos mixtos, donde las aristas dirigidas representan calles de un solo sentido y las aristas no dirigidas representan calles de doble sentido.