Изменения

{{Определение|definition== Многопоточная сортировка слиянием ==Благодаря тому, что сортировка слиянием построена на принципе "Разделяй Пусть дан фиксированный граф <tex>G</tex> и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелитьфиксированное число красок <tex>x</tex>. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, тКоличество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' (англ.е''chromatic polynomial''). процессов с вычислительными ресурсамиОбозначение: <tex>P(G, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоковx)</tex>.===Сортировка с однопоточным слиянием===Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.}}

mergeSortMT(array, left, right): mid = (left + right) / 2= Рекуррентные формулы для хроматических многочленов == {{Определение |definition='''spawnСтягивание ребра''' mergeSortMT(arrayангл. ''edge contraction'') — замена концов ребра одной вершиной, leftсоседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, midполученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}{{Теорема|statement=Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex>, то <tex>P(G,x) mergeSortMT=P(arrayG_1, mid x)+ 1P(G_2, rightx)</tex>.|proof=Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.}} '''syncЗамечание:''' merge(arrayЕсли к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, leftесли в произвольном графе уменьшим число вершин, midпутем их отождествления, right)не меняя числа ребер.

В данном алгоритме оператор '''spawnСледствие:''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http:Хроматический многочлен любого графа <tex>G<//neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2 слияние двух массивов].<brtex>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считатьравен сумме хроматических многочленов некоторого числа полных графов, что совершается один вызовчисло вершин в которых не больше, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: чем в графе <tex>T(n) = T(n / 2) + \Theta(n) = \Theta(n)G</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

===Многопоточное слияние=={{Теорема|statement=Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов Пусть <tex>T[left_{1} \dots right_{1}]u</tex> и <tex>T[left_{2} \dots right_{2}]</tex> в массив <tex>A[left_{3} \dots right_{3}]v</tex>:# Убедимся, что размер — смежные вершины графа <tex>T[left_{1} \dots right_{1}]G</tex> больше либо равен размеру . Если <tex>T[left_{2} G_1=G\dots right_{2}]backslash uv</tex># Возьмем и <tex>x G_2= T[mid_{1}]<G/tex> - середину первого массива (<tex>xuv</tex> также является и медианой этого массива)# При помощи бинарного поиска найдем , то <tex>mid_{2}</tex> такоеP(G, что <tex>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex># <tex>mid_{3} )= left_{3} + P(mid_{1} G_1,x)- left_{1}) + P(mid_{2} - left_{2}G_2,x)</tex>.# <tex>A[mid_{3}] |proof= x</tex># Сольем <tex>T[right_{1} \dots mid_{1} - 1]</tex> и <tex>T[right_{2} \dots mid_{2}]</tex> в <tex>A[right_{3} \dots mid_{3} - 1]</tex>Следует из предыдущей теоремы.# Сольем <tex>T[mid_{1} + 1 \dots right_{1}]</tex> и <tex>T[mid_{2} \dots right_{2}]</tex> в <tex>A[mid_{3} + 1 \dots right_{3}]</tex>Рассмотрим псевдокод данного алгоритма:

// если <tex>right \leqslant left</tex> возвращает <tex>left</tex>== Примеры хроматических многочленов == // если <tex>x \leqslant T[left]</tex>, возвращает <tex>left</tex> // иначе возвращает наибольший индекс <tex>i</tex> из отрезка <tex>[left; right]</tex> такой, что <tex>array[i - 1] < x</tex> binarySearch(x, array, left, right) // слияние <tex>T[left_{1} \dots right_{1}]</tex> и <tex>T[left_{2} \dots right_{2}]</tex> в <tex>A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex> mergeMT(T, left<tex>_{1}</tex>, right<tex>_{1}</tex>, left<tex>_{2}</tex>, right<tex>_{2}</tex>, A, left<tex>_{3}</tex>): n<tex>_{1}</tex> = right<tex>_{1}</tex> - left<tex>_{1}</tex> + 1 n<tex>_{2}</tex> = right<tex>_{2}</tex> - left<tex>_{2}</tex> + 1 '''if''' n<tex>_{1}</tex> < n<tex>_{2}</tex>: swap(left<tex>_{1}</tex>, left<tex>_{2}</tex>) swap(right<tex>_{1}</tex>, right<tex>_{2}</tex>) swap(n<tex>_{1}</tex>, n<tex>_{2}</tex>) '''if''' n<tex>_{1}</tex> = Хроматический многочлен полного графа == 0: '''return''' '''else''' mid<tex>_{1}</tex> = (left<tex>_{1}</tex> + right<tex>_{1}</tex>) / 2 mid<tex>_{2}</tex> = binarySearchP(T[mid<tex>_K_{1n}</tex>], T, left<tex>_{2}</tex>, right<tex>_{2}</tex>x) mid<tex>_{3}</tex> = left<tex>_{3}</tex> + x(mid<tex>_{1}</tex> x- left<tex>_{1}</tex>) + ...(mid<tex>_{2}</tex> x- left<tex>_{2}</tex>n+1) A[mid<tex>_=x^{3}</tex>] = T[mid<tex>_\underline{1n}</tex>] '''spawn''' mergeMT(T, left<tex>_{1}</tex>, midтак как первую вершину полного графа <tex>_K_{1n}</tex> - 1, leftможно окрасить в любой из <tex>_{2}x</tex>цветов, midвторую — в любой из оставшихся <tex>_{2}</tex> x- 1, A, left<tex>_{3}</tex>) mergeMT(Tцветов и т. д. Очевидно, midчто если <tex>_{1}x</tex> + 1, rightменьше <tex>_{1}n</tex>, midто и многочлен равен <tex>_{2}0</tex>, rightтак как один из его множителей <tex>_{2}</tex>, A, mid<tex>_{3}0</tex> + 1) '''sync'''.

Оба массива содержат <tex>n_=== Хроматический многочлен нуль-графа ==={1} + n_{2} Определение|definition= n</tex> элементов'''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. К моменту рекурсивных вызовов ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>n_{2} \leqslant n_{1}0</tex>, значит,<br>т.е. граф без рёбер.}}<tex>n_{2} = 2 \cdot n_{2} / 2 \leqslant P(n_O_{1} + n_{2n},x) / 2 = x^{n / 2}</tex>.<br> В худшем случае один , так как каждую из двух рекурсивных вызовов сольет <tex>n_{1} / 2n</tex> элементов вершин нулевого графа <tex>T[left_O_{1} \dots right_{1n}]</tex> с можно независимо окрасить в любой из <tex>n_{2}x</tex> элементами цветов.<br>'''Примечание:''' Нулевой граф <tex>T[left_O_{2} \dots right_{2n}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br>также можно обозначать <tex>n_{1} / 2 + n_{2} \leqslant n_overline{1} / 2 + n_K_{2} / 2 + n_{2} / 2 = (n_{1} + n_{2n}) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 \cdot n / 4</tex>.<br>Асимптотика каждого вызова функции - <tex>\Theta(\log(n))дополнительный граф для полного графа </tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(3 \cdot n / 4)</tex>. Тогда получим оценку сверху<br><tex>T_K_{merge}(n) = T_{merge}(3 \cdot n / 4) + \Theta(\log(n)) = \Theta(\log^2(n))</tex>).

===Сортировка с многопоточным слияниемХроматический многочлен простой цепи ===Приведем псевдокод алгоритмаПусть <tex>T_n</tex> — простая цепь, использующего слияние состоящая из <tex>n</tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из предыдущего раздела, сортирующего элементы <tex>A[leftA \dots rightA]x</tex> цветов, вторую и помещающего отсортированный массив последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>B[leftB \dots leftB + rightA P(T_n, x) = x(x - 1) ^ {n - leftA]1}</tex>.

mergeSortMT2=== Хроматический многочлен цикла ==={{Теорема|about=хроматический многочлен цикла|statement=Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P(AC_n, leftAx) = (x - 1)^n + (-1)^n(x - 1)</tex>.|proof=Рассмотрим случай <tex>n = 3</tex>: <tex>P(C_3, rightAx) = x(x - 1)(x - 2) = (x - 1)(x^2 - x) = (x - 1)^3 + (-1)^3(x - 1)</tex>, Bчто удовлетворяет формулировке теоремы.<br>Пусть <tex>P(С_k, leftBx): n = r (x - p 1)^k + (-1)^k(x - 1)</tex>.<br> '''if''' Рассмотрим случай <tex>n =k + 1</tex>. По теореме о [[#.D0.A0.D0.B5.D0.BA.D1.83.D1.80.D1.80.D0.B5.D0.BD.D1.82.D0.BD.D1.8B.D0.B5_.D1.84.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D1.8B_.D0.B4.D0.BB.D1.8F_.D1.85.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D1.85_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD.D0.BE.D0.B2|рекурентной формуле для хроматических многочленов]]: <tex>P(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)</tex> (где <tex>e</tex> — любое ребро <tex>C_{k + 1:}</tex>). BЗаметим, что граф <tex>C_{k + 1} / e</tex> изоморфен <tex>C_k</tex>. Заметим, что граф <tex>C_{k + 1} \setminus e</tex> является [leftB[#.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_.D0.BF.D1.80.D0.BE.D1.81.D1.82.D0.BE.D0.B9_.D1.86.D0.B5.D0.BF.D0.B8|простой цепью] ].Тогда <tex>P(C_{k + 1}, x)=P(T_{k + 1}, x)-P(C_k, x)=x(x-1)^k-(x-1)^k-(-1)^k(x-1)= A[leftA]</tex><tex>(x-1)^{k+1}+(-1)^{k+1}(x-1)</tex>.}}=== Хроматический многочлен колеса ==={{Определение '''else'''|definition=Колесо — это граф с <tex>n</tex> вершинами (<tex>n \le 4</tex>), образованный соединением единственной вершины со всеми вершинами (<tex>n - 1</tex>)-цикла.}} создадим новый массив T[Пусть <tex>W_n</tex> — колесо с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P_{C_{n - 1}}(x - 1 ) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса <tex>P_{W_n}(x) = x \dotscdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2))</tex>.=== Хроматический многочлен дерева ==={{Теорема|about=хроматический многочлен дерева|statement=Граф <tex>G</tex> с <tex> n] mid </tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)= x(leftA + rightAx-1) ^{n-1}</ 2tex>. newMid |proof= mid <tex>\Rightarrow</tex><br>Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n- leftA + 1}</tex>. Доказательство индукцией по числу <tex>n</tex>. Для <tex>n=1</tex> и <tex>n=2</tex> результат очевиден. Предположим, что <tex>P(T',x)=x(x-1)^{n-2}</tex> для любого дерева <tex>T''spawn''' mergeSortMT2</tex> с количеством вершин равным <tex>n-1</tex>. Пусть <tex>uv</tex> — ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(AT/uv, leftAx)=x(x-1)^{n-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>x-1</tex> способом, midтак как её цвет должен только лишь отличаться от цвета вершины <tex>u</tex>. Итого: <tex>P(T, x)=(x-1)P(T/uv, x)=x(x-1)^{n-1}</tex>.<br><tex>\Leftarrow</tex><br> mergeSortMT2Обратно, пусть <tex>G</tex> — граф, у которого <tex>P(AG, mid + x)=x(x-1)^{n-1}</tex>. Тогда верны два следующих утверждения:<ol> <li>Граф <tex>G</tex> связен, rightAпотому что если было бы две компоненты связности (или больше), Tто <tex>P(G, newMid + 1x)</tex> делился бы на <tex>x^2</tex> без остатка.<br /></li> '''sync''' mergeMT <li>В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по одной из теорем о коэффициентах хроматического многочлена (T[[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 4), количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, newMidвзятому со знаком минус. В нашем случае, newMid этот коэффициент удобно искать, используя бином Ньютона:<br /><tex>{P(G,x)=x(x-1)^{n-1}=x\left(x^{n-1}-{n-1 \choose 1}x^{n-2}+{n-1 \choose 2}x^{n-3}-...+(-1)^{n-1}\right)=x^{n}-(n-1)x^{n-1}+ ...+(-1)^{n-1}x}</tex><br /> </li></ol>Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, nчто граф <tex>G</tex> является деревом (см. [[Дерево, Bэквивалентные определения]], leftBутверждения 1 и 3).}}

Оценим данный алгоритм сверху при условии== Коэффициенты хроматического многочлена =={{Теорема|about=1|statement=Свободный член хроматического многочлена равен <tex>0</tex>.|proof=По определению хроматического многочлена графа <tex>G</tex>, что возможен запуск неограниченного количества независимых потоковего значение в точке <tex>x</tex> равно количеству способов раскрасить вершины <tex>G</tex> правильным образом в <tex>x</tex> цветов. Количество способов раскрасить граф в <tex>0</tex> цветов равно <tex>0</tex>. Из предыдущих пунктов То есть <tex>T_{mergeSort}P(nG,0) = T_{mergeSort}(n 0</ 2) + T_{merge}tex>. Из этого следует, что <tex>P(nG,x) = T_{mergeSort}(n </tex> кратен <tex>x</ 2) + \Theta(\log^2(n)) = \Theta(\log^3(n))tex>, следовательно его свободный член равен <tex>0</tex>.}}

{{Теорема|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>N_G_{ind2}</tex>— граф, полученный из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex> в одну и удалением возникших при этом кратных ребер. Оценим приведенные выше алгоритмы с учетом наложенных ограниченийПрименяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>::'''Сортировка с однопоточным слиянием''' будет иметь асимптотику <tex>\ThetaP(G,x) = {P(K_{n/N_},x) + a_{ind1}\logP(K_{n/N_-1},x) + a_{2}P(K_{indn-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>\Theta.<br/>'''Индукционный переход''' (<tex>n/N_{ind}\log(to n+1)</tex>:<br/N_{ind}))>Предположим, что теорема верна для всех графов на <tex>n</tex> операций нужно вершинах. Рассмотрим графы на последовательную сортировку массива длиной <tex>n+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</N_tex>, то его хроматический многочлен <tex>P(G,x)=x^{indn+1}</tex>обладает доказываемым свойством.::::Теперь предположим, что для всех <tex>\Theta(n+1,m)</tex> необходимо на последовательное слияние-графов теорема верна.::Соответветственно, асимптотика может быть как Возьмем <tex>\Theta(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</N_tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{ind1}\log</tex> удалением ребра <tex>uv</tex> (n<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/N_><tex>P(G_{ind1},x)=P(G,x)-P(G_{2},x)</tex>.Так как <tex>G</tex>, так и — <tex>\Theta(n+1,m)</tex> -граф, а в зависимости от <tex>N_G_{ind2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>nG_{2}</tex> теорема верна:<br/>::'''Многопоточное слияние''' будет работать за <tex>\Theta{P((\fracG,x)=x^{n+1}-a_{1}x^{n}+a_{N_2}x^{indn-1}-a_{3})x^{n-2}+\ldots}</tex> ,<br/><tex>{P(\log_G_{2},x)=x^{\fracn}-b_{41}x^{3n-1}+b_{2}x^{n-2)} + \log(n) \cdot min(N_ldots}</tex> ,<br/>где <tex>a_{ind1}</tex>, \log(<tex>a_{2}</tex> … <tex>a_{n))+1}</tex>::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex>min(N_b_{ind1}</tex>, \log(n))<tex>b_{2}</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за … <tex>\Theta(\log(b_{n))}</tex>— некоторые неотрицательные целые числа. Из этих равенств получаем::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна <br/>::::<tex>T_P(G_{merge1}'(n,x) = 2T_x^{mergen+1}'-(\frac a_{31}+1)x^{4n}n) + \Theta(\log(na_{2}+b_{1})) = \Theta(nx^{(n-1}+\log_ldots</tex>.Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}} {\frac{Теорема|about=4}{|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3}}2)})''' видно, что при увеличении количества ребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Так как для пустого графа второй коэффициент равен <tex>0</tex>, то утверждение верно для любого графа.}} ===Литература=Источники информации ==Cormen T* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.H2-е изд., Leiserson Cиспр. и доп.E- СПб.: Издательство "Лань", Rivest R2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература).LISBN 978-5-8114-1068-2* Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", Stein C2009. - 296 с. ISBN 978-5-397-00622-4* [[wikipedia:en:Chromatic_polynomial| Wikipedia {{---}} Introduction to Algorithms, Third EditionChromatic_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 {{---}} Хроматический многочлен]] [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]