Grafo signado

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Existen ocho formas de asignar los signos en las aristas de un grafo triángulo. De acuerdo con la teoría de Fritz Heider, un número impar de signos negativos lleva a un triángulo desbalanceado.

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]

Definición formal[editar]

Formalmente, un grafo signado se puede definir como un trío ordenado , donde es su conjunto de vértices, 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 , su signo es .

Ciclos signados[editar]

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[editar]

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 y agrupamiento de redes sociales.[1]

Véase también[editar]

Referencias[editar]

  1. a b c d e Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.

Bibliografía[editar]

  • 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.