Re: Интересненькая задачка

From

Mike Girkin (2:5055/177.22)

To

Artur Mogozov ()

Date

2003-03-20T22:05:54Z

Area

RU.ALGORITHMS

    Да пребудет с тобой тьма, Artur !

20 Мар 03 19:02, Artur Mogozov закинул письмецо для All:
 AM>  Нужно раскрасить все ребра графа в два цвета так, чтобы у каждой
 AM> вершины были хотя бы два ребра разного цвета, инцидентных ей. Если
 AM> степень вершины 1, то раскраска инцидентного ей ребра не имеет
 AM> значения.
И в чем здесь проблема? Помоему решение задачи заключается в поиске остовного
дерева графа, (причем вершины со степенью 1 вообще можно отбросить сначала).
Красим остовное дерево по условию, остальной граф красим одним цветом (любым).
Если такое невозможно (а бывает вообще, что невозможно?...подумаю на досуге)
берем другое остовное дерево, и те же операции.

Только сначала нужно подумать(доказать), что такую раскраску допускает любой
граф(сомнения меня берут).

                                       Тьма за нас. Mike .

... Плохо то pешение, котоpое не может быть изменено. (Пyблилий Сиp)
--- GoldED+/W32 1.1.5-030118
 * Origin:  (2:5055/177.22)