Задача определения хроматического полинома графа
Для теории графов домашних заданий меня просят определить хроматический полином следующего графа
Для теоремы о разложении хроматических полиномов. если G=(V,E), связный граф и e принадлежит E
P (G, λ) = P (Ge, λ) -P(Ge', λ)
где Ge обозначает де-подграф, полученный удалением dedge e из G (Ge= Ge), а Ge'- это подграф, полученный путем идентификации вершин {a,b} = e
При вычислении хроматических полиномов я должен поместить квадратные скобки вокруг графа, чтобы указать его хроматический полином. удаляет ребро любого исходного графа для вычисления хроматического полинома методом разложения.
P (G, λ) = P (Ge, λ)-P (Ge', λ) = λ (λ-1)^4 - [λ(λ-1)*(λ^2 - 3λ + 3)]
Но ответ от ключа ответа и учителя:
P (G, λ) = λ (λ-1)(λ-2)(λ^2-2λ-2)
Я оперировал полиномом, но не могу найти решение, которое спрашиваю... что я делаю не так?
3 ответа
math.stackexchange.com рассказал мне, как решить мою проблему. Вот решение:
Ваш ответ правильный, как и у учителя - они равны. [Кстати, хорошая картина и объяснение.]
Нечетный цикл не может иметь 2-окраски, следовательно, 5-цикл не может иметь 2-окраски, поэтому его хроматический полином f(x) должен иметь x * [x - 1] * [x - 2]
как делитель. Если вы объедините свое выражение для f(x) и разделите
x * [x - 1]
тогда вы обнаружите, что то, что осталось, делится на [x - 2], а частное - это то, что написал ваш учитель. Джонатан Кинг
В книге, которой я следую ("Теория графов с приложениями" - Deo Prentice Hall), все сделано по-другому. Вместо исключения ребра они соединяют две несмежные вершины.
Используя эту технику, я получаю
P (G, λ) = 2λ(λ-1)^2(λ-2) + 2λ(λ-1)(λ-2)(λ-3) + λ(λ-1)(λ-2)(λ-3)(λ-4) что также не равно ни одному из ваших результатов.
