Metadata
Author: WikiMatrix
Data
English[en]
Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems (systems of Boolean variables with constraints on the values of pairs of variables): as Aspvall, Plass & Tarjan (1979) showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its complement are both contained in the same strongly connected component of the implication graph of the instance.
Serbian[sr]
Алгоритми за проналажење чврсто повезаних компоненти могу да се користе за решавање проблема 2-SAT (системи Булових променљивих са ограничењима о вредностима парова променљивих): као што су Апсвал, Плас и Тарџан (1979) показали, 2-SAT пример је незадовољив ако и само ако постоји променљива v тако да се v и њен комплемент заједно налазе у истој чврсто повезаној компоненти од импликације графа примера.