#graph-theory #polynomial-math #text-coloring
#теория графов #многочлен-математика #раскраска текста
Вопрос:
для домашнего задания по теории графов меня просят определить хроматический многочлен следующего графика
Для теоремы декомпозиции хроматических многочленов. если G=(V,E), является связным графом и e принадлежит E
P (G, λ) = P (Ge, λ) -P(Ge', λ)
где Ge обозначает подграф, полученный путем удаления ребра e из G (Ge= G-e), а Ge’ — подграф, полученный путем идентификации вершин {a,b} = e
При вычислении хроматических многочленов я буду заключать график в квадратные скобки, чтобы указать его хроматический многочлен. удаляет любое ребро исходного графа для вычисления хроматического многочлена методом декомпозиции.
P (G, λ) = P (Ge, λ)-P (Ge', λ) = λ (λ-1)^4 - [λ(λ-1)*(λ^2 - 3λ 3)]
Но ответ от ключа ответа и учителя является:
P (G, λ) = λ (λ-1)(λ-2)(λ^2-2λ-2)
Я оперировал с многочленом, но я не могу прийти к решению, которое я прошу.. что я делаю не так?
Комментарии:
1. Интересная задача, но я думаю, вам было бы лучше получить ответ по адресу: cstheory.stackexchange.com или math.stackexchange.com
2. да, но на обеих страницах я не могу публиковать изображения, потому что я новый пользователь.
3. Продолжайте и открывайте новые вопросы на обоих сайтах, и я отредактирую вопросы для вас с изображениями, как они есть здесь. Ответьте здесь, конечно, чтобы я знал, когда Qs будут готовы.
4. math.stackexchange.com/questions/33946/…
5. Похоже, вы получили отличный ответ. И хорошая идея вернуться к ссылке SO для исходного вопроса с изображениями. Итак, вы готовы к работе?
Ответ №1:
math.stackexchange.com рассказал мне как способ решения моей проблемы. Вот решение:
Ответ №2:
Ваш ответ правильный, как и ответ учителя — они равны. [Кстати, хорошая картинка и объяснение.]
Нечетный цикл не может иметь двухцветной раскраски, следовательно, 5-цикл не может иметь двухцветной раскраски, поэтому его хроматический многочлен, f (x), должен иметь x * [x — 1] * [x — 2]
в качестве делителя. Если вы объедините свое выражение для f (x) и разделите
x * [x - 1]
тогда вы обнаружите, что то, что остается, делится на [x — 2], и
частное — это то, что написал ваш учитель.
-Джонатан Кинг
Ответ №3:
В книге, которую я читаю (Теория графов с приложениями — Deo Prentice Hall), это делается по-другому. Вместо исключения ребра они соединяют две несмежные вершины.
Используя эту технику, я получаю
P (G, λ) = 2λ(λ-1)^2(λ-2) 2λ(λ-1)(λ-2)(λ-3) λ(λ-1)(λ-2)(λ-3)(λ-4) который также не равен ни одному из ваших результатов.
