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.

Además, el dual del dual de un grafo signado, vuelve a restablecer las aristas a sus signos originales.

[2]​[3]​ Formalmente, un grafo signado se puede definir como un trío ordenado

es su conjunto de aristas, y

es el conjunto de signos asociados a cada arista.

[1]​ Note que como en un grafo ponderado,

se puede representar también como una función de asignación de pesos, en este caso,

, de modo que para cualquier arista

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]​ 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.