Grafo signado

En teoría de grafos, un grafo signado o grafo con signos es un grafo cuyas aristas tienen un signo positivo o negativo, que puede representar cualquier relación dicotómica.^[1]​

Existen ocho formas de asignar los signos en las aristas de un grafo triángulo. De acuerdo con la teoría del equilibrio estructural de Fritz Heider, un número impar de signos negativos lleva a un triángulo desbalanceado.

Estos grafos cumplen con la propiedad de dualidad antitética, de modo que el dual de un grafo signado implica cambiar el signo de sus aristas. Además, el dual del dual de un grafo signado, vuelve a restablecer las aristas a sus signos originales.^[2]​^[3]​

Definición formal

Formalmente, un grafo signado se puede definir como un trío ordenado ${\displaystyle G_{\pm }=(V,E,S)}$ , donde ${\displaystyle V=\{v_{1},\ldots ,v_{n}\}}$  es su conjunto de vértices, ${\displaystyle E=\{e_{1},\ldots ,e_{m}\}}$  es su conjunto de aristas, y ${\displaystyle S=\{s_{1},\ldots ,s_{m}\}}$  es el conjunto de signos asociados a cada arista.^[1]​ Note que como en un grafo ponderado, ${\displaystyle S}$  se puede representar también como una función de asignación de pesos, en este caso, ${\displaystyle s:E\to \{+,-\}}$ , de modo que para cualquier arista ${\displaystyle e\in E}$ , su signo es ${\displaystyle s(e)\in \{+,-\}}$ .

Ciclos signados

El signo de un ciclo o de un semiciclo se define como el producto de los signos de las aristas incluidas en el ciclo, calculado de acuerdo a una conjunción lógica:^[1]​

• (+)(+) = +
• (+)(–) = –
• (–)(+) = –
• (–)(–) = +

Por lo tanto, un ciclo con un número par de aristas negativas tendrá un signo positivo, y un ciclo con un número impar de aristas negativas tendrá un signo negativo.^[1]​

Aplicaciones

En análisis de redes sociales, los grafos con signos permiten representar los lazos de una red social como relaciones valoradas, del tipo quiere/odia, aliado/enemigo, aprueba/rechaza, etc. Este tipo de grafos se utiliza en el estudio del equilibrio estructural de redes sociales,^[1]​ así como en el estudio de agrupabilidad de redes y grafos.^[3]​

Véase también

• Grafo ponderado
• Grafo etiquetado

Referencias

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Harary, F. (1957). «Structural duality». Behavioral Science 2 (4): 255-265. doi:10.1002/bs.3830020403. 
3. Wasserman y Faust, 2013, «Equilibrio estructural y transitividad», pp. 241-268.

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

•   Datos: Q11246292