En el área de la teoría de grafos en matemáticas , un grafo con signo es un grafo en el que cada arista tiene un signo positivo o negativo.
Un grafo con signo está equilibrado si el producto de los signos de las aristas alrededor de cada ciclo es positivo. El nombre de "grafo con signo" y la noción de equilibrio aparecieron por primera vez en un artículo matemático de Frank Harary en 1953. [1] Dénes Kőnig ya había estudiado nociones equivalentes en 1936 bajo una terminología diferente pero sin reconocer la relevancia del grupo de signos. [2] En el Centro de Dinámica de Grupos de la Universidad de Michigan , Dorwin Cartwright y Harary generalizaron la teoría psicológica de equilibrio de Fritz Heider en triángulos de sentimientos a una teoría psicológica de equilibrio en grafos con signo. [3] [4]
Los grafos con signo han sido redescubiertos muchas veces porque surgen de manera natural en muchas áreas no relacionadas. [5] Por ejemplo, permiten describir y analizar la geometría de subconjuntos de los sistemas de raíces clásicos . Aparecen en la teoría de grafos topológicos y la teoría de grupos . Son un contexto natural para preguntas sobre ciclos pares e impares en grafos. Aparecen en el cálculo de la energía del estado fundamental en el modelo de Ising no ferromagnético ; para esto, es necesario encontrar el conjunto de aristas más grande y equilibrado en Σ. Se han aplicado a la clasificación de datos en la agrupación por correlación .
El signo de un camino es el producto de los signos de sus aristas. Por lo tanto, un camino es positivo solo si tiene un número par de aristas negativas (donde cero es par). En la teoría del equilibrio matemático de Frank Harary , un grafo con signo está equilibrado cuando cada ciclo es positivo. Harary demuestra que un grafo con signo está equilibrado cuando (1) para cada par de nodos, todos los caminos entre ellos tienen el mismo signo, o (2) los vértices se dividen en un par de subconjuntos (posiblemente vacíos), cada uno conteniendo solo aristas positivas, pero conectados por aristas negativas. [1] Generaliza el teorema de que un grafo ordinario (sin signo) es bipartito si y solo si cada ciclo tiene una longitud par.
Una prueba sencilla utiliza el método de cambio de signo. Cambiar un grafo con signo significa invertir los signos de todas las aristas entre un subconjunto de vértices y su complemento. Para demostrar el teorema de Harary, se demuestra por inducción que Σ puede cambiarse para que sea todo positivo si y solo si está balanceado.
Un teorema más débil, pero con una prueba más simple, es que si cada 3-ciclo en un grafo completo con signo es positivo, entonces el grafo está balanceado. Para la prueba, escoja un nodo arbitrario n y colóquelo junto con todos aquellos nodos que están unidos a n por una arista positiva en un grupo, llamado A , y todos aquellos unidos a n por una arista negativa en el otro, llamado B . Como este es un grafo completo, cada dos nodos en A deben ser amigos y cada dos nodos en B deben ser amigos, de lo contrario habría un 3-ciclo que estaría desequilibrado. (Como este es un grafo completo, cualquier arista negativa causaría un 3-ciclo desequilibrado). Del mismo modo, todas las aristas negativas deben ir entre los dos grupos. [6]
El índice de frustración (llamado en un principio índice de línea de equilibrio [7] ) de Σ es el número más pequeño de aristas cuya eliminación, o equivalentemente cuya inversión de signo (un teorema de Harary [7] ), hace que Σ esté equilibrado. La razón de la equivalencia es que el índice de frustración es igual al número más pequeño de aristas cuya negación (o, equivalentemente, eliminación) hace que Σ esté equilibrado.
Una segunda forma de describir el índice de frustración es que es el número más pequeño de aristas que cubren todos los ciclos negativos. Esta cantidad se ha denominado número de cobertura de ciclo negativo .
Hay otra definición equivalente (que se puede demostrar fácilmente cambiando). Démosle a cada vértice un valor de +1 o −1; llamamos a esto un estado de Σ. Una arista se llama satisfecha si es positiva y ambos extremos tienen el mismo valor, o es negativa y los extremos tienen valores opuestos. Una arista que no está satisfecha se llama frustrada . El número más pequeño de aristas frustradas en todos los estados es el índice de frustración. Esta definición fue introducida por primera vez en una notación diferente por Abelson y Rosenberg bajo el nombre (obsoleto) de complejidad . [8] El complemento de un conjunto de este tipo es un subgrafo balanceado de Σ con la mayor cantidad de aristas posibles.
Encontrar el índice de frustración es un problema NP-hard . Aref et al. sugieren modelos de programación binaria que son capaces de calcular el índice de frustración de grafos con hasta 10 5 aristas en un tiempo razonable. [9] [10] [11] Se puede ver la complejidad NP-hard observando que el índice de frustración de un grafo con signo totalmente negativo es el mismo que el problema de corte máximo en la teoría de grafos, que es NP-hard.
El índice de frustración es importante en un modelo de vidrios de espín , el modelo mixto de Ising . En este modelo, el grafo con signo es fijo. Un estado consiste en dar un "espín", ya sea "arriba" o "abajo", a cada vértice. Pensamos en el espín hacia arriba como +1 y el espín hacia abajo como −1. Por lo tanto, cada estado tiene un número de aristas frustradas. La energía de un estado es mayor cuando tiene más aristas frustradas, por lo que un estado fundamental es un estado con la menor energía frustrada. Por lo tanto, para encontrar la energía del estado fundamental de Σ uno tiene que encontrar el índice de frustración.
El número de vértice análogo es el número de frustración , definido como el número más pequeño de vértices cuya eliminación de Σ da como resultado el equilibrio. De manera equivalente, se desea el orden más grande de un subgrafo inducido equilibrado de Σ.
Tres preguntas fundamentales sobre un grafo con signo son: ¿Está equilibrado? ¿Cuál es el tamaño más grande de un conjunto de aristas equilibradas en él? ¿Cuál es el número más pequeño de vértices que se deben eliminar para que esté equilibrado? La primera pregunta es fácil de resolver en tiempo polinomial. La segunda pregunta se llama problema del índice de frustración o del subgrafo equilibrado máximo . Es NP-duro porque su caso especial (cuando todas las aristas del grafo son negativas) es el problema NP-duro de corte máximo . La tercera pregunta se llama problema del número de frustración o del subgrafo inducido equilibrado máximo , también es NP-duro ; véase, por ejemplo, [12]
Hay dos matroides asociadas con un grafo con signo, llamadas matroide de gráfico con signo (también llamada matroide de marco o, a veces, matroide de polarización ) y matroide de sustentación , las cuales generalizan el matroide de ciclo de un grafo. Son casos especiales de los mismos matroides de un grafo polarizado .
El matroide de marco (o matroide de gráfico con signo ) M ( G ) tiene como conjunto base el conjunto de aristas E . [13] Un conjunto de aristas es independiente si cada componente no contiene círculos o solo contiene un círculo, lo cual es negativo. (En la teoría de matroides, una media arista actúa exactamente como un bucle negativo). Un circuito del matroide es un círculo positivo o un par de círculos negativos junto con un camino simple de conexión, de modo que los dos círculos son disjuntos (entonces, el camino de conexión tiene un extremo en común con cada círculo y, de lo contrario, es disjunto de ambos) o comparten solo un único vértice común (en este caso, el camino de conexión es ese único vértice). El rango de un conjunto de aristas S es n − b , donde n es el número de vértices de G y b es el número de componentes balanceados de S , contando los vértices aislados como componentes balanceados. Este matroide es el matroide columna de la matriz de incidencia del grafo con signo. Es por eso que describe las dependencias lineales de las raíces de un sistema de raíces clásico.
El matroide de sustentación extendido L 0 ( G ) tiene como conjunto base el conjunto E 0 la unión del conjunto de aristas E con un punto extra , que denotamos e 0 . El matroide de sustentación L ( G ) es el matroide de sustentación extendido restringido a E . El punto extra actúa exactamente como un bucle negativo, por lo que describimos solo el matroide de sustentación. Un conjunto de aristas es independiente si no contiene círculos o solo contiene un círculo, que es negativo. (Esta es la misma regla que se aplica por separado a cada componente en el matroide de gráfico con signo). Un circuito matroide es un círculo positivo o un par de círculos negativos que son disjuntos o tienen solo un vértice en común. El rango de un conjunto de aristas S es n − c + ε, donde c es el número de componentes de S , contando vértices aislados, y ε es 0 si S está equilibrado y 1 si no lo está.
A veces, los signos se toman como +1 y -1. Esto es solo una diferencia de notación, si los signos se siguen multiplicando alrededor de un círculo y el signo del producto es lo importante. Sin embargo, hay otras dos formas de tratar las etiquetas de las aristas que no encajan en la teoría de grafos con signo.
El término grafo con signo se aplica ocasionalmente a grafos en los que cada arista tiene un peso, w ( e ) = +1 o −1. No se trata del mismo tipo de grafo con signo; son grafos ponderados con un conjunto de pesos restringido. La diferencia es que los pesos se suman, no se multiplican. Los problemas y los métodos son completamente diferentes.
El nombre también se aplica a los grafos en los que los signos funcionan como colores en los bordes. La importancia del color es que determina varios pesos aplicados al borde, y no que su signo sea intrínsecamente significativo. Este es el caso de la teoría de nudos , donde el único significado de los signos es que pueden ser intercambiados por el grupo de dos elementos, pero no hay una diferencia intrínseca entre positivo y negativo. El matroide de un grafo con color de signo es el matroide de ciclo del grafo subyacente; no es el matroide de marco o sustentación del grafo con signo. Las etiquetas de signo, en lugar de cambiar el matroide, se convierten en signos en los elementos del matroide.
En este artículo, analizamos únicamente la teoría de grafos con signo en sentido estricto. Para grafos con signo coloreado, consulte matroides coloreados .
Un dígrafo con signo es un grafo dirigido con arcos con signo. Los dígrafos con signo son mucho más complicados que los grafos con signo, porque solo los signos de los ciclos dirigidos son significativos. Por ejemplo, existen varias definiciones de equilibrio, cada una de las cuales es difícil de caracterizar, en marcado contraste con la situación de los grafos no dirigidos con signo.
Los dígrafos con signo no deben confundirse con los grafos con signo orientados. Estos últimos son grafos bidireccionales , no grafos dirigidos (excepto en el caso trivial de todos los signos positivos).
Un grafo con signo de vértice , a veces llamado grafo marcado , es un grafo cuyos vértices tienen signos asignados. Un círculo se llama consistente (pero esto no está relacionado con la consistencia lógica) o armonioso si el producto de los signos de sus vértices es positivo, e inconsistente o inarmónico si el producto es negativo. No existe una caracterización simple de los grafos con signo de vértice armoniosos análoga al teorema de equilibrio de Harary; en cambio, la caracterización ha sido un problema difícil, mejor resuelto (aún de manera más general) por Joglekar, Shah y Diwan (2012). [14]
A menudo resulta fácil añadir signos de arista a la teoría de signos de vértice sin realizar cambios importantes; por lo tanto, muchos resultados para grafos con signo de vértice (o "grafos con signo marcado") se extienden naturalmente a grafos con signo de vértice y arista. Esto es particularmente cierto en el caso de la caracterización de la armonía de Joglekar, Shah y Diwan (2012).
La diferencia entre un gráfico con signo marcado y un gráfico con signo con una función de estado (como en § Frustración ) es que los signos de vértice en el primero son parte de la estructura esencial, mientras que una función de estado es una función variable en el gráfico con signo.
Tenga en cuenta que el término "gráfico marcado" se usa ampliamente en las redes de Petri con un significado completamente diferente; consulte el artículo sobre gráficos marcados .
Al igual que con los grafos sin signo , existe una noción de coloración de grafos con signo. Mientras que una coloración de un grafo es una aplicación del conjunto de vértices a los números naturales, una coloración de un grafo con signo es una aplicación del conjunto de vértices a los números enteros. Las restricciones sobre las coloraciones adecuadas provienen de los bordes del grafo con signo. Los números enteros asignados a dos vértices deben ser distintos si están conectados por un borde positivo. Las etiquetas de los vértices adyacentes no deben ser inversas aditivas si los vértices están conectados por un borde negativo. No puede haber una coloración adecuada de un grafo con signo con un bucle positivo.
Al restringir las etiquetas de vértice al conjunto de números enteros con magnitud como máximo un número natural k , el conjunto de coloraciones propias de un grafo con signo es finito. La relación entre el número de tales coloraciones propias y k es un polinomio en k ; cuando se expresa en términos de este, se denomina polinomio cromático del grafo con signo. Es análogo al polinomio cromático de un grafo sin signo.
En psicología social , los grafos con signo se han utilizado para modelar situaciones sociales, con bordes positivos que representan amistades y bordes negativos enemistades entre nodos, que representan personas. [3] Entonces, por ejemplo, un ciclo 3 positivo es tres amigos mutuos o dos amigos con un enemigo común; mientras que un ciclo 3 negativo es tres enemigos mutuos o dos enemigos que comparten un amigo mutuo. Según la teoría del equilibrio , los ciclos positivos están equilibrados y se supone que son situaciones sociales estables, mientras que los ciclos negativos están desequilibrados y se supone que son inestables. Según la teoría, en el caso de tres enemigos mutuos, esto se debe a que compartir un enemigo común probablemente haga que dos de los enemigos se conviertan en amigos . En el caso de dos enemigos que comparten un amigo, es probable que el amigo compartido elija a uno sobre el otro y convierta a una de sus amistades en un enemigo.
Antal, Krapivsky y Reder consideran la dinámica social como el cambio de signo en un borde de un grafo con signo. [15] Las relaciones sociales con amigos anteriores de una pareja en proceso de divorcio se utilizan para ilustrar la evolución de un grafo con signo en la sociedad. Otra ilustración describe las cambiantes alianzas internacionales entre las potencias europeas en las décadas anteriores a la Primera Guerra Mundial . Consideran la dinámica de tríadas locales y la dinámica de tríadas restringidas, donde en el último caso se produce un cambio de relación solo cuando se reduce el número total de tríadas desequilibradas. La simulación supuso un grafo completo con relaciones aleatorias que tienen una tríada desequilibrada aleatoria seleccionada para la transformación. Se estudia y simula la evolución del grafo con signo con N nodos bajo este proceso para describir la densidad estacionaria de vínculos amistosos.
La teoría del equilibrio ha sido severamente cuestionada, especialmente en su aplicación a sistemas grandes, sobre la base teórica de que las relaciones amistosas unen a una sociedad, mientras que una sociedad dividida en dos bandos de enemigos sería altamente inestable. [16] Los estudios experimentales también han proporcionado sólo una débil confirmación de las predicciones de la teoría del equilibrio estructural. [17]
En física, los gráficos con signo son un contexto natural para el modelo de Ising no ferromagnético , que se aplica al estudio de los vidrios de espín .
Utilizando un método analítico desarrollado inicialmente en biología de poblaciones y ecología, pero ahora utilizado en muchas disciplinas científicas, los dígrafos con signo han encontrado aplicación en el razonamiento sobre el comportamiento de sistemas causales complejos. [18] [19] Dichos análisis responden a preguntas sobre la retroalimentación en niveles dados del sistema, y sobre la dirección de las respuestas variables dada una perturbación a un sistema en uno o más puntos, las correlaciones variables dadas dichas perturbaciones, la distribución de la varianza a través del sistema, y la sensibilidad o insensibilidad de variables particulares a las perturbaciones del sistema.
La agrupación por correlación busca la agrupación natural de los datos por similitud. Los puntos de datos se representan como vértices de un gráfico, con un borde positivo que une elementos similares y un borde negativo que une elementos diferentes.
El cerebro puede considerarse como un gráfico signado donde la sincronía y la antisincronía entre los patrones de actividad de las regiones cerebrales determinan los bordes positivos y negativos. En este sentido, se puede explorar la estabilidad y la energía de la red cerebral. [20] Además, recientemente, el concepto de frustración se ha utilizado en el análisis de redes cerebrales para identificar el ensamblaje no trivial de conexiones neuronales y destacar los elementos ajustables del cerebro. [21]
Un gráfico con signo es un tipo especial de gráfico de ganancia en el que el grupo de ganancia tiene orden 2. El par ( G , B (Σ)) determinado por un gráfico con signo Σ es un tipo especial de gráfico sesgado . El grupo de signos tiene la propiedad especial, no compartida por grupos de ganancia más grandes, de que los signos de los bordes están determinados hasta la conmutación por el conjunto B (Σ) de ciclos equilibrados. [22]
