|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Mike Girkin 2:5055/177.22 20 Mar 2003 23:05:54 To : Artur Mogozov Subject : Re: Интересненькая задачка --------------------------------------------------------------------------------
Да пребудет с тобой тьма, Artur !
20 Мар 03 19:02, Artur Mogozov закинул письмецо для All:
AM> Hужно раскрасить все ребра графа в два цвета так, чтобы у каждой
AM> вершины были хотя бы два ребра разного цвета, инцидентных ей. Если
AM> степень вершины 1, то раскраска инцидентного ей ребра не имеет
AM> значения.
И в чем здесь проблема? Помоему решение задачи заключается в поиске остовного
дерева графа, (причем вершины со степенью 1 вообще можно отбросить сначала).
Красим остовное дерево по условию, остальной граф красим одним цветом (любым).
Если такое невозможно (а бывает вообще, что невозможно?...подумаю на досуге)
берем другое остовное дерево, и те же операции.
Только сначала нужно подумать(доказать), что такую раскраску допускает любой
граф(сомнения меня берут).
Тьма за нас. Mike .
... Плохо то pешение, котоpое не может быть изменено. (Пyблилий Сиp)
--- GoldED+/W32 1.1.5-030118
* Origin: (2:5055/177.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/164723e7a11d7.html, оценка из 5, голосов 10
|