Задача на графы

Тема в разделе "WASM.A&O", создана пользователем GL, 30 янв 2011.

  1. GL

    GL New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2010
    Сообщения:
    5
    Имеется задача:

    Может кто-нибудь разъяснить, что подразумевается под фразой "граф K-раскрашиваем..."? Речь идет о реберной раскраске?
     
  2. deLight

    deLight New Member

    Публикаций:
    0
    Регистрация:
    26 май 2008
    Сообщения:
    879
    Граф K-раскрашиваем, если существует K-раскраска такая, что никакие две вершины, соединенные ребром,
    не раскрашены одинаковыми цветами.
     
  3. GL

    GL New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2010
    Сообщения:
    5
    Т.е. задача сводится к тому чтобы, например, первую вершину красим в черный, всех ее соседей в белый, всех соседей-соседей в черный и т.д.
    Решить такое можно с помощью, например, BFS.
    Я Вас правильно понял?
     
  4. tectep

    tectep New Member

    Публикаций:
    0
    Регистрация:
    23 май 2008
    Сообщения:
    8
    Способ представления графа выбирается исходя из его структуры (в общем случае). Но для данной задачи удобен способ представления "список примыканий". Элементы списка ссылаются на список связанных вершин. Пусть изначально цвет всех вершин [x] - неопределённый, а по мере продвижения алгоритма по списку, он будет заполняться: [Ч]ёрный или [Б]елый.
    [1 [x]] -> [2 [x]], [3 [x]]
    [2 [x]] -> [1 [x]], [3 [x]], [4 [x]]
    [3 [x]] -> [1 [x]], [2 [x]], [5 [x]]
    [4 [x]] -> [2 [x]], [5 [x]]
    [5 [x]] -> [3 [x]], [4 [x]]

    Красиво будет сделать рекурсивную раскраску, но сложность надо будет просчитать - тут не факт, что рекурсия даст полиномическую сложность. Как только рекурсивная фунция обнаружит противоречие, вершина [Ч] закрашивается в [Б] или наоборот, то надо остановиться, если не обнаружит, то граф можно раскрасить в два цвета.
    Пример трассировки рекурсивной расскраски (данный граф имеет хроматическое число выше 2, то есть двумя цветами не раскрасить, но рекурсивная функция узнает об этом не сразу):
    [1 [Ч-1, Ч-5, Б-9]] -> [2 [Б-2]], [3 [x]]
    [2 [Б-3]] -> [1 [Ч-4]], [3 [Ч-6]], [4 [x]]
    [3 [Ч-7]] -> [1 [Б-8]], [2 [x]], [5 [x]]
    [4 [x]] -> [2 [x]], [5 [x]]
    [5 [x]] -> [3 [x]], [4 [x]]

    Будет 9 шагов раскраски, после шага Б-8 (8-й шаг, вершина 1 красится в белый), фунция пойдёт в вершину 1, и обнаружит, что та уже [Ч]ёрная, то есть 9-й шаг - последний (+ накладные расходы на выход из рекурсии). В целом эффективно, но вероятно, есть способ и побыстрее.