Изменения
Нет описания правки
{{Определение|definition== Многопоточная сортировка слиянием ==Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' (англ. ''chromatic polynomial''). Обозначение: <tex>P(G,x)</tex>.}}
===Многопоточное слияниеХроматический многочлен простой цепи ===Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов Пусть <mathtex>T[left_{1} \dots right_{1}]T_n</mathtex> и — простая цепь, состоящая из <mathtex>T[left_{2} \dots right_{2}]n</mathtex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в массив один из <mathtex>A[left_{3} \dots right_{3}]x</mathtex>:# Убедимсяцветов, что размер <math>T[left_{1} \dots right_{1}]</math> больше либо равен размеру <math>T[left_{2} \dots right_{2}]</math># Вычислим вторую и последующие в один из <mathtex>x = T[mid_{- 1}]</mathtex> - середину первого массива цветов (<math>x</math> также является и медианой этого массиват.е. так, чтобы цвет не совпадал с предыдущей вершиной)# При помощи бинарного поиска найдем . Тогда <mathtex>mid_{2}</math> такоеP(T_n, что <math>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</math># <math>mid_{3} ) = left_{3} + x(mid_{1} x - left_{1}) + (mid_{2} - left_{2})</math># <math>A[mid_{3}] = x</math># Сольем <math>T[right_{1} \dots mid_^ {1} n - 1]</math> и <math>T[right_{2} \dots mid_{2}]</mathtex> в <math>A[right_{3} \dots mid_{3} - 1]</math># Сольем <math>T[mid_{1} + 1 \dots right_{1}]</math> и <math>T[mid_{2} \dots right_{2}]</math> в <math>A[mid_{3} + 1 \dots right_{3}]</math>Рассмотрим псевдокод данного алгоритма:.
{{Теорема|about=2|statement=Старший коэффициент хроматического многочлена равен <tex>1</tex>.|proof=Сортировка с многопоточным Воспользуемся рекуррентной формулой:<br/><tex>P(G,x) = P(G_{1},x) + P(G_{2},x)</tex>,<br/>где <tex>G_{1}</tex> — граф, полученный из <tex>G</tex> добавлением отсутствующего в <tex>G</tex> ребра <tex>uv</tex>, а <tex>G_{2}</tex> — граф, полученный из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex> в одну и удалением возникших при этом кратных ребер.Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/><tex>P(G,x) = {P(K_{n},x) + a_{1}P(K_{n-1},x) + a_{2}P(K_{n-2},x) + \ldots = x^{\underline{n}} + a_{1}x^{\underline{n-1}}+a_{2}x^{\underline{n-2}}+\ldots}</tex><br/>Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.}} {{Теорема|about=3|statement=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof=Индукция по количеству вершин.<br/>'''База индукции:'''<br/>Теорема верна для графа <tex>G</tex> из одной вершины, потому что <tex>P(G,x)=x</tex>.<br/>'''Индукционный переход''' (<tex>n \to n+1)</tex>:<br/>Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{n+1}</tex> обладает доказываемым свойством. Теперь предположим, что для всех <tex>(n+1,m)</tex>-графов теорема верна. Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> слияниемвершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/><tex>P(G_{1},x)=P(G,x)-P(G_{2},x)</tex>.Так как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, а в <tex>G_{2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>G_{2}</tex> теорема верна:<br/><tex>{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}</tex> ,<br/><tex>{P(G_{2},x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}</tex> ,<br/>где <tex>a_{1}</tex>, <tex>a_{2}</tex> … <tex>a_{n+1}</tex>, <tex>b_{1}</tex>, <tex>b_{2}</tex> … <tex>b_{n}</tex> — некоторые неотрицательные целые числа. Из этих равенств получаем:<br/><tex>P(G_{1},x)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots</tex>.Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}} {{Теорема|about=4|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3)''' видно, что при увеличении количества ребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Так как для пустого графа второй коэффициент равен <tex>0</tex>, то утверждение верно для любого графа.}} == Источники информации ==* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2* Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. ISBN 978-5-397-00622-4* [[wikipedia:en:Chromatic_polynomial| Wikipedia {{---}} Chromatic_polynomial]]* [[wikipedia:ru:Хроматическое_число#.D0.A5.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D0.B9_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD| Wikipedia {{---}} Хроматический многочлен]] [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]
