1. Знаковые графы

Граф является моделью для представления отношений между людьми, например, отношения "лицо u знает лицо v". Такие отношения могут иметь и иной смысл, не обязательно только означая, что u знает или не знает v.

Рис. 1. Знаковый орграф D и знаковый граф G

В знаковом орграфе D на рис. 1 путь u, v, w, у имеет знак минус, и контур u, v, w, x, имеет знак плюс. В знаковом графе G на рис. 1 цепь а, b, с, d отрицательна. Очевидно, что путь и цепь имеют знак минус, если число отрицательных дуг или ребер, содержащихся в них, нечетно, в противном случае они имеют знак плюс.