Graph::chromaticPolynomial
Вычисляет цветной полином
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
Graph::chromaticPolynomial(G, x)
Описание
Graph::chromaticPolynomial(G, x) возвращает цветной полином графика G. Оценка результата в x = n, для любого целочисленного n, дает количество возможных способов окрасить график G использование n окрашивает таким образом, что никакие две смежных вершины не имеют тот же цвет.
G должен быть неориентированный граф: если ребро идет от a tob, другое ребро должно пойти от b до a, для любых двух verticesa, b.
Примеры
Пример 1
Мы вычисляем цветной полином полного графика с 5 вершинами:
f:= Graph::chromaticPolynomial(Graph::createCompleteGraph(5), x)
Существует 240 способов окрасить полный график с 5 вершинами, поскольку это - количество bijective отображений между набором цветов и набором вершин:
f(5)
delete f:
Пример 2
Теперь давайте удалим одно ребро из полного графика:
G:= Graph::createCompleteGraph(5): G:= Graph::removeEdge(G, [[2, 3]]): G:= Graph::removeEdge(G, [[3, 2]])
Теперь существуют некоторые дополнительные возможные окраски: вершины 2 и 3 могут теперь иметь тот же цвет пятью различными способами; в каждом случае должен быть один из четырех остающихся цветов, который не происходит вообще. В каждом из этих 20 случаев нас оставляют с 3 вершинами, которые формируют полный график и 3 цвета, такие, что существует 6 окрасок. В целом это дает нам 120 дополнительных окрасок:
Graph::chromaticPolynomial(G, x)(5)
Параметры
|
Неориентированный граф |
|
Идентификатор |
Возвращаемые значения
Ссылки
Смотрите Биркгофа и Льюиса, Цветные Полиномы, Сделку. AMS, Издание 60, p.355-451, 1946.
Алгоритмы
Вычисление цветного полинома графика с вершинами n уменьшает до вычисления двух цветных полиномов графиков с n - 1 вершина. Время выполнения следовательно примерно 2n.