Re: Построить граф

From

Timur Vafin ()

To

Yurij Zabelyshynskij

Date

2002-12-11T22:59:08Z

Area

RU.ALGORITHMS

From: "Timur Vafin" <tland@bip.ru>

Мир вертится, коннект нормальный, а посему приветствую тебя, Yurij

Wed Dec 11 2002 19:14, Yurij Zabelyshynskij wrote to Timur Vafin:
 >> Зная n>=3, число вершин, требуется построить граф,
 >> не содержащий циклов длиной 3 и такой, что степень
 >> всех вершин равна 3.
 >> Есть предположение, что для нечетных n, такого графа
 >> построить нельзя.
 YZ> В любом графе количество вершин с нечетной степенью должно быть четно,
 YZ> так что действительно нельзя :)

Это что за теорема такая. На кого ссылаться?

 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)