. . ۳, . . ٳ۳

D(G) = 3 ٳ G ٳ ݻ ϳ-ѳ
2-ٳ ۳ ݹ NP-۳ ٳ

    NP- ݹ, D(G) = 3 ٳ G ٳ ݻ ݻ ۳, V1 V2 ѳ óݻ ٳ ٻ , v l(v) ó ϳ ݻݳ ||l(v)V1| - |l(v)V2|| 1 ѳ: