Gráfico de ganancia

Un gráfico de ganancia es un gráfico cuyos bordes están etiquetados de forma "invertible" u "orientable" por elementos de un grupo G. Esto significa que, si un borde e en una dirección tiene la etiqueta g (un elemento de grupo), entonces en la otra dirección tiene la etiqueta g ⁻¹ . Por lo tanto , la función de etiqueta φ tiene la propiedad de que se define de manera diferente, pero no independientemente, en las dos orientaciones o direcciones diferentes de un borde e . El grupo G se llama grupo de ganancia , φ es la función de ganancia y el valor φ ( e ) es la ganancia de e (en alguna dirección indicada). Un gráfico de ganancia es una generalización de un gráfico con signo , donde el grupo de ganancia G tiene solo dos elementos. Véase Zaslavsky (1989, 1991).

No se debe confundir una ganancia con un peso sobre un borde, cuyo valor es independiente de la orientación del borde.

Aplicaciones

Algunas razones para interesarse en los gráficos de ganancia son sus conexiones con la teoría del flujo de redes en optimización combinatoria , con la geometría y con la física .

Las matemáticas de una red con ganancias , o red generalizada , están conectadas con el marco matroide del gráfico de ganancias.
Supongamos que tenemos algunos hiperplanos en R ⁿ dados por ecuaciones de la forma x _j = g x _i . La geometría de los hiperplanos se puede tratar utilizando el siguiente gráfico de ganancia: El conjunto de vértices es {1,2,..., n }. Hay una arista ij con ganancia g (en la dirección de i a j ) para cada hiperplano con ecuación x _j = gx _i . Estos hiperplanos se tratan a través del marco matroide del gráfico de ganancia (Zaslavsky 2003).
O supongamos que tenemos hiperplanos dados por ecuaciones de la forma x _j = x _i + g . La geometría de estos hiperplanos se puede tratar utilizando el gráfico de ganancia con el mismo conjunto de vértices y una arista ij con ganancia g (en la dirección de i a j ) para cada hiperplano con ecuación x _j = x _i + g . Estos hiperplanos se estudian mediante la matroide de elevación del gráfico de ganancia (Zaslavsky 2003).
Supongamos que el grupo de ganancia tiene una acción sobre un conjunto Q. Asignar un elemento s _i de Q a cada vértice da un estado del gráfico de ganancia. Una arista se satisface si, para cada arista ij con ganancia g (en la dirección de i a j ), se satisface la ecuación s _j = s _i g ; de lo contrario se frustra . Un estado se satisface si se satisfacen todas las aristas. En física esto corresponde a un estado fundamental (un estado de menor energía), si tal estado existe. Un problema importante en física, especialmente en la teoría del espín del vidrio , es determinar un estado con el menor número de aristas frustradas.

Conceptos relacionados

Los gráficos de ganancia utilizados en la teoría de grafos topológicos como medio para construir incrustaciones de gráficos en superficies se conocen como " gráficos de voltaje " (Gross 1974; Gross y Tucker 1977). El término "gráfico de ganancia" es más habitual en otros contextos, por ejemplo, en la teoría de grafos sesgados y la teoría matroide . También se ha utilizado el término gráfico etiquetado por grupos , pero es ambiguo ya que las "etiquetas de grupo" pueden ser (y han sido) tratadas como ponderaciones.

Dado que gran parte de la teoría de los gráficos de ganancia es un caso especial de la de los gráficos sesgados (y gran parte de la teoría de los gráficos sesgados es una generalización de la de los gráficos de ganancia), el lector debe consultar el artículo sobre gráficos sesgados para obtener más información y ejemplos.

Referencias

Jonathan L. Gross (1974), Gráficos de voltaje. Matemáticas discretas , vol. 9, págs. 239–246.
JL Gross y TW Tucker (1977), Generación de todas las coberturas de gráficos mediante asignaciones de voltaje de permutación. Matemáticas discretas , vol. 18, págs. 273–283.
Thomas Zaslavsky (1989), Gráficos sesgados. I. Sesgo, equilibrio y ganancias. Revista de teoría combinatoria, serie B , vol. 47, 32–52.
Thomas Zaslavsky (1991), Gráficos sesgados. II. Las tres matroides. Revista de teoría combinatoria, serie B , vol. 51, 46–72.
Tomás Zaslavsky (1999). Una bibliografía matemática de gráficos con signo y ganancia y áreas afines. Revista Electrónica de Combinatoria, Encuestas dinámicas en Combinatoria, #DS8.
Thomas Zaslavsky (2003), Gráficos sesgados IV: Realizaciones geométricas. Revista de teoría combinatoria, serie B , vol. 89, núm. 2, págs. 231–297.