На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Еще геом. задачка (Кубик-II)
    Возьмем банальный трехмерный кубик.
    0-мерными гранями будем называть его вершины.
    1-мерными гранями будем называть его ребра
    2-мерными гранями называть его плоские квадратные грани

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

    Для трехмерного кубика все просто: вершины (0-грани) можно красить в 1 цвет, т.к., они друг друга не касаются. для ребер (1-грани) надо 3 краски (меньше точно нельзя, т.к., по три ребра сходятся в вершине, больше не надо, легко проверить), для сторон (2-грани) тоже надо три краски.

    Теперь задача: сколько надо красок для раскраски k-граней N-мерного кубика?
    Сообщение отредактировано: Visitor -
      уж больно задачу о 4 красках напоминает wink.gif
        Та была на плоскости, даже не на торе smile.gif Тут веселее smile.gif
          я к тому что ее вроде влоб решили smile.gif

            А... Ну так там еще и доказательство до сих пор не проверено, т.к., человек его проверить не в состоянии smile.gif Там ведь все возможные неэквивалентные плоские графы рассматривались smile.gif

            Здесь граф более "регулярный".
              что то давольно просто получается:

              0k = 1 always
              1k = N always ( думаю больше не понадобится smile.gif, так как все симетрично, если углы замалевать, то остальные по инерции сойдутся smile.gif )

              (N-1)k = N always ( чето хорошо начал на бумаге рисовать эти Н-угольники smile.gif, если правильно рисую, то с прибавлением каждого измерения, N-1 измерение, остается таким же как и до этого рисовал N-1, по отношению к N-2 )

              а вот с 2k для 4 мерного пришлось повозиться, но пришел к выводу что все таки будет 4 краски,
              а так как они все растут как то пропорционально, то можно сказать что от 2k до (N-1)k, будет N красок.
                С промежуточными посложнее будет... Не N.

                И вот еще более общая задачка сразу: k-грани N-мерного куба считаем соседними, если они имеют общую l-мерную сторону (l-грань). 0<l<k<N

                Сколько надо красок в етом случае?

                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0295 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:39 GMT ]