Boole programozás gráfok segítségével

Absztrakt

Olyan speciális egészértékű programozási feladatokat vizsgálunk, amelyekben minden változó a {0,1} értékhalmazból vehet fel értékeket. Megismerkedünk az ún. alap illetve a módosított Boole-programozási feladattal. Az alap Boole-programozási feladatot speciális lineáris programozási feladattá alakítjuk, gráffal reprezentáljuk. Adunk egy algoritmust, amiben a feladatot gráfok segítségével oldjuk meg. A módosított feladat esetén ez a speciális lineáris programozási feladat az eredeti feladatnál gyengébb feltétel rendszert jelent. Ezt a gráfoknál az ún. releváns élek segítségével vesszük figyelembe. A módosított Boole-programozási feladatot az alapfeladathoz hasonló módszerrel oldhatjuk meg.