Un gráfico de ganancia es un gráfico cuyos bordes están etiquetados como "invertiblemente", o "orientable", por elementos de un grupo G . Esto significa que, si una arista e en una dirección tiene la etiqueta g (un elemento de grupo), entonces en la otra dirección tiene la etiqueta g −1 . La función de etiqueta φ , por tanto, tiene la propiedad de que se define de manera diferente, pero no de forma independiente, en las dos orientaciones diferentes, o direcciones, 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).
Una ganancia no debe confundirse con un peso en un borde, cuyo valor es independiente de la orientación del borde.
Aplicaciones
Algunas razones para estar interesado en los gráficos de ganancia son sus conexiones con la teoría del flujo de red en la optimización combinatoria , la geometría y la física .
- Las matemáticas de una red con ganancias , o red generalizada , están conectadas con la matriz de tramas del gráfico de ganancia.
- Suponga que tenemos algunos hiperplanos en R n 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 de la matriz de cuadros del gráfico de ganancia (Zaslavsky 2003).
- O suponga 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 un borde ij con ganancia g (en la dirección de i a j ) para cada hiperplano con la ecuación x j = x i + g . Estos hiperplanos se estudian a través de 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. Se satisface una arista 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 de los vidrios giratorios , es determinar un estado con la menor cantidad 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 común en otros contextos, por ejemplo, teoría de grafos sesgados y teoría de matroides . También se ha utilizado el término gráfico con etiquetas de grupo , pero es ambiguo ya que las "etiquetas de grupo" pueden ser, y han sido, tratadas como pesos.
Dado que gran parte de la teoría de los gráficos de ganancia es un caso especial del 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 por 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.
- Thomas Zaslavsky (1999). Una bibliografía matemática de gráficas firmadas y ganadas 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, no. 2, págs. 231-297.