|
|
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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/657786bb384f.html, оценка из 5, голосов 10
|