Необходимо решить две задачки — решение надо в Visual C представить.
В программировании я не шарю и поэтому прошу помочь.
Мне кажется они достаточно стандартные.

1. задан граф — не дерево. проверить, можно ли превратить его в дерево удалением одной вершины вместе с ее ребрами.

2. задана система двусторонних дорог. найти замкнутый путь длинной не более T, проходящий через каждую дорогу ровно один раз.

Здравствуйте, borofff, Вы писали:

B>Необходимо решить две задачки — решение надо в Visual C представить.
B>В программировании я не шарю и поэтому прошу помочь.
B>Мне кажется они достаточно стандартные.

B>1. задан граф — не дерево. проверить, можно ли превратить его в дерево удалением одной вершины вместе с ее ребрами.

B>2. задана система двусторонних дорог. найти замкнутый путь длинной не более T, проходящий через каждую дорогу ровно один раз.

Ище все про поиски в глубину и ширину, и все что в них связано с выявлением циклов.

borofff:

> Необходимо решить две задачки — решение надо в Visual C представить.

Ну писать тебе прожку врядли кто-то будет — весна!

> 1. задан граф — не дерево. проверить, можно ли превратить его в дерево
> удалением одной вершины вместе с ее ребрами.

Критерий дерева: количество рёбер на 1 меньше количества вершин.
Берёшь вершину, "удаляешь" её, смотришь, выполняется ли критерий. Так с
каждой.

> 2. задана система двусторонних дорог. найти замкнутый путь длинной не
> более T, проходящий через каждую дорогу ровно один раз.

Алгоритм без ограничения на длину пути называется "Алгоритм построения
эйлерова цикла". С твоим ограничением не понятно: если я построил твой путь,
то его длина равна суммарной длине всех рёбер, — причём тут T?

Здравствуйте, dikun, Вы писали:

D>borofff:

>> Необходимо решить две задачки — решение надо в Visual C представить.

D>Ну писать тебе прожку врядли кто-то будет — весна!

>> 1. задан граф — не дерево. проверить, можно ли превратить его в дерево
>> удалением одной вершины вместе с ее ребрами.

D>Критерий дерева: количество рёбер на 1 меньше количества вершин.
Небольшая поправка: причем граф должен оставаться связным.
D>Берёшь вершину, "удаляешь" её, смотришь, выполняется ли критерий. Так с
D>каждой.

>> 2. задана система двусторонних дорог. найти замкнутый путь длинной не
>> более T, проходящий через каждую дорогу ровно один раз.

D>Алгоритм без ограничения на длину пути называется "Алгоритм построения
D>эйлерова цикла". С твоим ограничением не понятно: если я построил твой путь,
D>то его длина равна суммарной длине всех рёбер, — причём тут T?

Nev0:

D>>Критерий дерева: количество рёбер на 1 меньше количества вершин.
> Небольшая поправка: причем граф должен оставаться связным.

Да, Вы правы — я поспешил.
Добавлю. Связность проверяется поиском в ширину/глубину, как подсказал
mkopachev.

Всем большое спасибо за советы.

Про весну это точно! Код пишется все медленнее, а мозговая активность
перемещается в область половых органов.