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

From

Yurij Zabelyshynskij ()

To

Timur Vafin

Date

2002-12-11T19:14:01Z

Area

RU.ALGORITHMS

From: "Yurij Zabelyshynskij" <ergo@sky.net.ua>

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)