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

From

Yurij Zabelyshynskij ()

To

Timur Vafin

Date

2002-12-12T00:11:28Z

Area

RU.ALGORITHMS

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

Hi, Timur.
Timur Vafin wrote
>> В любом графе количество вершин с нечетной степенью
>> должно быть четно, так что действительно нельзя :)

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

На любой курс теории графов. Впрочем, это доказывается очень просто:
если мы сложим все степени вершин, то каждое ребро посчитается дважды,
значит, эта сумма - четная, значит, нечетных слагаемых в ней четное
количество.

> Почему нельзя при 4? Берем пару - соединяем тремя
> ребрами и все.  Берем другую пару и т.д.

Я считал, что между 2 вершинами не больше 1 ребра. Иначе ты прав, это
тривиально.
--
WBR, Yura.

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)