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


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yurij Zabelyshynskij                 2:5020/400     11 Dec 2002  20:14:01
 To : Timur Vafin
 Subject : Re: Построить граф
 -------------------------------------------------------------------------------- 
 
 Hi, Timur.
 Timur Vafin wrote
 
 > Зная n>=3, число вершин, требуется построить граф,
 > не содержащий циклов длиной 3 и такой, что степень
 > всех вершин равна 3.
 > Есть предположение, что для нечетных n, такого графа
 > построить нельзя.
 
 В любом графе количество вершин с нечетной степенью должно быть четно,
 так что действительно нельзя :)
 При n=2 или 4 тоже, конечно, нельзя.
 А при четном n=2k>4 можно разбить вершины на 2 группы: (x1, x2, ...,
 xk) и (y1, y2, ..., yk), и провести ребра
 x_i - y_i
 x_i - y_i+1
 x_i - y_i+2,
 
 где i+1, i+2 берется по модулю k.
 --
 WBR, Yura.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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

 Тема:    Автор:    Дата:  
 Построить граф   Timur Vafin   10 Dec 2002 19:02:01 
 Re: Построить граф   Yurij Zabelyshynskij   11 Dec 2002 20:14:01 
 Re: Построить граф   Timur Vafin   11 Dec 2002 23:59:08 
 Re: Построить граф   Yurij Zabelyshynskij   12 Dec 2002 01:11:28 
 Re: Построить граф   Dmitry Statyvka   12 Dec 2002 15:55:55 
Архивное /ru.algorithms/657786bb384f.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional