Cтраница 2
Для построения таких планов следует использовать один из общих методов решения минимаксных задач. [16]
Удалим из G2 любую дугу, вес которой не меньше с2, и так будем продолжать до тех пор, пока не получим орграф Gm 1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фт в Gm ( с весом ст) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm 1 следует, что в G. Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе G может быть найден с помощью построения полного орграфа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам - бесконечные веса. Если решение минимаксной задачи коммивояжера для Ог имеет конечный вес ( на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот. [17]
Удалим из С2 любую дугу, вес которой не меньше с2, и так будем продолжать до тех пор, пока не получим орграф 6гт 1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фт в Ст ( с весом ст) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Ст 1 следует, что в Сг1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ст. Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе С может быть найден с помощью построения полного орграфа &1 с тем же самым множеством вершин, что и в С, дугам которого, соответствующим дугам из О, приписаны единичные веса, а остальным дугам - бесконечные веса. Если решение минимаксной задачи коммивояжера для Ог имеет конечный вес ( на самом деле равный единице), то в графе С может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе О не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот. [18]
Удалим из G2 любую дугу, вес которой не меньше с2, и так будем продолжать до тех пор, пока не получим орграф Gm 1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фт в Gm ( с весом ст) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm 1 следует, что в G. Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе G может быть найден с помощью построения полного орграфа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам - бесконечные веса. Если решение минимаксной задачи коммивояжера для Ог имеет конечный вес ( на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот. [19]