Я думаю, что мне удалось выяснить что-то вроде того, что авторы намеревались.Я бы не назвал это простым.
Пусть G - граф, а H - изначально пустой 2-3 подграф G. Алгоритм имеет семейное сходство с обходом в глубину, но я бы не сталне называй это так.Начиная с произвольного узла, мы ходим по графику, помещая шаги в стек.Всякий раз, когда мы обнаруживаем, что стек содержит форму пути / цикла / сигмы, которая будет составлять 2-3 суперграфа H, мы перемещаем его из стека в H и продолжаем.Когда уже невозможно найти такую форму, H максимальна, и мы закончили.
Более подробно, стек обычно состоит из пути, не имеющего узлов степени 3 в H. Курсоррасположен на одном конце пути.С каждым шагом мы рассматриваем следующий край инцидента до конца.Если единственным инцидентным фронтом является тот, по которому мы прибыли, мы удаляем его как из G, так и из стека и перемещаем конец назад на один.В противном случае мы можем расширить путь по некоторому ребру e.Если другая конечная точка e имеет степень 3 в H, мы удаляем e из G и рассматриваем следующее ребро, инцидентное концу.Если другая конечная точка e имеет степень 2 в H, но в данный момент не находится в стеке, то мы закрепили этот конец.Если другой конец тоже привязан, то добавьте путь стека к H и продолжайте.В противном случае переместите курсор на другой конец стека, перевернув его.В последнем случае стек возвращается к самому себе.Затем мы можем извлечь путь / цикл / сигму и продолжать.
Печатая это на мобильном телефоне, извините за краткое описание.Может быть, я найду время для ее реализации.