ВИС помогите срочно
В графе рёбрами соединены вершины 1 и 2, 2 и 3, 3 и 1, 4 и 3. Укажите ребро, убрав которое, нельзя превратить граф в дерево. В ответе укажите ребро, записав вершины, которые его соединяют.
Только авторизированные пользователи могут оставлять свои ответы
Дата
Популярность
Чтобы граф можно было превратить в дерево, в нём не должно быть циклов.
В данном графе есть цикл, образованный вершинами 1, 2 и 3 (1-2-3-1).
Чтобы разорвать этот цикл и получить дерево, нужно убрать любое ребро из этого цикла.
Таким образом, ответом может быть любое из следующих ребер:
• 1 2
• 2 3
• 3 1
Удаление ребра 4 3 не разорвет цикл и граф не станет деревом.