En teoría de grafos , un gráfico mixto G = ( V , E , A ) es un gráfico que consta de un conjunto de vértices V , un conjunto de aristas (no dirigidas) E y un conjunto de aristas (o arcos) dirigidas A. [1]
Considere los vértices adyacentes . Una arista dirigida , llamada arco , es una arista con una orientación y se puede denotar como o (nótese 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 puede denotarse como o . [2]
A los efectos de nuestro ejemplo, no consideraremos bucles ni aristas múltiples de gráficos mixtos.
Un recorrido en un gráfico mixto es una secuencia de vértices y aristas/arcos tales que para cada índice , es un borde del gráfico o un arco del gráfico. Este recorrido es un camino si no repite ninguna arista, arco o vértice, excepto posiblemente el primer y el último vértice. Un camino está cerrado si su primer y último vértice son iguales, y un camino cerrado es un ciclo . Un gráfico mixto es acíclico si no contiene un ciclo.
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 una arista. Los colores pueden representarse mediante 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]
Por ejemplo, considere la figura de la derecha. Nuestros k colores disponibles para colorear nuestro gráfico mixto son {1, 2, 3}. Dado que u y v están conectados por un borde, 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 la cola ( v ) con un color más pequeño (o un número entero de nuestro conjunto) que la cabeza ( w ) de nuestro arco.
Una coloración k adecuada (fuerte) de un gráfico 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]
Se puede aplicar una condición más débil a nuestros arcos y podemos considerar una coloración k débil propia de un gráfico mixto como 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.
Un color puede existir o no para un gráfico mixto. Para que un gráfico mixto tenga una coloración k , el gráfico no puede contener ciclos dirigidos. [2] Si existe tal coloración k , entonces nos referimos al k más pequeño necesario para colorear adecuadamente nuestro gráfico como el número cromático , denotado por χ ( G ) . [2] El número de k -coloraciones propias es una función polinómica de k llamada polinomio cromático de nuestro gráfico G (por analogía con el polinomio cromático de gráficos no dirigidos) y puede denotarse por χ G ( k ) . [1]
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 (es decir, eliminar) un borde o arco y posiblemente unir los vértices restantes incidentes a ese borde o arco para formar un vértice. [4] Después de eliminar una arista e de un gráfico mixto G = ( V , E , A ) obtenemos el gráfico 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 gráfico mixto, obtenemos ( V , E , A – a ) donde denotamos la eliminación de a por G – a . Además, denotamos la contracción de e y a por G / e y G / a , respectivamente. De las proposiciones dadas en Beck et al. [4] obtenemos las siguientes ecuaciones para calcular el polinomio cromático de un gráfico mixto: [5]
Se pueden utilizar gráficos mixtos para modelar problemas de programación de talleres en los que se debe realizar una colección de tareas, sujetas a ciertas restricciones de tiempo. En este tipo de problema, se pueden utilizar aristas no dirigidas 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 llama gráfico disyuntivo . El problema de coloración de gráficos mixtos se puede utilizar para encontrar un cronograma de duración mínima para realizar todas las tareas. [2]
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 aristas dirigidas) también se denomina gráfico en 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 en cadena se llama cadena. Un gráfico en 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 en cadena agregando aristas no dirigidas entre pares de vértices que tienen aristas salientes a la misma cadena, y luego olvidando las orientaciones de las aristas dirigidas. . [6]
![{\displaystyle [u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c790b8b85a510362484e22edb7d03d54656ee4e1)
