Изменения

{{Определение|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)не меняя числа ребер.

В данном алгоритме оператор <tex>\mathrm {\bf {spawn}}</tex> запускает новый поток, а оператор <tex>\mathrm {\bf {sync}}</tex> ожидает завершения этого потока. Функция '''Следствие:'''Хроматический многочлен любого графа <tex>\mathrm {merge}G</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#.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|слияние двух массивов]].<br>Несмотря на наличие двух рекурсивных вызововравен сумме хроматических многочленов некоторого числа полных графов, при оценке будем считатьчисло вершин в которых не больше, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: чем в графе <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)G</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

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

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

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

===Сортировка с многопоточным слияниемХроматический многочлен простой цепи ===Приведем псевдокод алгоритмаПусть <tex>T_n</tex> — простая цепь, использующего слияние состоящая из <tex>n</tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]x</tex> цветов, вторую и помещающего отсортированный массив последующие в один из <tex dpi>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P(T_n, x) ="120">B[leftB \dots leftB + rightA 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|простой цепью] = A[leftA]. '''else''' создадим новый массив T[Тогда <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)=</tex><tex>(x-1)^{k+1}+(-1)^{k+1}(x-1 )</tex dpi>.}}="120"== Хроматический многочлен колеса ==={{Определение|definition=Колесо — это граф с <tex>n</tex> вершинами (<tex>n \dotsle 4</tex>), образованный соединением единственной вершины со всеми вершинами (<tex>n - 1</tex>)-цикла.}}Пусть <tex>W_n</tex> — колесо с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P_{C_{n - 1}}(x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса <tex>P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^n](x - 2))</tex>.=== Хроматический многочлен дерева ==={{Теорема|about=хроматический многочлен дерева mid |statement= Граф <tex>G</tex> с <tex>n</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> mergeSortMT2<tex>\Leftarrow</tex><br>Обратно, пусть <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 dpi="130">T_{\mathrm {mergeSort}}P(nG,0) = T_{\mathrm {mergeSort}}0</tex>. Из этого следует, что <tex>P(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 nG,x)</tex> кратен <tex>x</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 dpi="120">N_G_{ind1}</tex>. Допустим— граф, полученный из <tex>G</tex> добавлением отсутствующего в <tex>G</tex> ребра <tex dpi="120">nuv</tex> много больше , а <tex dpi="120">N_G_{ind2}</tex>— граф, что полученный из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex> в общем случае верно для ПК одну и достаточно больших объемов данныхудалением возникших при этом кратных ребер. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущенийПрименяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi>P(G,x) ="135">\Theta{P(\fracK_{n},x) + a_{N_1}P(K_{indn-1},x) + a_{2}\log \fracP(K_{n-2},x) + \ldots = x^{N_\underline{indn}} + n) = a_{1}x^{\Theta(\fracunderline{n-1}}+a_{N_2}x^{ind}}\log \fracunderline{n-2}{N_{ind}+\ldots})</tex><br/>Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.}} {{Теорема|about=3|statement=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof=Индукция по количеству вершин.<br/>'''База индукции:'''<br/>::::Теорема верна для графа <tex>G</tex> из одной вершины, потому что <tex dpi>P(G,x)="135"x</tex>.<br/>\Theta'''Индукционный переход''' (\frac{<tex>n}{N_{ind}}\log \frac{to n}{N_{ind}}+1)</tex> операций нужно :<br/>Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на последовательную сортировку массива длиной <tex dpi="135">\fracn+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{N_{ind}n+1}</tex>обладает доказываемым свойством.::::Теперь предположим, что для всех <tex dpi="135">\Theta(n+1,m)</tex> необходимо на последовательное слияние-графов теорема верна.::[[#Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D0.BE.D0.B5_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|Многопоточное слияние]] будет работать Обозначим за <tex dpi="135">\Theta((\fracG</tex> граф, полученный из <tex>G_{n1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{N_{ind}1}-uv</tex>)^, а за <tex>G_{(\log_{\frac{42}</tex> — граф, полученный из <tex>G_{31}}2)} + \log n \cdot min</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/><tex>P(N_G_{ind1}, \log nx)=\ThetaP((\frac{n}{N_{ind}}G,x)^{-P(\log_{\frac{4}G_{3}}2)},x)</tex>:.::::Прежде чем достигнуть ограничения на создание нового потокаТак как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, алгоритм углубится на а в <tex dpi="110">min(N_G_{ind2}, \log </tex> — <tex>n)</tex> уровней вглубь дерева рекурсиивершин, где на каждом уровне выполняется бинпоиск за то для <tex>G</tex> и <tex dpi="135">\Theta(\log n)G_{2}</tex>теорема верна::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна <br/>::::<tex dpi="135">T_{\mathrm P(G,x)=x^{mergen+1}-a_{1}'(x^{n) = 2T_}+a_{\mathrm 2}x^{mergen-1}}'(\frac -a_{3}x^{4n-2}n) + \Thetaldots}</tex> ,<br/><tex>{P(\log nG_{2},x) = \Theta(nx^{(\log_n}-b_{\frac1}x^{4n-1}+b_{32}x^{n-2}2)+\ldots})</tex> ,<br/>::Оценим [[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|сортировку с многопоточным слиянием]] снизу:::::Части массива длиной где <tex dpi="135">\frac{n}a_{N_{ind}1}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm a_{mergeSortMT22} </tex> от массива длиной … <tex dpi="135">\fraca_{n+1}</tex>, <tex>b_{N_1}</tex>, <tex>b_{ind}2}</tex> число потоков, равное … <tex dpi="135">N_b_{indn}</tex>— некоторые неотрицательные целые числа. Тогда по основной теореме рекуррентных соотношенийИз этих равенств получаем:<br/>::::<tex dpi="135">T_{\mathrm {mergeSort}}'P(\fracG_{n}{N_{ind}1},x) = 2T_x^{\mathrm {mergeSortn+1}}'-(\fraca_{n1}+1)x^{2N_{indn}}) + \Theta(\fraca_{n2}+b_{N_{ind}1})x^{(\log_{\frac{4n-1}{3}}2)} = +\Theta(\frac{nldots</tex>.Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}{N_{ind}})^ {(\log_{\frac{Теорема|about=4}{|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3}}2)}''' видно, что при увеличении количества ребер графа на <tex>1</tex>Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием вышевторой коэффициент также увеличивается на <tex>1</tex>. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет Так как для пустого графа второй коэффициент равен <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})0</tex>, то утверждение верно для любого графа.}} ===Литература=Источники информации ==Cormen T* Асанов М. О., Баранский В.HА., Leiserson CРасин В.EВ. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.2-е изд., испр. и доп. - СПб.: Издательство "Лань", Rivest R2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2* Харари Ф. — Теория графов: Изд. 4-е.L- М.: Книжный дом "ЛИБРОКОМ", Stein C2009. - 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 {{---}} Introduction to Algorithms, Third EditionХроматический многочлен]] [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]