Hispanopedia Wiki
Articulo de referencia

Grafo con signo

Existen ocho maneras de asignar signos a los lados de un triángulo. Según la teoría de Fritz Heider , un número impar de signos negativos forma un triángulo desequilibrado. En e...

Hispanopedia WikiContenido en espanolLectura gratuita
Existen ocho maneras de asignar signos a los lados de un triángulo. Según la teoría de Fritz Heider , un número impar de signos negativos forma un triángulo desequilibrado.

En el ámbito 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 signos está equilibrado si el producto de los signos de las aristas alrededor de cada ciclo es positivo. El nombre "grafo con signos" 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 con 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 del equilibrio en triángulos de sentimientos de Fritz Heider a una teoría psicológica del equilibrio en grafos con signos. [ 3 ] [ 4 ]

Los grafos con signo se han redescubierto muchas veces porque aparecen de forma 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 topológica de grafos y en 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 se necesita encontrar un conjunto de aristas equilibrado más grande en Σ. Se han aplicado a la clasificación de datos en el agrupamiento de correlación .

Teorema fundamental

El signo de un camino es el producto de los signos de sus aristas. Por lo tanto, un camino es positivo solo si hay un número par de aristas negativas en él (donde cero es par). En la teoría del equilibrio matemático de Frank Harary , un grafo con signo es equilibrado cuando cada ciclo es positivo. Harary demuestra que un grafo con signo es 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 ] Esto generaliza el teorema de que un grafo ordinario (sin signo) es bipartito si y solo si cada ciclo tiene longitud par.

Una demostración sencilla utiliza el método de intercambio. Intercambiar un grafo con signos significa invertir los signos de todas las aristas entre un subconjunto de vértices y su complemento. Para demostrar el teorema de Harary, se muestra por inducción que Σ puede cambiarse a todos los signos positivos si y solo si es un grafo balanceado.

Un teorema más débil, pero con una demostración más sencilla, establece que si cada ciclo de 3 vértices en un grafo completo con signos es positivo, entonces el grafo está equilibrado. Para la demostración, se elige un nodo arbitrario n y se coloca junto con todos los nodos conectados a n mediante una arista positiva en un grupo, llamado A , y todos los nodos conectados a n mediante una arista negativa en otro, llamado B. Dado que se trata de un grafo completo, cada par de nodos en A debe ser amigo y cada par de nodos en B también debe ser amigo; de lo contrario, existiría un ciclo de 3 vértices desequilibrado. (Como se trata de un grafo completo, cualquier arista negativa provocaría un ciclo de 3 vértices desequilibrado). Asimismo, todas las aristas negativas deben conectar los dos grupos. [ 6 ]

Frustración

Índice de frustración

El índice de frustración (anteriormente denominado índice de equilibrio lineal [ 7 ] ) de Σ es el número mínimo de aristas cuya eliminación, o equivalentemente cuya inversión de signo (un teorema de Harary [ 7 ] ), hace que Σ sea equilibrada. La razón de esta equivalencia es que el índice de frustración es igual al número mínimo de aristas cuya negación (o, equivalentemente, eliminación) hace que Σ sea equilibrada.

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 ciclos negativos .

Hay otra definición equivalente (que se puede demostrar fácilmente intercambiando). A cada vértice se le asigna un valor de +1 o −1 ; a esto lo llamamos un estado de Σ. Una arista se llama satisfecha si es positiva y ambos extremos tienen el mismo valor, o si 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 sobre 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 dicho conjunto es un subgrafo equilibrado de Σ con la mayor cantidad de aristas posibles.

Calcular el índice de frustración es un problema NP-difícil .

Se puede apreciar la complejidad NP-difícil al observar que el índice de frustración de un grafo con todos los signos negativos es el mismo que el del problema del corte máximo en la teoría de grafos, que es NP-difícil.

El índice de frustración es importante en un modelo de vidrios de espín , el modelo de Ising mixto . En este modelo, el grafo con signo es fijo. Un estado consiste en asignar un "espín", ya sea "hacia arriba" o "hacia abajo", a cada vértice. Consideramos 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 cuanto más aristas frustradas tiene, por lo que un estado fundamental es un estado con la menor energía frustrada. Así, para hallar la energía del estado fundamental de Σ, es necesario hallar el índice de frustración.

Número de frustración

El número de vértices 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 Σ resulta en equilibrio. De forma equivalente, se busca el orden más grande de un subgrafo inducido equilibrado de Σ.

Problemas algorítmicos

Tres preguntas fundamentales sobre un grafo con signos son: ¿Está equilibrado? ¿Cuál es el tamaño máximo de un conjunto de aristas equilibradas en él? ¿Cuál es el número mínimo de vértices que deben eliminarse para que esté equilibrado? La primera pregunta es fácil de resolver en tiempo polinomial. La segunda pregunta se denomina problema del Índice de Frustración o Subgrafo Equilibrado Máximo . Es NP-difícil porque su caso especial (cuando todas las aristas del grafo son negativas) es el problema NP-difícil de Corte Máximo . La tercera pregunta se denomina problema del Número de Frustración o Subgrafo Inducido Equilibrado Máximo , y también es NP-difícil ; véase, por ejemplo, [ 9 ].

teoría de los matroides

Existen dos matroides asociados a un grafo con signos: el matroide gráfico con signos (también llamado matroide de marco o, a veces, matroide de sesgo ) y el matroide de elevación . Ambos generalizan el matroide de ciclo de un grafo. Son casos especiales de los mismos matroides de un grafo con sesgo .

El matroide de marco (o matroide gráfico con signo ) M ( G ) tiene como conjunto base el conjunto de aristas E. [ 10 ] Un conjunto de aristas es independiente si cada componente contiene o bien ningún círculo o bien un solo círculo, que es negativo. (En la teoría de matroides, una media arista actúa exactamente como un bucle negativo). Un circuito del matroide es o bien un círculo positivo, o bien un par de círculos negativos junto con un camino simple de conexión, de modo que los dos círculos sean disjuntos (en cuyo caso el camino de conexión tiene un extremo en común con cada círculo y, por lo demás, es disjunto de ambos) o bien compartan 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 balanceadas de S , contando los vértices aislados como componentes balanceadas. Este matroide es el matroide columna de la matriz de incidencia del grafo con signo. Por eso describe las dependencias lineales de las raíces de un sistema de raíces clásico.

El matroide de elevació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 elevación L ( G ) es el matroide de elevación extendido restringido a E . El punto extra actúa exactamente como un bucle negativo, por lo que solo describimos el matroide de elevación. Un conjunto de aristas es independiente si no contiene círculos o solo un círculo, que es negativo. (Esta es la misma regla que se aplica por separado a cada componente en el matroide 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 común. El rango de un conjunto de aristas S es n − c + ε, donde c es el número de componentes de S , contando los vértices aislados, y ε es 0 si S es balanceado y 1 si no lo es.

Otros tipos de "grafos con signo"

A veces, los signos se interpretan como +1 y −1 . Esto es solo una diferencia de notación, si los signos se multiplican alrededor de un círculo y lo importante es el signo del producto. Sin embargo, existen otras dos formas de tratar las etiquetas de las aristas que no se ajustan a la teoría de grafos con signos.

El término grafo con signos se aplica ocasionalmente a grafos en los que cada arista tiene un peso, w ( e ) = +1 o −1 . Estos no son el mismo tipo de grafo con signos; son grafos ponderados con un conjunto de pesos restringido. La diferencia radica en que los pesos se suman, no se multiplican. Los problemas y los métodos son completamente distintos.

El nombre también se aplica a grafos en los que los signos funcionan como colores en las aristas. La importancia del color radica en que determina los distintos pesos aplicados a la arista, y no en que su signo sea intrínsecamente significativo. Este es el caso en la teoría de nudos , donde la única importancia de los signos es que pueden intercambiarse mediante el grupo de dos elementos, pero no existe una diferencia intrínseca entre positivo y negativo. El matroide de un grafo con signos coloreados es el matroide cíclico del grafo subyacente; no es el matroide de marco o de elevación del grafo con signos. Las etiquetas de los signos, en lugar de modificar el matroide, se convierten en signos en los elementos del mismo.

En este artículo solo trataremos la teoría de grafos con signos en sentido estricto. Para grafos con signos y colores, véase matroides coloreados .

Dígrafo firmado

Un digrafo con signos es un grafo dirigido con arcos con signos. Los digrafos con signos son mucho más complejos que los grafos con signos, ya que solo los signos de los ciclos dirigidos son relevantes. 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 signos.

Los digrafos con signo no deben confundirse con los grafos orientados con signo . Estos últimos son grafos bidireccionales , no grafos dirigidos (excepto en el caso trivial de todos los signos positivos).

Signos del vértice

Un grafo con vértices marcados , a veces llamado grafo con signos , es un grafo cuyos vértices tienen signos asignados. Un círculo se denomina consistente (aunque esto no guarda relación 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 armónicos con vértices marcados análoga al teorema de equilibrio de Harary; en cambio, la caracterización ha sido un problema difícil, resuelto de forma más general por Joglekar, Shah y Diwan (2012). [ 11 ]

A menudo resulta sencillo añadir signos de arista a la teoría de signos de vértice sin grandes cambios; por lo tanto, muchos resultados para grafos con signos de vértice (o "grafos con signos marcados") se extienden naturalmente a grafos con signos de vértice y arista. Esto se observa especialmente en la caracterización de la armonía propuesta por Joglekar, Shah y Diwan (2012).

La diferencia entre un grafo con signos marcados y un grafo con signos con una función de estado (como en § Frustración ) es que los signos de los vértices en el primero son parte de la estructura esencial, mientras que una función de estado es una función variable en el grafo con signos.

Tenga en cuenta que el término "grafo marcado" se usa ampliamente en redes de Petri con un significado completamente diferente; consulte el artículo sobre grafos marcados .

Colorante

Al igual que con los grafos sin signo , existe el concepto de coloración de grafos con signo. Mientras que la coloración de un grafo es una función que asigna el conjunto de vértices a los números naturales, la coloración de un grafo con signo es una función que asigna el conjunto de vértices a los números enteros. Las restricciones sobre las coloraciones adecuadas provienen de las aristas del grafo con signo. Los números enteros asignados a dos vértices deben ser distintos si están conectados por una arista positiva. Las etiquetas de los vértices adyacentes no deben ser inversos aditivos si los vértices están conectados por una arista negativa. No puede existir una coloración adecuada de un grafo con signo con un bucle positivo.

Cuando se restringen las etiquetas de los vértices al conjunto de 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 de2k+1{\displaystyle 2k+1}Se denomina polinomio cromático del grafo con signo. Es análogo al polinomio cromático de un grafo sin signo.

Aplicaciones

psicología social

En psicología social , los grafos con signos se han utilizado para modelar situaciones sociales, donde las aristas positivas representan amistades y las negativas enemistades entre nodos, que representan personas. [ 3 ] Entonces, por ejemplo, un ciclo positivo de 3 es o bien tres amigos mutuos, o dos amigos con un enemigo común; mientras que un ciclo negativo de 3 es o bien tres enemigos mutuos, o dos enemigos que comparten un amigo común. 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 hará 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 una de sus amistades en enemistad.

Antal, Krapivsky y Reder consideran la dinámica social como el cambio de signo en una arista de un grafo con signos. [ 12 ] Las relaciones sociales con amigos anteriores de una pareja que se divorcia se utilizan para ilustrar la evolución de un grafo con signos en la sociedad. Otra ilustración describe las cambiantes alianzas internacionales entre 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 este último caso un cambio de relación se realiza solo cuando se reduce el número total de tríadas desequilibradas. La simulación supuso un grafo completo con relaciones aleatorias con una tríada desequilibrada aleatoria seleccionada para la transformación. La evolución del grafo con signos con N nodos bajo este proceso se estudia y simula para describir la densidad estacionaria de enlaces amistosos.

La teoría del equilibrio ha sido severamente cuestionada, especialmente en su aplicación a sistemas grandes, bajo el argumento teórico de que las relaciones amistosas mantienen unida a una sociedad, mientras que una sociedad dividida en dos bandos enemigos sería altamente inestable. [ 13 ] Los estudios experimentales también han proporcionado una confirmación débil de las predicciones de la teoría del equilibrio estructural. [ 14 ]

Vasos giratorios

En física, los gráficos con signos constituyen un contexto natural para el modelo de Ising no ferromagnético , que se aplica al estudio de los vidrios de espín .

Sistemas complejos

Un digrafo con signo de tres variables que representa un sistema trófico simple.

Utilizando un método analítico desarrollado inicialmente en biología de poblaciones y ecología, pero que ahora se utiliza en muchas disciplinas científicas, los digrafos con signo han encontrado aplicación en el razonamiento sobre el comportamiento de sistemas causales complejos. [ 15 ] [ 16 ] Estos análisis responden preguntas sobre la retroalimentación en niveles dados del sistema, y ​​sobre la dirección de las respuestas variables ante una perturbación del sistema en uno o más puntos, las correlaciones variables ante tales perturbaciones, la distribución de la varianza en todo el sistema y la sensibilidad o insensibilidad de variables particulares a las perturbaciones del sistema.

Agrupación de datos

El análisis de correlación busca agrupaciones naturales de datos según su similitud. Los puntos de datos se representan como los vértices de un grafo, donde una arista positiva une elementos similares y una arista negativa une elementos diferentes.

Neurociencia

El cerebro puede considerarse como un grafo con signos donde la sincronía y la antisincronía entre los patrones de actividad de las regiones cerebrales determinan las aristas positivas y negativas. En este sentido, se puede explorar la estabilidad y la energía de la red cerebral. [ 17 ] Además, recientemente, el concepto de frustración se ha utilizado en el análisis de redes cerebrales para identificar el conjunto no trivial de conexiones neuronales y resaltar los elementos ajustables del cerebro. [ 18 ]

Generalizaciones

Un grafo con signos es un tipo especial de grafo de ganancia en el que el grupo de ganancia tiene orden 2. El par ( G , B (Σ)) determinado por un grafo con signos Σ es un tipo especial de grafo sesgado . El grupo de signos tiene la propiedad especial, no compartida por grupos de ganancia mayores, de que los signos de las aristas están determinados, salvo conmutación, por el conjunto B (Σ) de ciclos balanceados. [ 19 ]

Notas

  1. 1 2 Harary, Frank (1955), "Sobre la noción de equilibrio de un grafo con signo" , Michigan Mathematical Journal , 2 : 143–146 , MR 0067468 {{citation}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  2. ^ Kőnig, Dénes (1936), Akademische Verlagsgesellschaft (ed.), Theorie der endlichen und unendlichen Graphen
  3. 1 2 Cartwright, D.; Harary, Frank (1956). "Equilibrio estructural: una generalización de la teoría de Heider" (PDF) . Psychological Review . 63 (5): 277– 293. doi : 10.1037/h0046049 . PMID 13359597 . 
  4. ↑ Steven Strogatz (2010), El enemigo de mi enemigo , The New York Times , 14 de febrero de 2010
  5. ↑ Zaslavsky, Thomas (1998), "Una bibliografía matemática de grafos con signo y de ganancia y áreas afines" , Electronic Journal of Combinatorics , 5 , Dynamic Surveys 8, 124 pp., MR 1744869 .
  6. ↑ Luis Von Ahn La ciencia de la web Lección 3 pág. 28
  7. 1 2 Harary, Frank (1959), Sobre la medición del equilibrio estructural, Behavioral Science 4, 316–323.
  8. ↑ Robert P. Abelson; Milton J. Rosenberg (1958), Psicología simbólica: un modelo de cognición actitudinal, Behavioral Science 3, 1–13.
  9. ↑ Gülpinar, N.; Gutin, G. ; Mitra, G.; Zverovitch, A. (2004). "Extracción de submatrices de red puras en programas lineales usando grafos con signo". Discrete Appl. Math. 137 (3): 359– 372. doi : 10.1016/S0166-218X(03)00361-5 .
  10. ↑ Zaslavsky, Thomas (1982), "Grafos con signo", Matemáticas Aplicadas Discretas , 4 (1): 47– 74, doi : 10.1016/0166-218X(82)90033-6 , hdl : 10338.dmlcz/127957 , MR 0676405 . Errata. Matemáticas Discretas Aplicadas , 5 (1983), 248
  11. ↑ Manas Joglekar, Nisarg Shah y Ajit A. Diwan (2012), "Grafos etiquetados de grupos balanceados", Matemáticas Discretas , vol. 312, n.º 9, págs. 1542–1549.
  12. ↑ T. Antal, PL Krapivsky y S. Redner (2006) Equilibrio social en redes: la dinámica de la amistad y la enemistad
  13. ↑ B. Anderson, en Perspectives on Social Network Research , ed. PW Holland y S. Leinhardt. Nueva York: Academic Press, 1979.
  14. ↑ Morrissette, Julian O.; Jahnke, John C. (1967). "No hay relaciones y las relaciones de fuerza son cero en la teoría del equilibrio estructural". Human Relations . 20 (2): 189– 195. doi : 10.1177/001872676702000207 . S2CID 143210382 . 
  15. ↑ Puccia, Charles J. y Levins, Richard (1986). Modelado cualitativo de sistemas complejos: una introducción al análisis de bucles y al promedio temporal . Harvard University Press, Cambridge, MA.
  16. ↑ Dambacher, Jeffrey M.; Li, Hiram W.; Rossignol, Philippe A. (2002). "Relevancia de la estructura de la comunidad en la evaluación de la indeterminación de las predicciones ecológicas". Ecology . 83 (5): 1372– 1385. doi : 10.1890/0012-9658(2002)083 [ 1372:rocsia ] 2.0.co ; 2 . JSTOR 3071950 . 
  17. ↑ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (enero de 2021). "Impacto topológico de los enlaces negativos en la estabilidad de la red cerebral en estado de reposo" . Scientific Reports . 11 (1): 2176. Bibcode : 2021NatSR..11.2176S . doi : 10.1038/ s41598-021-81767-7 . PMC 7838299. PMID 33500525 .  
  18. ↑ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (octubre de 2022). "Patrón de formación de frustración en la red cerebral funcional" . Neurociencia de redes . 6 (4): 1334– 1356. doi : 10.1162/netn_a_00268 . PMC 11117102. PMID 38800463 .  
  19. ↑ Zaslavsky, Thomas (1981). "Caracterizaciones de grafos con signos". Journal of Graph Theory . 5 (4): 401– 406. doi : 10.1002/jgt.3190050409 .

Referencias

  • Cartwright, D.; Harary, F. (1956), "Equilibrio estructural: una generalización de la teoría de Heider", Psychological Review , 63 (5): 277– 293, doi : 10.1037/h0046049 , PMID 13359597 .
  • Seidel, JJ (1976), "Un estudio de dos gráficos", Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I , Atti dei Convegni Lincei, vol.  17, Roma: Accademia Nazionale dei Lincei , págs. 481–511 , MR 0550136  .
  • Zaslavsky, Thomas (1998), "Una bibliografía matemática de grafos con signo y de ganancia y áreas afines" , Electronic Journal of Combinatorics , 5 , Dynamic Surveys 8, 124 pp., MR 1744869