Gráfico con aristas etiquetadas por grupos
Un grafo de ganancia es un grafo 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 del grupo), entonces en la otra dirección tiene la etiqueta g −1 . Por lo tanto, la función de etiqueta φ tiene la propiedad de que se define de forma diferente, pero no independiente, en las dos orientaciones o direcciones diferentes de un borde e . El grupo G se denomina grupo de ganancia , φ es la función de ganancia y el valor φ ( e ) es la ganancia de e (en alguna dirección indicada). Un grafo de ganancia es una generalización de un grafo 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 interesarse en los gráficos de ganancia son sus conexiones con la teoría del flujo de red en la 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 matroide de trama del gráfico de ganancias.
- Supongamos 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 del matroide de marco del gráfico de ganancia (Zaslavsky 2003).
- O bien, 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 a través del matroide de sustentació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 grafo 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 satisface cada arista. En física, esto corresponde a un estado fundamental (un estado de energía más baja), si tal estado existe. Un problema importante en física, especialmente en la teoría de los vidrios de espín , 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 un medio para construir incrustaciones de grafos 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, la teoría de grafos sesgados y la teoría de matroides . El término grafo etiquetado por grupo también se ha utilizado, pero es ambiguo ya que las "etiquetas de grupo" pueden ser tratadas (y lo han sido) como pesos.
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 todos los recubrimientos de grafos 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. Journal of Combinatorial Theory, Serie B , Vol. 47, 32–52.
- Thomas Zaslavsky (1991), Grafos sesgados. II. Los tres matroides. Journal of Combinatorial Theory, Serie B , Vol. 51, 46–72.
- Thomas Zaslavsky (1999). Bibliografía matemática de grafos con signo y con ganancia y áreas afines. Revista electrónica de combinatoria, Encuestas dinámicas en combinatoria, n.° DS8.
- Thomas Zaslavsky (2003), Grafos sesgados IV: Realizaciones geométricas. Journal of Combinatorial Theory, Serie B , Vol. 89, núm. 2, págs. 231–297.
