Одно направление доказательства выглядит следующим образом: если блокировка улицы отключает сеть, то сеть разделяется на две части A и B. Поскольку между ними существует только одна улица, только одно направление A-> B илиB-> A может быть реализовано, но не оба (это означает, что вы не можете добраться до перекрестка в округе A от перекрестка в округе B, если реализовано A-> B). Следовательно, блокировка улицы не должна отключать сеть.
Другое направление доказательства основано на циклах. То есть можно легко преобразовать циклы в ориентированные графы, чтобы каждый узел в нем был достигнут. Таким образом, мы должны доказать, что каждый узел действительно является частью цикла.
Поскольку это сайт программирования, я предоставлю ответ, который легко может быть реализован в программе:
Упростите задачу: не имеет значения, есть ли у нас автопетли или несколько соединений между соседними соединениями.
Убедитесь, что не имеет значения, есть ли у нас автопетли в графе: они не способствуют достижению других соединений, поэтому мы можем предположить, что таких петель нет.
Далее, поймите, что двойные, тройные, ... соединения между соединениями X и Y также не имеют значения, потому что тогда мы можем рассматривать X и Y как один сетевой компонент / район и вместо этого указать исходную проблему с районами. перекрестков. Более конкретно, эта проблема может быть решена в более простую проблему без множественных соединений между соседними узлами путем удаления этих узлов X и Y и создания нового узла Z, который связан со всеми узлами, к которым были подключены X и Y. Это можно возобновить, пока не будет нескольких соединений. Эта проблема такая же, как и в оригинале, потому что при назначении хотя бы одного направления от X до Y и хотя бы одного направления от Y до X выполняется следующее: из X мы можем достичь Y, и, следовательно, каждый узел, который был доступен из Y, можетбыть достигнутым от X, а также (и наоборот). Следовательно, нет никакой разницы между X и Y в исходной проблеме (с каждого перекрестка мы можем добраться до любого другого перекрестка в городе).
Итак, теперь мы смотрим на самоконтроль, множественные соединения-свободный граф.
В упрощенном случае:
Каждый узел должен иметь как минимум два соединения. Он не может иметь 0, тогда сеть не будет подключена. И он не может иметь 1, потому что тогда это соединение может быть заблокировано, отключив сеть.
Это означает, что соединение A должно быть подключено по крайней мере к двум другим соединениям B и C. Это означает, A, B иС связаны. Давайте назовем это подключенной группой G. У B также должно быть как минимум два соединения, одно из которых является соединением с A. Оставшееся соединение может перейти к другому соединению за пределами G. В этом случае добавьте новый узел вG и резюме для вновь добавленного узла. Так, например, B-> D, тогда G = {A, B, C, D}, вычислите D;C-> A, A-> B, B-> D используется. В конце концов, поскольку число узлов в этой сети конечно, соединение должно идти к другому узлу в G. Это означает, что действительно существует хотя бы один цикл / цикл (путь, который начинается с узла А и заканчивается узломА, используя каждое соединение не более одного раза).
Теперь этот цикл либо содержит каждый узел: в этом случае вы можете отметить, просто выбрать направление и пройти через вашу сеть, каждый узел может быть достигнут.
Или цикл содержит толькочасть всей сети. В этом случае снова упростим: удалите все узлы, которые содержатся в пути цикла (пусть это будет группа P), затем создайте новый узел Z со всеми соединениями из исходной группы P, которые выходят за пределы P.
Пример: A-> B-> C-> D-> E-> A было обнаружено, что это путь цикла. Тогда P = {A, B, C, D, E}. Удалить все узлы A, B, C, D, E. Создайте новый узел Z. В исходной сети A <-> F и A <-> C также были соединениями. Затем необходимо добавить Z <-> F, так как F не содержится в P, но Z <-> C не следует добавлять, поскольку C содержится в P (и был удален).
Оставшаяся сеть сообщаетта же исходная проблема по тем же причинам, что и указанная выше: это верно, поскольку каждый узел A, B, C, D, E (в P) может быть достигнут из любого другого узла A, B, C, D, E, поэтому он ненезависимо от того, к какому узлу A, B, C, D, E подключен узел F (за пределами P).
Поскольку число узлов в оставшейся сети уменьшается из-за этого и является конечным, эта процедураможет быть сделано, пока каждый узел не будет достигнут, и, следовательно, проблема решена.