Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Интересненькая задачка   Artur Mogozov   20 Mar 2003 20:02:19 
 Re: Интересненькая задачка   Mike Girkin   20 Mar 2003 23:05:54 
 Интересненькая задачка   Anthone Tikhonov   21 Mar 2003 15:32:24 
 Интересненькая задачка   Artur Mogozov   21 Mar 2003 23:47:24 
Архивное /ru.algorithms/164723e7a11d7.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional