Опитвам се да структурирам ефективен алгоритъмнеподходяща графика и край e (u, v) и решава дали ръбът принадлежи на някой цикъл в графиката, но не и на всички цикли! Моят подход е да извадя ръба (u, v) от графиката и да стартирате BFS, за да видите дали v все още е достъпна от u. Ако да, тогава оригиналната графика има цикъл, съдържащ e, в противен случай няма. Но аз не съм толкова сигурен как да ощипвам алгоритъма, че ще реши дали ръбът не принадлежи на всички цикли на графиката.
Отговори:
1 за отговор № 1Неориентираната графика може да съдържа ръб, който принадлежи на всичките си графи за цикли само ако тази графика има само един цикъл.
Нека разгледаме един пример: Edge (2,3) принадлежи към два цикъла, но винаги можете да намерите трети цикъл, към който не принадлежи такъв край.
След като проверите дали ръбът принадлежинякой цикъл, можете да проверите дали това е единственият цикъл в графиката, като премахнете този край и проверите дали намалената графика изобщо има цикли. Благодарение на @nomanpouigt за това.