Думая над Роминой задачкой — давайте перенумеруем вершины гиперкуба двоичными числами, так что цифры каждого двоичного числа будут координатами вершины. Можно ли обойти гиперкуб с помощью двух последовательных кодов Грея — решил применить метод грубой силы.
Взял вот такой гиперкуб:
Сгенерировал двадцать четыре подстановки четырех осей и применил их к коду Грея. Исключая тождественную подстановку, всего получилось двадцать три пары кодов. Ни одно применение пары кодов не дало гиперкуба:
Такое впечатление, что и тремя кодами гиперкуб не нарисовать — только четырьмя.
Походу узнал, что у Математики баг при экспорте в gif. Собственно из анимации там работает только avi и swf. Любимый Ромой svg работает, да.
Взял вот такой гиперкуб:
Походу узнал, что у Математики баг при экспорте в gif. Собственно из анимации там работает только avi и swf. Любимый Ромой svg работает, да.
Мм... Я не так рассуждал. Берем один код Грея. После первого обхода зарисована ровно половина вершин. Далее, для каждой вершины есть два инцидентных ребра. Поэтому следующий обход определен почти однозначно, с точностью до того, по какому ребру двигать из нулевой вершины. И тут быстро выясняется, что этот обход слишком мал и не прочерчивает все оставшиеся ребра.
ОтветитьУдалитьПоэтому более показательно было бы наоборот, стереть все ребра, по которым прошел за первый раз и убедиться, что граф стал несвязным. В связи с этих задача: как нарисовать одним росчерком 2n-мерный куб? То, что нарисовать можно --- очевидно, конечно.
Упс, два предложения "После первого ... инцидентных ребра." следует читать как "После первого обхода зарисована ровно половина ребер. Далее, для каждой вершины есть два непрорисованных инцидентных ребра."
ОтветитьУдалитьНу я ж написал грубой силой. Просто проходов по коду Грея много — в зависимости от того, что ты считаешь за оси (x,y,z,u).
ОтветитьУдалитьНашел прикольное утверждение: Traversing the polyhedron vertices of an n-dimensional hypercube in Gray code order produces a generator for the n-dimensional Hilbert curve.
ОтветитьУдалитьКак я сейчас только прочитал As a generalization of the Königsberg bridge problem, Euler showed (without proof) that a connected graph has an Eulerian cycle iff it has no graph vertices of odd degree.
ОтветитьУдалитьНа самом деле можно иметь даже две вершины нечетного порядка.
Не, cycle --- замкнутый обход.
ОтветитьУдалитьДобрый день! Ваш блог участвует в рейтинге научных блогов. Голосование идет до 28 февраля.
ОтветитьУдалитьhttp://www.strf.ru/material.aspx?CatalogId=222&d_no=35195
Вот глупость какая. Написал, попросил чтоб убрали.
ОтветитьУдалить