Conteo mixto

Un grafo mixto G = (V, E, A) es un objeto matemático que consta de un conjunto de vértices (o nodos) V, un conjunto de aristas (no dirigidas) E y un conjunto de aristas dirigidas (o arcos) A. [ 1]

Definiciones y notación

Más información: Gráfico (matemáticas)

Considere los vértices vecinos . Un borde orientado se llama arco , un borde con una orientación, que se denota por o (vale la pena señalar que esta es la cola y esta es la cabeza del arco). [2] Una arista no dirigida , o simplemente una arista , se denomina arista sin orientación y se denota por o . [2] ${\ estilo de visualización u, v \ en V}$ ${\displaystyle {\displaystyle {\overrightarrow {uv))))$ ${\ estilo de visualización {\ estilo de visualización (u, v)))$ $tu$ $v$ ${\ estilo de visualización {\ estilo de visualización uv))$ ${\ estilo de visualización [u, v]}$

Más información: Múltiples aristas

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

Como nuestro ejemplo de aplicación, no consideraremos ciclos o múltiples bordes de gráficos mixtos.

Una ruta en un gráfico mixto es una secuenciade vértices y aristas/arcos de modo que, para todos los índices,arista del gráfico o el elementoes un arco del gráfico. Este camino es un camino si no tiene aristas, arcos o vértices repetidos, excepto posiblemente el primer y el último vértice. Un camino es cerrado si su primer y último vértice son iguales, y un camino cerrado es un ciclo si no tiene vértices repetidos además del primero y el último. Un grafo mixto es acíclico si no contiene un ciclo. ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\puntos,c_{k},v_{k))$ ${\ estilo de visualización {\ estilo de visualización i))$ ${\displaystyle c_{i}=v_{i}v_{i+1))$ ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1))))$

Dibujo para colorear

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

Se puede pensar que colorear un gráfico mixto es etiquetar o asignar diferentes colores (donde es un número entero positivo) a los vértices del gráfico mixto. [3] A los vértices conectados por una arista se les debe asignar diferentes colores. Los colores se pueden representar con números del 1 al , y para un arco dirigido, la cola del arco debe indicarse con un número menor que la cabeza del arco. [3] $k$ $k$ $k$

Ejemplo

Por ejemplo, considere la figura de la derecha. Disponibles k-colores para colorear nuestro gráfico mixto: . Dado que y están conectados por un borde, deben tener diferentes colores o números ( y están etiquetados como 1 y 2 respectivamente). También tenemos un arco de a . Ya que estamos tratando con un arco donde la orientación dicta el orden de los números, necesitamos etiquetar la cola ( ) con un color más pequeño (o un número entero de nuestro conjunto) que la cabeza ( ) de nuestro arco. ${\ estilo de visualización {\ estilo de visualización \ {1,2,3\))}$ ${\ estilo de visualización {\ estilo de visualización u))$ ${\ estilo de visualización {\ estilo de visualización v))$ ${\ estilo de visualización {\ estilo de visualización u))$ ${\ estilo de visualización {\ estilo de visualización v))$ ${\ estilo de visualización {\ estilo de visualización v))$ ${\ estilo de visualización {\ estilo de visualización w))$ ${\ estilo de visualización {\ estilo de visualización v))$ ${\ estilo de visualización {\ estilo de visualización w))$

Coloración fuerte y débil

El ( fuerte) eigen - coloración de un gráfico mixto es una función $k$

${\displaystyle c:V\flecha derecha [k]}$ , donde tal que , si , y , si . [una] ${\ estilo de visualización [k]: = {1,2, \ puntos, k))$ ${\ estilo de visualización {\ estilo de visualización c (u) \ neq c (v)))$ ${\ estilo de visualización {\ estilo de visualización uv \ en E))$ ${\ estilo de visualización {\ estilo de visualización c (u) <c (v)))$ ${\displaystyle {\overrightarrow {uv}}\en A}$

Podemos relajar la condición en nuestros arcos. Entonces podemos considerar la débil coloración propia de la gráfica mixta como una función

${\displaystyle c:V\flecha derecha [k]}$ , donde tal que , si , y , si . [1] Volviendo a nuestro ejemplo, esto significa que podemos etiquetar la cabeza y la cola con el entero positivo 2. ${\ estilo de visualización [k]: = {1,2, \ puntos, k))$ ${\ estilo de visualización {\ estilo de visualización c (u) \ neq c (v)))$ ${\ estilo de visualización {\ estilo de visualización uv \ en E))$ ${\ estilo de visualización {\ estilo de visualización c (u) \ leq c (v)))$ ${\displaystyle {\overrightarrow {uv}}\en A}$ $(v,w)$

Existencia

Para un gráfico mixto, un color puede o no existir. Para que un gráfico mixto sea coloreable, no debe contener ningún ciclo dirigido. [2] Si tal coloración existe, entonces denotamos el más pequeño requerido para colorear correctamente nuestro gráfico como el número cromático , denotado por . [2] Podemos contar el número de colores propios como una función polinomial de . Esto se llama el polinomio cromático de nuestro gráfico (por analogía con el polinomio cromático de los gráficos no dirigidos) y se puede denotar como . [una] $k$ $k$ $k$ ${\ estilo de visualización {\ estilo de visualización \ chi (G)))$ $k$ $k$ ${\ estilo de visualización G}$ ${\ estilo de visualización {\ estilo de visualización \ chi _ {G} (k)))$

Cálculo de polinomios cromáticos débiles

La fórmula de deleción-contracción se puede utilizar para calcular polinomios cromáticos débiles de gráficos mixtos. Este método consiste en eliminar un borde o arco y reducir (o unir) los vértices restantes en ese borde (o arco) para formar un solo vértice. [1] Después de eliminar un borde de un gráfico mixto, obtenemos un gráfico mixto . [1] Podemos denotar esta eliminación de bordes como . De manera similar, al eliminar un arco de un gráfico mixto, obtenemos , donde podemos denotar la eliminación como . [1] Además, podemos denotar la abreviatura y as y , respectivamente. [1] De las afirmaciones anteriores, [1] obtenemos las siguientes ecuaciones para calcular el polinomio cromático de un grafo mixto: $mi$ ${\ Displaystyle G = (V, E, A)}$ ${\ estilo de visualización (V, Ee, A)}$ $mi$ ${\ estilo de visualización Ge}$ $a$ ${\ estilo de visualización (V, E, Aa)}$ $a$ ${\ estilo de visualización Ga}$ $mi$ $a$ ${\ estilo de visualización G / e}$ ${\ estilo de visualización G/a}$

${\displaystyle {\displaystyle \mathrm {X}_{G}(k)=\chi_{Ge}(k)-\chi_{G/e}(k)))$ [una]
${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k) }$ [una]

Aplicaciones

Problema de planificación

Los gráficos mixtos se pueden utilizar para modelar tareas de programación de trabajo en las que se deben recopilar tareas, sujetas a ciertas limitaciones de tiempo. En este tipo de tareas, los bordes no dirigidos se pueden usar para modelar la restricción de que dos tareas son incompatibles (no se pueden ejecutar al mismo tiempo). Los bordes dirigidos se pueden usar para modelar restricciones de prioridad, en las que una tarea debe completarse antes que otra. Una gráfica definida de esta manera a partir de un problema de programación se llama gráfica disyuntiva. El problema de coloración de gráficos mixtos se puede usar para encontrar el programa de duración mínima para completar 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 (sin ciclos de aristas dirigidas) también se denomina gráfico de cadena. Los bordes dirigidos de estos gráficos se utilizan para indicar una relación causal entre dos eventos, en la que el resultado del primer evento afecta la probabilidad del segundo evento. Los bordes no dirigidos indican una correlación no causal entre dos eventos. Un componente conexo de un subgrafo no dirigido de un grafo de cadena se llama cadena. Un gráfico de cadena se puede convertir en un gráfico no dirigido mediante la construcción de su gráfico moral , un gráfico no dirigido formado a partir de un gráfico de cadena mediante la adición de aristas no dirigidas entre pares de vértices que tienen aristas salientes en la misma cadena, sin tener en cuenta la orientación de las aristas dirigidas. [cuatro]

Notas

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. Sobre Polinomios Cromáticos Débiles de Grafos Mixtos // Grafos y Combinatoria. — 2015-01-01. — vol. 31 , edición. 1 . — págs. 91–98 . — ISSN 1435-5914 . -doi : 10.1007/ s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. Colorear algunas clases de grafos mixtos (inglés) // Matemática Aplicada Discreta. - 2007-01-01. — vol. 155 , edición. 1 . — P. 1–6 . — ISSN 0166-218X . -doi : 10.1016/ j.dam.2006.05.004 .
↑ 1 2 Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Coloreados de grafos mixtos (inglés) // Métodos Matemáticos de Investigación de Operaciones. - 1997-02-01. — vol. 45 , edición. 1 . — P. 145–160 . — ISSN 1432-5217 . -doi : 10.1007/ BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Redes Probabilísticas y Sistemas Expertos: Métodos Computacionales Exactos para Redes Bayesianas . — Springer Science & Business Media, 2007-07-16. — 340 s. - ISBN 978-0-387-71823-1 .

Enlaces

Weisstein, Eric W. "Gráfica mixta" MathWorld