Gráfico mixto

En teoría de grafos , un grafo mixto G = ( V , E , A ) es un grafo que consiste en un conjunto de vértices V , un conjunto de aristas (no dirigidas) E y un conjunto de aristas dirigidas (o arcos) A . ^[1]

Consideremos 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, una arista no dirigida , o arista , es una arista sin orientación y se puede denotar como o . ^[2]${\displaystyle u,v\en V}$${\displaystyle {\overrightarrow {uv}}}$${\estilo de visualización (u,v)}$${\estilo de visualización u}$${\estilo de visualización v}$${\estilo de visualización uv}$${\estilo de visualización [u,v]}$

Para los propósitos de nuestro ejemplo, no consideraremos bucles o aristas múltiples de gráficos mixtos.

Un paseo en un grafo mixto es una secuencia de vértices y aristas/arcos de manera que para cada índice , o bien es una arista del grafo o bien es un arco del grafo. Este paseo es un camino si no repite ninguna arista, arco o vértice, excepto posiblemente el primer y el último vértice. Un paseo es cerrado si su primer y último vértice son iguales, y un camino cerrado es un ciclo . Un grafo 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}}$${\estilo de visualización i}$${\displaystyle c_{i}=v_{i}v_{i+1}}$${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$

La coloración de gráficos mixtos puede considerarse como un etiquetado o una asignación de k colores diferentes (donde k es un entero positivo) a los vértices de un gráfico mixto. ^[3] Se deben asignar colores diferentes a los vértices que están conectados por una arista. Los colores pueden representarse con números del 1 al k y, para un arco dirigido, la cola del arco debe colorearse 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}. Como u y v están conectados por una arista, deben recibir diferentes colores o etiquetas ( u y v están etiquetadas como 1 y 2, respectivamente). También tenemos un arco de v a w . Como la orientación asigna un orden, debemos etiquetar la cola ( v ) con un color más pequeño (o un entero de nuestro conjunto) que la cabeza ( w ) de nuestro arco.

Una coloración k (fuerte) propia 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]${\displaystyle {\overrightarrow {uv}}\en A}$

Se puede aplicar una condición más débil en nuestros arcos y podemos considerar una k -coloración propia débil 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.${\displaystyle {\overrightarrow {uv}}\en A}$

Puede existir o no una coloración para un grafo mixto. Para que un grafo mixto tenga una k -coloración, el grafo no puede contener ningún ciclo dirigido. ^[2] Si existe dicha 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 puede denotarse por χ _{G ( k )} . ^[1]

El método de deleció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 . Además, 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 gráficos mixtos se pueden utilizar 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). Las aristas dirigidas 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 cronograma 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 (uno sin ciclos de aristas dirigidas) también se denomina grafo de cadena . Las aristas dirigidas de estos grafos 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. Las aristas no dirigidas, en cambio, indican una correlación no causal entre dos eventos. Un componente conectado del subgrafo no dirigido de un grafo de cadena se denomina cadena. Un grafo de cadena se puede transformar en un grafo no dirigido construyendo 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 a la misma cadena, y luego olvidando las orientaciones de las aristas dirigidas. ^[6]

• Beck, M.; Blado, D.; Crawford, J.; Jean-Louis, T.; Young, M. (2013), "Sobre polinomios cromáticos débiles de grafos mixtos", Graphs and Combinatorics , 31 : 91–98, arXiv : 1210.4634 , doi :10.1007/s00373-013-1381-1.
• Cowell, Robert G.; David, A. Felipe ; 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ág. 27, doi :10.1007/0-387-22630-3 (inactivo 2024-10-25), ISBN 0-387-98767-3{{citation}}: CS1 maint: DOI inactivo a partir de octubre de 2024 ( enlace )
• Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique (1997), "Coloración mixta de gráficos", Métodos matemáticos de investigación de operaciones , 45 (1): 145–160, doi :10.1007/BF01194253, MR  1435900.
• Ries, B. (2007), "Coloración de algunas clases de gráficos mixtos", Discrete Applied Mathematics , 155 (1): 1–6, doi : 10.1016/j.dam.2006.05.004 , MR  2281351.

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