|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Timur Vafin 2:5020/400 11 Dec 2002 23:59:08
To : Yurij Zabelyshynskij
Subject : Re: Построить граф
--------------------------------------------------------------------------------
Мир вертится, коннект нормальный, а посему приветствую тебя, Yurij
Wed Dec 11 2002 19:14, Yurij Zabelyshynskij wrote to Timur Vafin:
>> Зная n>=3, число вершин, требуется построить граф,
>> не содержащий циклов длиной 3 и такой, что степень
>> всех вершин равна 3.
>> Есть предположение, что для нечетных n, такого графа
>> построить нельзя.
YZ> В любом графе количество вершин с нечетной степенью должно быть четно,
YZ> так что действительно нельзя :)
Это что за теорема такая. Hа кого ссылаться?
YZ> При n=2 или 4 тоже, конечно, нельзя.
Почему нельзя при 4? Берем пару - соединяем тремя ребрами и все. Берем другую
пару и т.д.
YZ> А при четном n=2k>4 можно разбить вершины на 2 группы: (x1, x2, ...,
YZ> xk) и (y1, y2, ..., yk), и провести ребра
YZ> x_i - y_i
YZ> x_i - y_i+1
YZ> x_i - y_i+2,
YZ> где i+1, i+2 берется по модулю k.
Всё будет хорошо...
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
