Конкурс Изящные Графы

[bin]

Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф. На конкурсе Intel® Threading Challenge 2008 (о котором я недавно упоминал в другой теме) одно из заданий было на такие графы, может, в архивах интеловских сайтов сохранились обсуждения и тексты программ-лидеров того конкурса. Желаю успехов!

[dimkadimon]

bin в сообщении #769348 писал(а):

Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф. На конкурсе Intel® Threading Challenge 2008 (о котором я недавно упоминал в другой теме) одно из заданий было на такие графы, может, в архивах интеловских сайтов сохранились обсуждения и тексты программ-лидеров того конкурса. Желаю успехов!

Спасибо за уточнение. А вы можете дать ссылки?

[whitefox]

dimkadimon в сообщении #768683 писал(а):

Вот у нас линейка (а1, а2, ..., а8, а9), мы соединим а1 и а9. Какое теперь растояние от а9 до а1?

Метка $a_1$ имеет значение $0$, а метка $a_9$ имеет значение $\mathrm L$. Теперь свернём линейку в кольцо, совместив метки $a_1$ и $a_9$, расстояние от $a_1$ до $a_9$ равно $a_9-a_1=(\mathrm L - 0)\bmod \mathrm L=0$, а также $a_1-a_9=(0-\mathrm L)\bmod \mathrm L=0$.
В общем же случае расстояние между двумя точками на циклической линейке будет иметь два значения $d$ и $\mathrm L-d$. Именно по этому я писал

whitefox в сообщении #768601 писал(а):

Очевидно, что всякая полная линейка одновременно является и полной циклической линейкой. Обратное, скорее всего, не верно.

Scryer в сообщении #768695 писал(а):

I assumed he meant that each pair now has either one or two differences. For example if a1=0 and a9=9, this pair covers differences {1,9}: 9 in the usual direction, and 1 in the new direction.

Именно это я и имел ввиду

-- 30 сен 2013, 21:39 --

bin в сообщении #769348 писал(а):

Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф.

Цитата:

graceful [ˈgreɪsfʊl]
/прилагательное/

1. изящный, стройный, элегантный
   (elegant, slender)
   graceful art — изящное искусство
   
2. грациозный, благодатный
   (gracious)
   graceful dances — грациозные танцы

Насколько я понимаю, в русском языке перевод этого термина ещё не устоялся. Имхо, перевод "изящный граф" лучше передаёт суть понятия.

[bin]

dimkadimon в сообщении #769361 писал(а):

Спасибо за уточнение. А вы можете дать ссылки?

Посмотрите в Википедии (рувики) статью: Intel Software Network - там ссылки на сайты, где искать. Они менялись и точных ссылок у меня нет - если не найдете, но очень нужно, сообщите - посмотрю свои архивы.

-- Вт окт 01, 2013 03:42:43 --

whitefox в сообщении #769459 писал(а):

Насколько я понимаю, в русском языке перевод этого термина ещё не устоялся. Имхо, перевод "изящный граф" лучше передаёт суть понятия.

ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять? Чисто практически люди набирают поиск по сетке "Изящные Графы" и получают почти ничего, а в терминах Зыкова м.б. что-то и найдут... Но м.б. Вы знаете другую солидную книгу с термином "Изящные Графы"?

whitefox

(Оффтоп)

Все еще жду Ваших замечаний по изоморфизму графов

[dimkadimon]

Значит на даный момент мы не можем обойти линейки Wichmann. Мы даже не можем сравняться с ними (для N>14). А как насчёт хороших приближений? Предлагаю небольшой неофициальный конкурс без призов просто для интереса. Задача найти самые лучшие не-Wichmann линейки для N=24, 25, 26, 27 и 28. Я специально выбрал эти значения N чтобы они никак не повлияли на настоящий конкурс.

Вот мои лучшие результаты:

N=24, Wichmann=198
191: 0, 1, 2, 11, 20, 22, 29, 31, 40, 57, 74, 91, 108, 125, 142, 159, 167, 175, 178, 183, 186, 189, 190, 191
191: 0, 1, 2, 3, 8, 16, 24, 32, 40, 57, 74, 91, 108, 125, 142, 151, 160, 169, 178, 187, 188, 189, 190, 191

N=25, Wichmann=213
207: 0, 2, 4, 13, 17, 22, 26, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 186, 193, 199, 200, 203, 205, 206, 207

N=26, Wichmann=232
220: 0, 1, 2, 3, 4, 5, 6, 7, 97, 103, 109, 118, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 206, 213, 220

N=27, Wichmann=251
241: 0, 1, 2, 3, 4, 8, 16, 24, 32, 40, 57, 74, 91, 108, 125, 142, 159, 176, 193, 202, 211, 220, 229, 238, 239, 240, 241

N=28, Wichmann=270
259: 0, 1, 2, 3, 4, 13, 22, 31, 40, 57, 74, 91, 108, 125, 142, 159, 176, 193, 210, 227, 235, 243, 251, 255, 256, 257, 258, 259

[whitefox]

(bin)

bin в сообщении #769571 писал(а):

ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять?

Основания следующие:

• Тот кто пожелает ознакомиться с теорией графов по Зыкову, скорее всего, скачает из сети его издание 1987 года (просто по причине их подавляющего численного превосходства), где нет ни грациозных ни изящных графов, а потому зыковская версия перевода ему не будет знакома;
• Тот кто пожелает писать на русском о теории graceful graphs, скорее всего, переведёт этот термин как "изящные графы", если не знаком с последним изданием Зыкова, например http://np-soft.ru/npproject/projects/graphs/graceful/index.htm

P.S. Возможно я ещё вернусь к теме изоморфизма графов, она довольно интересна, но сейчас её вытеснили другие задачи, надеюсь временно

[dimkadimon]

Друзья, интересные новости. Я нашёл патерн очень похожий на Wichmann, который всегда даёт результаты на один меньше. Я его называю near-Wichmann:

W'(r,s) = 1:r, (r+1):1, (2r+1):(r+1), (4r+3):s, (2r+2):r, 1:r

[Pavlovsky]

Уже было

dmd в сообщении #767266 писал(а):

Интересно, что патерн 1^r, r+1, (2r+1)^(r+1), (4r+3)^s, (2r+2)^r, 1^r тоже работает, только все максимумы на единичку меньше получаются.

[bin]

(whitefox)

whitefox в сообщении #769593 писал(а):

bin в сообщении #769571 писал(а):

ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять?

Основания следующие:

• Тот кто пожелает ознакомиться с теорией графов по Зыкову, скорее всего, скачает из сети его издание 1987 года (просто по причине их подавляющего численного превосходства), где нет ни грациозных ни изящных графов, а потому зыковская версия перевода ему не будет знакома;
• Тот кто пожелает писать на русском о теории graceful graphs, скорее всего, переведёт этот термин как "изящные графы", если не знаком с последним изданием Зыкова, например http://np-soft.ru/npproject/projects/graphs/graceful/index.htm

Это напоминает казус в рувики, где line graphs перевели как линейные графы (уже исправлено) Последнее издание Зыкова найти не труднее, чем предыдущее. Оно сильно полнее. Общеизвестно правило, что если переиздание нестереотипное, то руководствоваться нужно этим переизданием. Прогресс все же движется, и новые книги исправляют недочеты предыдущих. Может, найдутся оригиналы, которые будут учить основы по арифметике Магницкого, но уверен, таких будет меньшинство. Стоит также отметить давно известный подход, согласно которому учебников по одной дисциплине нужно несколько. Например, этот подход широко используется в МГУ. Тот, кто пожелает ознакомиться с теорией графов, прочтет скорее всего не одну книгу, и вполне возможно, что и Зыков (в полном издании) окажется в числе этих книг.

whitefox в сообщении #769593 писал(а):

P.S. Возможно я ещё вернусь к теме изоморфизма графов, она довольно интересна, но сейчас её вытеснили другие задачи, надеюсь временно

Вот и все так говорят. Лучше решать безобидные задачи, чем страшные-ужасные открытые проблемы. Согласиться с моим доказательством боязно, а опровергнуть не получается

[Pavlovsky]

Изучаю статью
Л. Редей (Сегед) и А. Реньи (Будапешт) О представлении чисел 1,2,...,N посредством разностей
http://www.mathnet.ru/links/8a122709abb ... sm5985.pdf

В ней доказывается оценка $\sqrt{2+\frac{4}{3\pi}}\le \lim \limits_{L \to \infty} {\frac{N}{\sqrt{L}}}$.

Возникли проблемы с пониманием доказательства. Может кто поможет? У меня радиотехническое образование, где комплексные числа активно используются. Но с удивлением понял, что у меня огромные пробелы в знании комплексных чисел.

Не понимаю как получилось неравенство (17). У меня получается странная формула:
$e^{ib_rx}e^{ib_sx}=e^{i(b_r-b_s)x}$. Откуда взялся минус? Рациональное(действительное, целочисленное) сознание говорит, что должен быть плюс.

К тому же не понимаю элементарной вещи, что означает сравнение комплексного числа с нулем:
$a+ib \ge 0$??

Так же не понимаю откуда следует, что
$e^{ib_rx} \le 1$

Главное не могу понять "физического смысла" доказательства. Использование комплексных чисел для доказательств в теории чисел (привет от Дирихле), для меня выглядит каким то шулерским фокусом.

[Xaositect]

Pavlovsky в сообщении #771431 писал(а):

Не понимаю как получилось неравенство (17).

Из равенств $|f(x)|^2 = f(x)\overline{f(x)}$ и $\overline{e^{ibt}} = e^{-ibt}$

Pavlovsky в сообщении #771431 писал(а):

К тому же не понимаю элементарной вещи, что означает сравнение комплексного числа с нулем:
$a+ib \ge 0$??

$|f(x)|^2$ по определению модуля действительное неотрицательное число.

[Pavlovsky]

Xaositect

Спасибо, небольшое прояснение наступило. Может вы дадите ссылку, где описаны эти аспекты комплексных чисел. Но чтобы материал сильно не напрягал умственные способности.

[svb]

Определение 1. Множеством разностей некоторого конечного множества чисел $B$ называется множество всевозможных $x-y$, где $x \in B$ , $y \in B$ . Обозначим это множество так $def(B)$.

Определение 2. Если $H = def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$ .

В дальнейшем нас будут интересовать базы множества $H = \left( {0,1,...,L} \right)$. Эти базы можно задавать в виде набора чисел, но часто их удобно задавать в виде набора разностей соседних чисел базы после упорядочивания чисел базы по возрастанию. Например,

${\rm .1}{\rm .2}{\rm .3}{\rm .7}{\rm .7}{\rm .7}{\rm .4}{\rm .4}{\rm .1}{\rm .} $

это база $\left( {{\rm 0}{\rm ,1}{\rm ,3}{\rm ,6}{\rm ,13}{\rm ,20}{\rm ,27}{\rm ,31}{\rm ,33}{\rm ,36}} \right)$ для множества $\left( {0,1,...,36} \right) $

Теорема 1. Пусть база $.a_1 .a_2 ....a_k .x/s.b_1 ....b_m .$ множества $H_s = \left( {0,1,...,L} \right)$ удовлетворяет условиям:
1. $x > a_i$ , $x > b_i$ ,
2. $H_s = def\left( {.a_1 ....a_k .x/s.} \right)\bigcup {def\left( {.x/s.b_1 ....b_m .} \right)}$,
тогда множество $.a_1 .a_2 ....a_k .x/\left( {s + 1} \right).b_1 ....b_m .$ является базой множества $H_{s + 1} = \left( {0,1,...,L + x} \right)$. Кроме того $\left( {0,1,...,x - 1} \right) \in def\left( {.a_1 ....a_k .} \right)\bigcup {def\left( {.b_1 ....b_m .} \right)} $

Доказательство.
Последнее утверждение очевидно, т.к. $x > x - 1$.
При добавлении числа $x$ в базу все прежние представления чисел меньших или равных $L$ сохраняются, что следует из условия 2. Любое число, большее $L$ , входит в одно из множеств $def\left( {.a_1 ....a_k .x/\left( {s + 1} \right).} \right)$ или $def\left( {.x/\left( {s + 1} \right).b_1 ....b_m .} \right)$. Таким образом, для любого $p > s$ множество $.a_1 .a_2 ....a_k .x/p.b_1 ....b_m .$ также является базой.

Дополнительно приведу пример линейки $.1/3r-2.r.5r/s.1/r-1.3r.1/r.$, которая хуже линейки Вихмана.

Последовательность $s$ элементов $a$ в тексте обозначена через $a/s$

[whitefox]

svb в сообщении #777148 писал(а):

Определение 2. Если $H = def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$

Имхо, так:
Определение 2. Если $H \subseteq def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$

[svb]

whitefox в сообщении #777297 писал(а):

Имхо, так:
Определение 2. Если $H \subseteq def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$

Спасибо. Согласен.