ВИС помогите срочно

Question

ВИС помогите срочно

FLinker Ученик (205), открыт 1 неделю назад

В графе рёбрами соединены вершины 1 и 2, 2 и 3, 3 и 1, 4 и 3. Укажите ребро, убрав которое, нельзя превратить граф в дерево. В ответе укажите ребро, записав вершины, которые его соединяют.

Answer 1

Чтобы граф можно было превратить в дерево, в нём не должно быть циклов.

В данном графе есть цикл, образованный вершинами 1, 2 и 3 (1-2-3-1).

Чтобы разорвать этот цикл и получить дерево, нужно убрать любое ребро из этого цикла.

Таким образом, ответом может быть любое из следующих ребер:

• 1 2
• 2 3
• 3 1

Удаление ребра 4 3 не разорвет цикл и граф не станет деревом.