Есть связный граф и 4 цвета. Надо найти такую раскраску, при которой никакие две смежные вершины не покрашены в один цвет.
Предположительно, граф будет задаваться матрицей смежности.

Добавлено через 2 минуты и 1 секунду
Говорят, эта задача относится к классу NP-полных задач... Т.е. нет лучшего алгоритма решения, чем просто перебор  .

Добавлено через 5 минут и 38 секунд
Если даже рассматривать перебор, то не совсем понятно, как перебирать вершины графа... Граф любой: хотя с циклами, хоть без, хоть ориентированный, хоть нет, хоть.
Сегодня судьба свела меня с алгоритмом Липтона... В нем используется представление ... эээ ... графообразных структур, которое можно попробовать задействовать. Пока хочу идти от этого...

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

Что такое алгоритм Липтона, понятия не имею. Это такое задание - использовать его?

Я понимаю, я так для краткости написала.

Нет.
Задание - пользоваться методами теории графов.

Вообще он относится к молекулярной биологии:
есть раствор в пробирке, в нем цепочки нуклеотидов ДНК;
цепочки могут соединяться в разных последовательностях и мы хотим выбрать только те, которые удовлетворяют каким-то условиям;
для этого сначала порождаются все возможные последовательности (при этом создается, так сказать, графообразное представление: каждая цепочка - вершина, связь между цепочками - ребро, ну и еще интересные особенности, которые и привлекли мое внимание; каждая последовательность рассматривается как путь в этом графе);
ну и дальше с помощью нескольких шагов (не буду утомлять тебя их описанием) отбрасываются ненужные последовательности;
смотрят, осталась хоть одна последовательность?

Короче, все равно это все не поможет, т.к. порождение всевозможных путей и выбор нужных к моей задачке отношения не имеет - возможные пути уже указаны.

Ну и там же было сказано, что задача 3-раскраски (раскраски в три цвета так, чтобы смежые вершины были разноцветными) - NP-полная, что это доказано и пока ничего не найдено... Я так понимаю, тогда 4-раскраска тем более NP-полная.

Вот в этом и была моя ошибка.
Я все время пыталась сначала понять, смежны ли вершины и раскрасить их в разные цвета; потом, если каким-то вершинам не хватило раскраски, то сделать, например, раскраску не 1-2-3, а 1-2-1... А это же по сути построение раскраски  .
А в переборе с точностью до наоборот обратный подход: сначала раскрасить как попало - хоть все вершины в один цвет  (ну понятно, что в связном графе не надо тратить силы на рассмотрение этого варианта), а потом смотреть, смежно или не смежно.
Оказывается, у меня проблемы с определением перебора  !

Спасибо, вобщем    !

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

Доказано, что невозможно с помощью циркуля и линейки разделить любой угол на три равные части. Ну и что? Прямой угол делится запросто. Это я к тому, что NP-полная задача не должна уж так сильно запугивать..

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

А если у нас не 5 вершин, а 100005? Чем нам может помочь предыдущее наблюдение?
А тем, что если мы среди 100005 найдем 5 таких, что они связаны вот так крепко, то и вся задача для 100005 неразрешима. А поиск таких завязок - это не NP-полная задача, а что-то порядка поиска циклов в графе.

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

С другой стороны, если наш граф дерево, и нет вершин, в которых сходится более чем три ребра, то решение существует всегда, и строится тривиально прямым способом, без какого бы то ни было перебора.

Осталось разобраться с циклами.

Удачи!
_______________________________________________
P.S. Подсказка.
Если у нас есть циклы, но никакие два цикла не имеют общих ребер, то задача тоже решается тривиально прямым построением. Но только если цветов больше трех.
Это замечание надо понимать и так, что из того, что для трех цветов задача NP-полная, то из этого не следует, что она такая же трудная для четырех цветов.
А здравый смысл без всякой теории графов подсказывает: чем больше цветов, тем проще задача.


Это сообщение отредактировал(а) Sefko - 14.3.2009, 20:14

Sefko

Поиск клик (и даже проверка наличия клик фиксированного размера) тоже NP-полная задача. В данном случае (для размера 5) что-то не видится алгоритма, быстрее O(N^5). Это огромное время, на большинстве практических тестов перебор отработает быстрее. Более того, как вы сами заметили, отсутствие таких клик не означает, что граф может быть раскрашен, и уж тем более не даёт самой раскраски.


Здесь вообще не понял. Ну будет у нас такая "звёздочка" - граф из 10 вершин, где все вершины 2..10 смежны вершине 1 и только ей. В вершине 1 "сходятся" 9 рёбер, однако этот граф можно раскрасить в 2 цвета.


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

Sefko
Кстати, цитата из авторитетной книги "Вычислительные машины и труднорешаемые задачи" Гэри и Джонсона:



Т.н. "здравый смысл" много чего подсказывает (например, мне подсказывает, что задача о гамильтоновом цикле не должна бы быть сильно сложнее задачи о эйлеровом цикле), но в математике, и особенно в теории сложности, доверяться ему просто глупо.

А тут и понимать особо нечего. Просто не стоит писать якобы серьезные сообщения наспех. Это кирпич в мой огород. Но удалять сообщение (методом затирки) не буду. Пусть висит. Другим наука.

 Конечно.
Когда я говорила "как попало", то я больше думала не об этой конкретной задаче, а о переборе в принципе. Понятно, что при переборе нужно исключать заведомо неподходящие варианты и что это очень желательная составная часть перебора.
(рада тебя видеть  
ты все так же верен своему желанию (пере)делать все Рационально, Правильно, Экономично    ; только для того, чтобы это желание реже усаживало тебя переписывать чужое творение, я буду делать нормальные программы)

Благодарим за желание помочь   !

Замечательная цитата    !

Вобщем я начинаю представлять, как все это будет выглядеть  .

Граф можно задавать любым удобным способом. Нам будет удобен тот, где можно максимально быстро и просто определить, смежны вершины с номерами i и j или нет.
Имхо "быстро и просто" - это м-а смежности: если [i][j] и [j][i] - нули, то вершины не смежны; иначе - смежны.


Теперь непосредственно перебор (с почти правильными исключениями  ):

закрасили вершину i
смотрим на i-ые строку и столбец м-ы смежности (смотрим элементы с номерами [i][j] и [j][i], где 0<=j<i - зачем проверять на смежность еще не закрашенное?)
    увидели не смежность - перешли на уровень глубже (закрасили вершину i+1, ...)
    иначе - проверили вершины i и j на совпадение цвета
        увидели не совпадение - перешли на уровень глубже (закрасили вершину i+1, ...)
        иначе - проверили, есть ли неиспользованные цвета для i
                есть - поднялись обратно и перекрасили вершину i
                нет - поднялись, поднялись и перекрасили i-1

Добавлено через 2 минуты и 51 секунду
Какая-то рекурсия получается... Да еще и не исключены симметричные варианты: 4-3-1-3, 4-2-1-2, 3-2-1-2, 1-4-3-4, ... .

KasMP
В 4 цвета можно раскрасить плоские графы, т.е. те которые можно нарисовать на плоскости без пересечения рёбер.

Алгоритм для раскраски логичнее (да и лучше) взять готовый. Наиболее известная книга по алгоритмам теории графов 
Н. Кристофедес, "Теория графов. Алгоритмический подход."
Там много алгоритмов по раскраскам. Можете сначала почитать параграф в этой книге, а затем найти где-нибудь в Интернете приглянувшийся запрограммированный алгоритм.


Это сообщение отредактировал(а) nworm - 17.3.2009, 17:56

А не плоские, я так понимаю, иногда можно, иногда - нет?

Спасибо  !Теперь знаю, что читать  !

Нет, вот это я буду делать уже сама  ...
(тем более, что результат надо еще нарисовать через API-функции  )

Добавлено @ 18:13

Целая глава про раскраски  !

Это сообщение отредактировал(а) KasMP - 17.3.2009, 18:14

KasMP

Вроде всё правильно. Самая что ни на есть рекурсия.


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

Кстати, какие всё-таки ограничения на размер графа? Может, meet-in-the-middle с динамическим программированием будет удобно применить.

Особенно правилен перебор "симметричных" вариантов - цвета-то разные, а суть одинаковая:
4-3-1-3, 4-2-1-2, 3-2-1-2, 1-4-3-4, ... . 

4-3-1-3 читается как "вершина 1 цвета 4, вершина 2 цвета 3, в3 цвета 1, в4 цвета 3"
4-2-1-2 читается как "в1 цвета 4, в2 цвета 2, в3 цвета 1, в4 цвета 2"

Как от них избавиться??

Рекурсия, да  .
Есть мнение, что рекурсией можно пользоваться тогда, когда нужна наглядность, маленькое время написания и простота самого процесса написания, а производительность некритична (и что вообще рекурсию используют неумеющие программировать люди); а нормальные программы лучше писать без рекурсии.
Поэтому мне не нравится рекурсия.

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

Почему  ?

Ну, понятно, что для проверки больше 20-30 никто не возьмет... Но для порядка пусть их будет 1024    .

Это сообщение отредактировал(а) KasMP - 17.3.2009, 22:31

Предполагаю хранить текущую раскраску в одномерном массиве размерности n: a[i] = {0, 1, ... 4}, 0 <= i <= n-1 .
Вроде логично  (да и вообще по-другому сложно придумать  ).

Можно a[i] сделать не каким-то целочисленным, а символьным - зачем занимать ненужные байты? (да и перепрыгивать через 1 байт легче, чем через 2 или 4)
Если a[i] - символ, то получается что-то типа битовой маски, только не из {0, 1}, а из {0, ..., 4}. Интересно  .

Это сообщение отредактировал(а) KasMP - 17.3.2009, 22:53