4.3. A problémaredukciós reprezentációt szemléltető gráf

Legyen a probléma a reprezentációval megadva. Ez a reprezentáció is egy irányított gráfot, ún. ÉS/VAGY gráfot határoz meg.

Azt mondjuk, hogy az irányított ÉS/VAGY gráf a probléma problémaredukciós reprezentációjához tartozó reprezentációs gráfja.

Lemma

Legyen a probléma problémaredukciós reprezentációjához tartozó reprezentációs gráfja. Pontosan akkor áll fenn a reláció, ha a reprezentációs gráfban van az csúcsából induló olyan hiperút, melynek levelei éppen az csúcsok.

Bizonyítás

  1. Tegyük fel, hogy . Ez a redukálhatósag definíció miatt azt jelenti, hogy létezik olyan (véges) problémahalmaz-sorozat úgy, hogy

    Equation 4.. 


    és

    Equation 4.. 


    minden esetén.

    • Tehát minden -re valamelyik problémája, mondjuk -ben már részekre van bontva, azaz van olyan redukciós operátor, amelyik -t épp ezekre a részproblémákra bontja, így a reprezentációs gráfban a -t szemléltető csúcsból ÉS élköteg indul a részproblémákat szemléltető csúcsokba.

    • Továbbá -ben már nem szerepel, tehát újabb hiperél már nem indul belőle.

    Azaz a reprezentációs gráfunkban egy hiperélből álló sorozatunk van, melyben az első hiperél a -t szemléltető csúcsból indul, minden következő hiperél kezdőcsúcsa valamely előző hiperél végcsúcsa, és minden csúcsból legfeljebb egy hiperél indul. Tehát a szemléltető részgráf egy hiperút.

    Továbbá a sorozat utolsó halmazának, -nak a problémái azok, amiket nem bontottunk tovább, tehát az ezeket szemléltető csúcsok a a hiperút levelei.

  2. Most tegyük fel azt, hogy a reprezentációs gráf csúcsából indul olyan hiperút, melynek levelei az csúcsok. Ez azt jelenti, hogy van olyan hiperélsorozat a reprezentációs gráfban, hogy

    Equation 4.. 


    továbbá

    Equation 4.. 


    és

    Equation 4.. 


    A sorozat minden hiperéle egy redukciós operátoralkalmazást szemléltet: az által szepléltetett problémát bontja a redukciós operátor az csúcsok által szemléltetett problémákká. Tehát a hiperélsorozat egy redukciós operátorsorozat, mely első operátorát -ra alkalmaztuk, az összes többit pedig, valamely megelőző operátor eredményeképpen előállt problémára.

Tétel

Legyen a probléma problémaredukciós reprezentációjához tartozó reprezentációs gráfja. Pontosan akkor oldható meg , ha van a reprezentációs gráfban a startcsúcsból induló olyan hiperút, melynek levelei terminális csúcsok.