Моя проблема в том, что я не знаю, как обрабатывать точки сочленения / вырезать вершины в сети P2P. Как я могу сохранить сеть, , где минимум 2 и максимум 3 соединения на узел обязательны в подключенном состоянии после (добровольно) удаления точки сочленения? Поиск точки сочленения не является проблемой, есть множество ответов и объяснений по этому поводу. Но я не смог найти ничего о том, как решить проблему, упомянутую выше. Мне позволено предположить, что происходят только ожидаемые "выходы".
В худшем случае точка AP артикуляции имеет 3 подключенных компонента, в противном случае подключенных к ней. У 3 соседей AP есть еще 2 соседа. У меня было 2 идеи, которые не работают / не разрешены в соответствии с требованиями выше или могут быть слишком неэффективными:
- Подключите двух соседей AP к третьему. Это не работает, когда все 3 соседа уже имеют 2 других соединения, потому что третий сосед AP будет иметь 4 соседа (не разрешено). Более того, попытка решить эту проблему путем удаления одного из двух других ребер 3-го соседа AP может, опять же в худшем случае, пересечь проблему, только если 3-й сосед AP является точкой сочленения, со всеми вышеизложенными допущениями. Таким образом, эта идея ни к чему не приведет.
- Соедините 2 соседей AP. Найдите новое соединение для третьего соседа точки доступа к узлу в одном из двух других подключенных компонентов. Если его нет (что может произойти), разорвите соединение между любыми двумя узлами в одном из первых двух подключенных компонентов, а также убедитесь, что ни один из них не является точкой сочленения, затем подключите 3-го соседа точки доступа к любому из них. Я думаю, что это сработает, но, честно говоря, это кажется крайне неэффективным. У меня есть ощущение, что должна быть возможность использовать модифицированную версию моей первой идеи, чтобы сохранить сложность на низком уровне, но я не могу ее найти. Я знаю, что это расплывчато.
Благодарю за любую помощь!