Grafo signado

Archiu:Pox.jpg

Existixen huit formes d'assignar els signes en les arestes d'un grafo triàngul. D'acort en la teoria de l'equilibri estructural de Fritz Heider, un número impar de signes negatius du a un triàngul desbalanceado.

En teoria de grafos, un grafo signado o grafo en signes és un grafo que les seues arestes tenen un signe positiu o negatiu, que pot representar qualsevol relació dicotòmica.

Estos grafos complixen en la propietat de dualitat antitética, de modo que el dual d'un grafo signado implica canviar el signe de les seues arestes. Ademés, el dual del dual d'un grafo signado, torna a restablir les arestes als seus signes originals.

Definició formal

Formalment, un grafo signado es pot definir com un trio ordenat $G_{\pm }=(V,E,S)$, a on $V=\{v_1,\dots ,v_n\}$ és el seu conjunt de vèrtiços, $E=\{e_1,\dots ,e_m\}$ és el seu conjunt d'arestes, i $S=\{s_1,\dots ,s_m\}$ és el conjunt de signes associats a cada aresta. Note que com en un grafo ponderat, $S$ es pot representar també com una funció d'assignació de pesos, en este cas, $s:E\to \{+,-\}$, de modo que per a qualsevol aresta $e\in E$, el seu signe és $s(e)\in \{+,-\}$.

Cicles signados

El signe d'un cicle o d'un semiciclo es definix com el producte dels signes de les arestes incloses en el cicle, calculat d'acort a una conjunció llògica:

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

Per lo tant, un cicle en un número par d'arestes negatives tindrà un signe positiu, i un cicle en un número impar d'arestes negatives tindrà un signe negatiu.

Vore també

• Grafo ponderat
• Grafo etiquetat

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.