|
|
| Строка 116: |
Строка 116: |
|
| |
|
|
| |
|
| Требуется: двудольный граф G = (V1, V2, E), целое число k, отношение линейного порядка<1 на V1, отношение частичного порядка <2 на V2. Результат: ДА в том и только том случае, если данный экземпляр задачи односторонней минимизации пересечений (OSCM) имеет решение
| | [[Файл:PADG_code.png]] |
| repeat
| |
| Исчерпывающим образом применить правила редукции, соответственно корректируя <2 и k. Определить вершины, порядок которых был установлен при помощи транзитивности, и соответствующим образом скорректировать <2 и k, до тех пор, пока не останется вариантов изменения <2 и k: if k < 0 or <2 содержит и (x, y), и (y; x) then
| |
| return НЕТ.
| |
| else if 9fx; у} С V2 : не имеет места ни x <2 y, y <2 x then if OSCM-ST-simple(G,fc- 1;<1;<2 [ f(x, y)g) then
| |
| return ДА 10: else
| |
| return OSCM-ST-simple(G ;k - 1; <b <2 [ f(y;x)g) end if else
| |
| return ДА 15: end if
| |
|
| |
|
|
| |
|
