Изменения

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

В данном алгоритме оператор == Рекуррентные формулы для хроматических многочленов =={{Определение|definition='''Стягивание ребра''' (англ. ''edge contraction'') — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>\mathrm {\bf {spawn}}G/uv</tex> запускает новый потокграф, а оператор полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>\mathrm .}}{\bf {sync}}Теорема|statement=Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex> ожидает завершения этого потока. Функция Если <tex>G_1=G\mathrm {merge}cup uv</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|слияние двух массивов]]., а <tex>G_2=G/uv<br/tex>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: то <tex dpi="120">TP(nG,x) = TP(\frac {n}{2}G_1,x) + \ThetaP(nG_2,x) </tex>.|proof= \Theta(n)Рассмотрим все произвольные раскраски графа <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<br/tex>и <tex>v</tex>.}}'''Замечание:'''Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.

==Многопоточное слияние==Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <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_{3}]</tex>:[[Файл'''Следствие:MergeMT.png‎|430px|thumb|Слияние массивов]]'''# Убедимся, что размер Хроматический многочлен любого графа <tex dpi="120">T[left_{1} \dots right_{1}]G</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex># Возьмем <tex dpi="120">x = T[mid_{1}]</tex> - середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такоесумме хроматических многочленов некоторого числа полных графов, что <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}) + (mid_{2} - left_{2})</tex># <tex dpi="120">A[mid_{3}] = 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}]G</tex>.

===Реализация==={{Теорема // если <tex dpi|statement="120">right \leqslant left</tex> возвращает <tex dpi="120">left</tex> // если Пусть <tex dpi="120">x \leqslant T[left]u</tex>, возвращает и <tex dpi="120">leftv</tex> // иначе возвращает наибольший индекс — смежные вершины графа <tex dpi="120">iG</tex> из отрезка . Если <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex> integer binarySearch(x, array, left, right) // слияние <tex dpiG_1="120">T[left_{1} G\dots right_{1}]backslash uv</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> function mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpiG_2="120">_{1}</tex>, left<tex dpi="120">_{2}<G/tex>, right<tex dpi="120">_{2}uv</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> swapP(left<tex dpi="120">_{1}</tex>G, left<tex dpi="120">_{2}</tex>x) swap(right<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{2}</tex>) swapP(n<tex dpi="120">_{1}</tex>G_1, n<tex dpi="120">_{2}</tex>x) '''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-P(T[mid<tex dpi="120">_{1}</tex>]G_2, T, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>) mid<tex dpi="120">_{3}</tex> = left<tex dpi="120">_{3}</tex> + (mid<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex>x) + (mid<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex>). A[mid<tex dpi="120">_{3}</tex>] |proof= T[mid<tex dpi="120">_{1}</tex>] '''spawn''' mergeMT(T, left<tex dpi="120">_{1}</tex>, mid<tex dpi="120">_{1}</tex> - 1, left<tex dpi="120">_{2}</tex>, mid<tex dpi="120">_{2}</tex> - 1, A, left<tex dpi="120">_{3}</tex>)Следует из предыдущей теоремы. mergeMT(T, mid<tex dpi="120">_{1}</tex> + 1, right<tex dpi="120">_{1}</tex>, mid<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, mid<tex dpi="120">_{3}</tex> + 1) '''sync'''

Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpiПримеры хроматических многочленов ===== Хроматический многочлен полного графа ==="120">n_{2} \leqslant n_{1}</tex>, значит,<br><tex dpi="135">n_P(K_{2n} ,x)= 2 \cdot \frac{n_{2}}{2} \leqslant \frac{x(n_{x-1} )...(x-n+ n_{2}1)}=x^{2} = \fracunderline{n}{2}</tex>.<br>В худшем случае один из двух рекурсивных вызовов сольет , так как первую вершину полного графа <tex dpi="135">\fracK_{n_{1}}{2n}</tex> элементов можно окрасить в любой из <tex dpi="120">T[left_{1} \dots right_{1}]x</tex> с цветов, вторую — в любой из оставшихся <tex dpi="120">n_{2}x-1</tex> элементами цветов и т. д. Очевидно, что если <tex dpi="120">T[left_{2} \dots right_{2}]x</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} + \frac{n}{4} = \frac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции - , то и многочлен равен <tex dpi="120">\Theta(\log n)0</tex>, т.е. время, затрачиваемое на бинарный поиск. Так так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это один из его множителей <tex dpi="120">T(\frac{3}{4}n)0</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>

==Сортировка с многопоточным слиянием= Хроматический многочлен нуль-графа ===Приведем псевдокод алгоритма{{Определение|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. ''null graph'', использующего слияние из предыдущего раздела''empty graph'', сортирующего элементы ''edgeless graph'') — регулярный граф степени <tex>0</tex dpi>, т.е. граф без рёбер.}}<tex>P(O_{n},x)="120"x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>A[leftA \dots rightA]O_{n}</tex> и помещающего отсортированный массив можно независимо окрасить в любой из <tex>x</tex> цветов.<br>'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex dpi="120">B[leftB \dots leftB + rightA - leftA]overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).

function mergeSortMT2(A, leftA, rightA, B, leftB): n = r - p + 1 '''if''' n == 1 B[leftB] Хроматический многочлен простой цепи === A[leftA] '''else''' создадим новый массив T[1 Пусть <tex dpi="120">\dotsT_n</tex> — простая цепь, состоящая из <tex> n] mid = (leftA + rightA) </tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</ 2 newMid = mid tex> цветов, вторую и последующие в один из <tex>x - leftA + 1 '''spawn''' mergeSortMT2</tex> цветов (Aт.е. так, leftA, mid, T, 1чтобы цвет не совпадал с предыдущей вершиной) mergeSortMT2. Тогда <tex>P(AT_n, mid + 1, rightA, T, newMid + 1x) '''sync''' mergeMT= x(T, x - 1, newMid, newMid + ) ^ {n - 1, n, B, leftB)}</tex>.

Оценим данный алгоритм сверху при условии=== Хроматический многочлен цикла ==={{Теорема|about=хроматический многочлен цикла|statement=Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.|proof=Рассмотрим случай <tex>n = 3</tex>: <tex>P(C_3, x) = x(x - 1)(x - 2) = (x - 1)(x^2 - x) = (x - 1)^3 + (-1)^3(x - 1)</tex>, что возможен запуск неограниченного количества независимых потоковудовлетворяет формулировке теоремы. Из предыдущих пунктов <br>Пусть <tex dpi>P(С_k, x) ="130"(x - 1)^k + (-1)^k(x - 1)</tex>.<br>T_Рассмотрим случай <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} \mathrm setminus e, x) - P(C_{k + 1} / e, x)</tex> (где <tex>e</tex> — любое ребро <tex>C_{mergeSortk + 1}</tex>).Заметим, что граф <tex>C_{k + 1}/ e</tex> изоморфен <tex>C_k</tex>. Заметим, что граф <tex>C_{k + 1} \setminus e</tex> является [[#.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(nC_{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>.}}=== Хроматический многочлен колеса ==={{Определение|definition=Колесо — это граф с <tex>n</tex> вершинами (<tex>n \mathrm le 4</tex>), образованный соединением единственной вершины со всеми вершинами (<tex>n - 1</tex>)-цикла.}}Пусть <tex>W_n</tex> — колесо с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P_{C_{mergeSortn - 1}}(x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса <tex>P_{W_n}(x) = x \fraccdot P_{C_{n- 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2}) + T_)</tex>.=== Хроматический многочлен дерева ==={{Теорема|about=хроматический многочлен дерева|statement=Граф <tex>G</tex> с <tex>n</tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)=x(x-1)^{n-1}</tex>.|proof=<tex>\mathrm Rightarrow</tex><br>Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{mergen-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'</tex> с количеством вершин равным <tex>n-1</tex>. Пусть <tex>uv</tex> — ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(T/uv,x)=x(x-1)^{n-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>x-1</tex> способом, так как её цвет должен только лишь отличаться от цвета вершины <tex>u</tex>. Итого: <tex>P(T,x)=(x-1)P(T/uv,x) = T_x(x-1)^{n-1}</tex>.<br><tex>\mathrm Leftarrow</tex><br>Обратно, пусть <tex>G</tex> — граф, у которого <tex>P(G,x)=x(x-1)^{mergeSortn-1}</tex>. Тогда верны два следующих утверждения:<ol> <li>Граф <tex>G</tex> связен, потому что если было бы две компоненты связности (или больше), то <tex>P(G,x)</tex> делился бы на <tex>x^2</tex> без остатка.<br /></li> <li>В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по одной из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 4), количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<br /><tex>{P(G,x)=x(x-1)^{n-1}=x\fracleft(x^{n-1}-{n-1 \choose 1}x^{n-2}) + {n-1 \Thetachoose 2}x^{n-3}-...+(-1)^{n-1}\logright)=x^2 {n}-(n-1) = \Thetax^{n-1}+...+(\log-1)^3 {n-1}x}</tex><br /> </li></ol>Из этих двух утверждений (связность и <tex>n-1</tex> ребро)следует, что граф <tex>G</tex>является деревом (см.[[Дерево, эквивалентные определения]], утверждения 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>P(G,0)=0</tex>. Из этого следует, что при отсутствии возможности запуска неограниченного количества независимых потоков<tex>P(G,x)</tex> кратен <tex>x</tex>, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоковследовательно его свободный член равен <tex>0</tex>. Обозначим такое количество как }} {{Теорема|about=2|statement=Старший коэффициент хроматического многочлена равен <tex>1</tex dpi>.|proof="120"Воспользуемся рекуррентной формулой:<br/><tex>P(G,x) = P(G_{1},x) + P(G_{2},x)</tex>,<br/>где <tex>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 dpi="135">\fracn</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_{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(G,x)-P(\frac{n}G_{N_{ind}})^{\log_{\frac{4}{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алгоритмы: Учебное пособие.E2-е изд., Rivest Rиспр.Lи доп.- СПб.: Издательство "Лань", Stein C2010. - 368 с. : ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2* Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 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 {{---}} Хроматический многочлен]] [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]