Геометрическая \%) задачка

[Visitor]

Дан N-мерный куб.

T-Углом куба называется конструкция, состоящая из одной центральной вершины куба, и вершин, кратчайший путь до которых содержит не более T ребер. Из одной вершины куба можно попасть в другую, только пройдя по ребру, "прыгать" нельзя.

Можно ли 7-мерный куб разрезать на 1-углы так, чтобы каждая вершина куба оказались в одном из получившихся 1-углов?

Можно ли 15-мерный куб так же разрезать на 2-углы?
---
Поправил неоднозначности.

Сообщение отредактировано: Visitor - 04.11.03, 15:13

[Sazabis]

для 7 мерного куба:
если я правильно понял из 1 вершины исходит 3 ребра ?
тогда из теоремы об эйлеровом пути получаем ответ НЕТ.

для 15 мерного я не понял условие

[Visitor]

У N-мерного куба из вершины выходит N ребер.

2-угол -- совокупность центральной вершины, и всех вершин, кратчайший путь до которых состоит из не более, чем 2х ребер. Для трехмерного куба 2-угол представляет собой все вершины, кроме одной, противоположной центральной.

Сообщение отредактировано: Visitor - 04.11.03, 14:26

[Sazabis]

главное нечетно
ответ НЕТ

[Visitor]

(Разрезать на _полные_ T-углы, т.е., включающие _все_ вершины, путь до которых...)

Сообщение отредактировано: Visitor - 04.11.03, 14:23

[Visitor]

7 на 1-углы можно...
Что с 15?

[Sazabis]

1 угол это не по всем вершимам 1 раз, а это все вершины которые соединены ребром с вершиной ?

[Visitor]

1-угол, ето да/нет (нужное подчеркнуть, не понял ), все вершины, которые соединены с одной центральной вершиной путями не более чем в одно ребро + сама ета центральная вершина.

Сообщение отредактировано: Visitor - 04.11.03, 14:38

[zx1024]

Что значит: "разрезать на 1-углы"?

[zx1024]

Что значит: "разрезать на 1-углы"?

[zx1024]

Что значит: "разрезать на 1-углы"?

[Visitor]

Ето значит, например, назначить _каждой_ вершине куба номер _полного_ T-угла, в котором она содержится. Так, чтобы получилось некоторое количество (совершенно одинаковых) конструкций из вершин, обозначенных одним номером, представляющих собой T-углы. Т.е., имеющих ту центральную вершину и все возможные вершины _куба_,  путь до которых...

Сообщение отредактировано: Visitor - 04.11.03, 14:45

[Sazabis]

Цитата

Можно ли 7-мерный куб разрезать на 1-углы так, чтобы все вершины куба оказались в одном из 1-углов?

другими словами, так чтобы из одна вершина была соединена со всеми остальными ?
тогда что значит порезать ?

[Visitor]

Порезать -- удалить все ребра, которые соединяют вершины, принадлежащие разным T-углам. Тогда куб развалится на части Трехмерный куб режется на два 1-угла, получаются два куста, каждый с тремя ветками

Сообщение отредактировано: Visitor - 04.11.03, 14:54

[Sazabis]

после того как мы порезали 3х мерный куб на два 1-угла,

мы получили все вершины куба в одном из 1-углов ? или что мы получили ?
(два куста, каждый с тремя ветками - другими словами )

[Visitor]

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

[Sazabis]

<br>получили, что каждая вершина содержится в одном из полных 1-углов. не осталось вершин, которые не попали в один из  1-углов. <br>

если это то что удовлетворяет условию
то на 1-углы можно порезать все n мерные кубы
так как 1-угол съедает 3 + 1 вершину, если кол-во вершин будет кратно, а оно будет кратно 4

2-угл съедает, 6+1 (для куба посмотрел), как 15 мерный куб соеденен сейчас в голову не лезет, но возможно его 2 вершины не перехлестываются ... че хочу сказать ???
тогда возможно 9 + 1 вершин на угол, и то и другое не кратно 2^15 а значит нельзя

[Visitor]

на 1-углы нельзя порезать четырехмерный куб... да и двумерный тоже...

Сообщение отредактировано: Visitor - 04.11.03, 15:33

[zx1024]

Цитата

о на 1-углы можно порезать все n мерные кубы

при нечётном n.

[Visitor]

и пятимерный тоже нельзя.

[zx1024]

Цитата

о на 1-углы можно порезать все n мерные кубы

при нечётном n.

[zx1024]

Извиняюсь за повторы. Выясню почему - избавлюсь.

[Visitor]

Глючит кого-то... не то инет, не то форум... у меня тоже с трудом отправляется.

Сообщение отредактировано: Visitor - 04.11.03, 15:41

[Sazabis]

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

[Sazabis]

http://www1.tip.nl/\%7Et515027/hypercube.html
15 - мерный

[Visitor]

Его легко представить (и даже нарисовать ) Берем два трехмерных куба, совмещаем все их вершины, пронумеровываем все вершины. Затем один из кубов параллельным переносом сдвигаем так, чтобы его первая вершина попала в центр другого куба. Соединяем соответствующие вершины ребрами (1-1, 2-2, ...). Теперь можно начинать представлять пятимерный

[Tishaishii]

Цитата Sazabis, 04.11.03, 19:14:01

http://www1.tip.nl/\%7Et515027/hypercube.html
15 - мерный

:

Сообщение отредактировано: Tishaishii - 04.11.03, 16:37

[Sazabis]

для 3 мерного получилось так, что ни в одной вершине нет 2 1-углов, это случайность или закономерность ?, тобишь получился разрыв по ребрам.

[Visitor]

Около каждой вершины, если ее считать центральной, существует только один T-угол. Куб ведь симметричен во все стороны

Сообщение отредактировано: Visitor - 04.11.03, 16:52

[Vesper]

Хмммм. Я так понял. 1-угол для Н-мерного куба содержит Н+1 вершину, соответственно для 7-мерного их 8, следовательно просто так не отделаться ))) С другой стороны, 7-мерный куб с разбиением на 1-углы есть не что иное, как код Хэмминга с коррекцией ошибок в 1 бит (Хэмминга ли? Забыл ) А такой код.... существует, следовательно разбить можно. Для 15-мерного куба примерно тот же подход, но нужно построить код эмминга длиной 15 бит, исправляющий 2 бита.... а я не умею :'(

[Sazabis]

я хотел спросить:

у нас из вершины исходит T-угол, => конец этого T-угла будет в другой вершине. Понятно что из той вершины мы не будем строить дальше углы, но может ли в этой же вершине закончится другой T-угол ?
по другому сформулировав: исходящие ребра из той вершины уже "забиты" ?

[Visitor]

Лучше сформулировать "можно ли", как в задаче

[Visitor]

нет, T-угол не может иметь одной из крайних вершин вершину другого T-угла. Иначе как их резать

Сообщение отредактировано: Visitor - 04.11.03, 17:05

[MeG]

по матрице смежности можно 1-углы найти и проверить первый вопрос.

2-углы  в матрице смежности уже не катит, нужна другая матрица, слоёв? или какие там есть еще??

[Vesper]

Да кстати, дошло уже дома для 2-угла кол-во вершин есть C⁰_n+C¹_n+C²_n, что для 15-мерного куба есть 121, т.е. нельзя сделать полное разбиение 15-мерного куба на 2-углы.

[Sazabis]

Ну вот, до инета добрался, а задачку уже решили  

что такое это С⁰n + ... ? и как из этого 121 получилось ?

у меня вот что получилось, для N мерного куба:
 - если 2ⁿ кратно n+1, то можно порезать на 1-углы.
 - если 2ⁿ кратно n(n+1)/2 + 1, то можно порезать на 2-углы.

7 мерный режется на 1-углы, 15 мерный тоже, и похоже все 2ⁿ-1 мерные
15 мерный не режется на 2 углы, т.к. , все-таки у меня тоже 121,   не кратно 2¹⁵

2ⁿ - кол-во вершин, для n мерного куба.

но это необходимые условия, а их достаточность у меня не вышла

Сообщение отредактировано: Sazabis - 05.11.03, 07:44

[Visitor]

Решили
Для достаточности см тут: http://www.yandex.ru/yandsearch?text=\%F1\...8\%E9&stype=www
Набор вершин единичного N-мерного куба изоморфен пространству двоичных векторов длины N. Переход по ребру -- сложение с единичным вектором ортонормированного базиса -- изменение значения одного бита в векторе.

Сообщение отредактировано: Visitor - 05.11.03, 09:06