задача на определение хроматического многочлена графа

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

введите здесь описание изображения

Для Теоремы о разложении хроматических многочленов. если G=(V,E), является связным графом и e принадлежит E

P (G, λ) = P (Ge, λ) -P(Ge', λ)

где Ge обозначает подграф de, полученный удалением ребра de 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)

Я работал над полиномом, но не могу найти решение, о котором спрашиваю... что я делаю не так?


graph-theory polynomial-math text-coloring
person franvergara66    schedule 20.04.2011    source источник
comment
Интересная проблема, но я думаю, что вам лучше получить ответ по адресу: cstheory.stackexchange.com или math.stackexchange.com   -  person Paul Sasik    schedule 20.04.2011
comment
да, но на обеих страницах я не могу размещать изображения, потому что я новый пользователь.   -  person franvergara66    schedule 20.04.2011
comment
Идите вперед и открывайте новые вопросы на обоих сайтах, и я отредактирую вопросы для вас с изображениями, как они здесь. Ответьте, конечно, здесь, чтобы я знал, когда вопросы будут готовы.   -  person Paul Sasik    schedule 20.04.2011
comment
math.stackexchange.com/questions/33946/   -  person franvergara66    schedule 20.04.2011
comment
Похоже, вы получили отличный ответ. И хорошая идея, чтобы вернуться к SO для исходного вопроса с изображениями. Итак, вы готовы идти?   -  person Paul Sasik    schedule 20.04.2011
comment
вопрос не решился, но натолкнул на мысль как это сделать, думаю вопрос закрою   -  person franvergara66    schedule 21.04.2011
comment
Вы можете ответить на свой вопрос, не забудьте.   -  person Paul Sasik    schedule 21.04.2011

Ответы (3)


arrow_upward
3
arrow_downward

math.stackexchange.com сказал мне, как решить мою проблему. Вот решение:

https://math.stackexchange.com/questions/33946/problem-to-determine-the-chromatic-polynomial-of-a-graph

person franvergara66    schedule 20.04.2011

arrow_upward
3
arrow_downward

Ваш ответ правильный, как и ответ учителя — они равны. [Кстати, красивая картинка и объяснение.]

Нечетный цикл не может иметь 2-раскраски, следовательно, 5-цикл не может иметь 2-раскраски, поэтому его хроматический многочлен f(x) должен иметь x * [x - 1] * [x - 2]

как делитель. Если вы скомбинируете свое выражение для f(x) и разделите

x * [x - 1]

тогда вы обнаружите, что то, что осталось, делится на [х - 2], а частное - это то, что написал ваш учитель. -Джонатан Кинг

person Jonathan King    schedule 12.03.2013

arrow_upward
0
arrow_downward

В книге, которой я следую (Теория графов с приложениями - Део Прентис Холл), это сделано по-другому. Вместо исключения ребра они соединяют две несмежные вершины.

Используя эту технику, я получаю

P (G, λ) = 2λ(λ-1)^2(λ-2) + 2λ(λ-1)(λ-2)(λ-3) + λ(λ-1)(λ-2)(λ-3)(λ-4), что также не равно ни одному из ваших результатов.

введите здесь описание изображения

person Souradeep Nanda    schedule 07.04.2017