Estaba leyendo Teoría de grafos y redes complejas por Maarten van Steen. Estaba leyendo sobre grafos con signo no dirigidos en la sección sobre análisis de redes sociales, que contiene el siguiente teorema:
Un grafo no dirigido con signo G está equilibrado si y sólo si V(G) puede dividirse en dos subconjuntos disjuntos $V_0$ y $V_1$ de forma que se cumplan las dos condiciones siguientes:
(1) $E^-(G) = \{\langle x, y \rangle | x \in V_0, y \in V_1 \}$
(2) $E^+(G) = \{ \langle x, y \rangle | x, y \in V_0 \thinspace or \thinspace x, y \in V_1 \}$
El caso nº 1 (sobre todo teniendo en cuenta la descripción previa en el libro) me parece bastante parecido a los criterios de un grafo bipartito. ¿Significa este teorema básicamente que si tuvieras un grafo en el que cada arista tuviera signo negativo (es decir. $E^-(G) = E(G)$ ) entonces $G$ debe ser bipartita?
Edita: Un grafo con signo es un grafo simple en el que cada arista está etiquetada con un signo (- o +). Un grafo no dirigido con signo está equilibrado cuando todos sus ciclos son positivos. El signo de un conjunto de aristas se puede hallar multiplicando todos los signos de las aristas del conjunto; el resultado de multiplicar dos signos es negativo si exactamente uno de los signos es negativo y positivo en caso contrario (así, por ejemplo, - * - = + y - * + = -).
