Направленный ациклический граф через удаление арок или их возврат

Question

Сейчас я боролся за то, чтобы формализовать и полностью доказать следующее:

Нам дана сеть улиц города. Докажите, что если мы сможем удалить все циклы в этой сети, создав не более p блоков, то мы сможем удалить все циклы в городской сети, изменив один путь на максимум p улиц.

Блокировка означает перекрытие улицы с односторонним движением. Реверсивный - (в случае улицы с двусторонним движением) означает, что один из путей инвертирован, и тогда оба пути одинаковы. Движение задним ходом (в случае улицы с односторонним движением) означает, что единственный путь перевернут

Теперь проблема заключается в том, чтобы сначала иметь случайный ориентированный граф, который может иметь циклы, которые мы должны удалить. С помощью метода BLOCKING мы гарантируем, что если мы заблокируем не более p узлов, мы получим DAG. Таким образом, проблема, на самом деле, состоит в том, чтобы доказать, что блокировка эквивалентна в результате и сделаны шаги (количество удаленных / перевернутых ребер).

Для проверки эквивалентности в случае улицы с двусторонним движением она довольно избыточна:

для блокировки: A ---> B, B <--- A <br> через блокировку становится A ---> B / A <--- B, а другая BLOCKED </p>

для реверса он все равно становится A ---> B / B ----> A, с одним из способов обратного

Но что я должен сделать, чтобы доказать, что они эквивалентны в случае только улиц с односторонним движением? Я пробовал тестировать в разных циклах в ориентированных графах, чтобы увидеть, может ли возврат одной арки создать больше циклов, хотя на самом деле он просто сохраняет одно и то же число или уменьшает их. Но я не знаю, как формально доказать эквивалентность двух операций.

Answer 1

Это математический вопрос (теория графов).

Схема доказательства состоит в том, чтобы отобразить p-блокировки в p-инверсии, чтобы получить тот же результат (удаление всех циклов.)

Блокировка и инверсия на улице с двусторонним движением имеют одинаковый эффект (делает улицу односторонней.)

Главное - показать, что инверсия улицы с односторонним движением не оставит цикл, который удаляется блокировкой этой улицы. Это можно увидеть, если предположить, что инверсия оставит / создаст цикл, который в противном случае заблокирован. Этот цикл находится в противоположном направлении, чем цикл, который предотвращается блокированием одной и той же улицы. Итак, у нас есть два цикла, которые встречаются на одной улице в противоположных направлениях. Эти циклы (без улицы) можно объединить в цикл, который не включает эту улицу, поэтому блок на этой улице не удалит этот цикл. Что противоречит тому, что блокировка этой улицы нужна вообще.