Помогите с алгоритмом

[Sanyok]

Возможно кто-нибудь сможет помочь с алгоритмом дискретной математики. Просьба тех, кто не знает что такое графы дальше не читать. )


Итак, нужен алгоритм(!) построения эйлерова цикла. НО! Чтобы алгоритм не портил граф. Есть самый известный способ (Липский, Иванов), но в нем присутствует удаление ребра при построении. Нужен соответственно алгоритм без удалений )
Представление графа - списком ребер. Хотя можно и матрицей смежности впринципе. ) Граф - связный, неориентированный.

[2garin]

Ты программу чтоле создаёшь или для себя алгорит выбираешь?

[Sanyok]

Цитата: Сообщение от 2garin Ты программу чтоле создаёшь или для себя алгорит выбираешь?

На С++ реализовать надо алгоритм этот самый ) реализовать-то не долго, труднее найти алгоритм...

[2garin]

Как я вас понимаю
Я подумаю, если что придумаю, то отпишу...

[torrie]

тож посижу..
с графами знаком, выступал на конкурсе по ним.
с++ в вижуале ноу проблэм сэр.

[torrie]

2 стэка - a,b
ЦИКЛ:
{
берём вершину x0, идём от неё по непройденному ранее ребру, записываем вершины в a.
ЕСЛИ x последняя = a, ТО
ЦИКЛ { перекладываем вершины из a в b ПОКА не наткнемся на x последнюю } ИНАЧЕ
ЕСЛИ стэк а - пустой, ТО в стэке b лежит путь эйлерова цикла
}


Сань, проверь только выход из 2ого цикла.. а то тут на бесконечный смахивает.. либо не делай ПОКА(while, for), а чисто проверку и число операций..

[Sanyok]

Цитата: Сообщение от torrie 2 стэка - a,b ЦИКЛ: { берём вершину x0, идём от неё по непройденному ранее ребру, записываем вершины в a. ЕСЛИ x последняя = a, ТО ЦИКЛ { перекладываем вершины из a в b ПОКА не наткнемся на x последнюю } ИНАЧЕ ЕСЛИ стэк а - пустой, ТО в стэке b лежит путь эйлерова цикла }

не очень понял, как это работает, если честно )

ЦИКЛ:
{
берём вершину x0, идём от неё по непройденному ранее ребру

Ну как раз условие ЦИКЛа получается ПОКА ребёр > 0

"ЕСЛИ x последняя = a, ТО" что здесь есть "x последняя"? и имеется ввиду видимо top стека a?)

[UrVag]

Могу написать алгоритм на бэйсике

[torrie]

выбираем вершину x0
заносим эту вершину в стэк a
пока a ≠ Ø
{
x = top(a)
если есть непройденное ребро (x,y) то "проходим его" то есть просто помечаем
y заносим в а
иначе перемещаем x из а в b
}

когда а будет пустое, что в b будет лежать последовательность вершин эйлерова цикла

[Alex-19]

ну вы уманы