Изменения

Перейти к: навигация, поиск

Обсуждение участника:AKhimulya

7912 байт добавлено, 01:30, 25 ноября 2014
Нет описания правки
{{Определение|definition== Многопоточная сортировка слиянием ==Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' (англ. ''chromatic polynomial''). Обозначение: <tex>P(G,x)</tex>.}}
Благодаря тому== Рекуррентные формулы для хроматических многочленов =={{Определение|definition='''Стягивание ребра''' (англ. ''edge contraction'') — замена концов ребра одной вершиной, что сортировка слиянием построена на принципе "Разделяй и властвуй"соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, выполнение данного алгоритма можно весьма эффективно распараллелитьполученный из графа <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)=P(G_1,x)+P(G_2,x)</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>.}}'''Замечание: будем сортировать левую и правую части массива параллельно'''Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.
mergeSortMT(array, left, right): mid = (left + right) / 2 '''spawnСледствие:''' mergeSortMT(array, left, mid) mergeSortMT(arrayХроматический многочлен любого графа <tex>G</tex> равен сумме хроматических многочленов некоторого числа полных графов, mid + 1число вершин в которых не больше, right) '''sync''' merge(array, left, mid, right)чем в графе <tex>G</tex>.
В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http:{{Теорема|statement=Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</neerctex>.ifmo.ruЕсли <tex>G_1=G\backslash uv</wikitex> и <tex>G_2=G/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 слияние двух массивов].uv<br/tex>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: то <mathtex>TP(nG,x) = TP(n / 2G_1,x) + \Theta-P(n) = \Theta(nG_2,x)</mathtex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга|proof=Следует из предыдущей теоремы.<br>На практике на однопроцессорных компьютерах имеет смысл запускать алгоритм, ограничив количество допустимое количество потоков. Изменим код в соответствии с этими требованиями:}}
mergeSortMTBounded== Примеры хроматических многочленов ===== Хроматический многочлен полного графа ===<tex>P(arrayK_{n}, left, rightx): mid = x(left x-1)...(x-n+ right1) =x^{\underline{n}}</ 2 if threadCount tex>, так как первую вершину полного графа <mathtex>K_{n}</tex> можно окрасить в любой из <tex>x</mathtex> maxThreads: threadCount++ '''spawn''' mergeSortMTBounded(arrayцветов, left, mid) else: mergeSortMTBounded(array, left, mid) mergeSortMTBounded(array, mid + вторую — в любой из оставшихся <tex>x-1</tex> цветов и т. д. Очевидно, right) if threadCount что если <tex>x</tex> меньше <mathtex>\leqslantn</mathtex> maxThreads: '''sync''' threadCount-- merge(array, leftто и многочлен равен <tex>0</tex>, mid, right)так как один из его множителей <tex>0</tex>.
Где threadCount === Хроматический многочлен нуль- глобальный счетчикграфа ==={{Определение|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>0</tex>, а maxThreads - ограничение по количеству потоковт.е. граф без рёбер.}}<tex>P(O_{n},x)=x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>O_{n}</tex> можно независимо окрасить в любой из <tex>x</tex> цветов.<br>Данный алгоритм будет иметь асимптотику'''Примечание: ''' Нулевой граф <tex>O_{n}<math/tex> также можно обозначать <tex>\Theta((overline{K_{n }}</ maxThreads) * \log(tex> (дополнительный граф для полного графа <tex>K_{n / maxThreads)))}</mathtex>).
===Многопоточное слияниеХроматический многочлен простой цепи ===Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов Пусть <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=хроматический многочлен цикла|statement=Пусть <tex>C_n<// если tex> — цикл длины <mathtex>right \leqslant leftn</mathtex> возвращает . Тогда хроматичсекий многочлен цикла <mathtex>leftP(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</mathtex>.|proof= Рассмотрим случай <tex>n = 3<// если tex>: <mathtex>P(C_3, x) = x(x - 1)(x - 2) = (x \leqslant T[left]- 1)(x^2 - x) = (x - 1)^3 + (-1)^3(x - 1)</mathtex>, возвращает что удовлетворяет формулировке теоремы.<math>left</mathbr> // иначе возвращает наибольший индекс Пусть <mathtex>iP(С_k, x) = (x - 1)^k + (-1)^k(x - 1)</mathtex> из отрезка .<mathbr>[left; right]Рассмотрим случай </mathtex> такой, что n = k + 1<math/tex>array. По теореме о [[i - 1#.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|рекурентной формуле для хроматических многочленов]] : < x</mathtex> binarySearchP(C_{k + 1}, x) = P(C_{k + 1} \setminus e, arrayx) - P(C_{k + 1} / e, left, rightx) </tex> (где <tex>e</ слияние tex> — любое ребро <mathtex>T[left_C_{k + 1} \dots right_</tex>).Заметим, что граф <tex>C_{k + 1}]/ e</tex> изоморфен <tex>C_k</mathtex> и . Заметим, что граф <mathtex>T[left_C_{2k + 1} \dots right_{2}]setminus e</mathtex> в является [[#.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|простой цепью]].Тогда <mathtex>A[left_P(C_{3k + 1} \dots right_, x)=P(T_{k + 1} , x)-P(C_k, x)=x(x-1)^k-(x-1)^k-(-1)^k(x-1)=</tex><tex>(x- left_1)^{k+1} + right_(-1)^{2k+1} (x- left_1)</tex>.}}=== Хроматический многочлен колеса ==={2}]{Определение|definition=Колесо — это граф с <tex>n</mathtex> mergeMTвершинами (T, left<mathtex>_{1}n \le 4</mathtex>), rightобразованный соединением единственной вершины со всеми вершинами (<mathtex>_{n - 1</tex>)-цикла.}}Пусть <tex>W_n</mathtex>, left— колесо с <mathtex>_{2}n</mathtex>, rightвершинами. Выбрав и зафиксировав один из <mathtex>_{2}x</mathtex>цветов на вершине, Aсвязнной со всеми остальными, leftимеем <mathtex>_P_{3C_{n - 1}}(x - 1) </mathtex>вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса <tex>P_{W_n}(x): = x \cdot P_{C_{n<math>_- 1}}(x - 1) = x((x - 2)^{(n - 1)}- (-1)^n(x - 2))</mathtex> .=== Хроматический многочлен дерева === right{{Теорема|about=хроматический многочлен дерева|statement=Граф <tex>G</tex> с <mathtex>_{1}n</mathtex> - leftвершинами является деревом тогда и только тогда, когда <mathtex>_P(G,x)=x(x-1)^{n-1}</mathtex> + 1.|proof= n<mathtex>_{2}\Rightarrow</mathtex><br> = rightСначала покажем, что хроматический многочлен любого дерева <mathtex>_{2}T</mathtex> - leftс <mathtex>_{2}n</mathtex> + 1 if nвершинами есть <mathtex>_x(x-1)^{n-1}</mathtex> .Доказательство индукцией по числу < tex>n<math/tex>. Для <tex>_{2}n=1</mathtex>: swap(leftи <mathtex>_{1}n=2</mathtex>результат очевиден. Предположим, leftчто <mathtex>_P(T',x)=x(x-1)^{n-2}</mathtex>) swap(rightдля любого дерева <mathtex>_{1}T'</mathtex>, rightс количеством вершин равным <mathtex>_{2}n-1</mathtex>) swap(n. Пусть <mathtex>_{1}uv</mathtex>, n— ребро дерева <mathtex>_{2}T</mathtex>) if n, такое что <mathtex>_{1}v</mathtex> == 0: return else midявляется висячей вершиной. Хроматический многочлен дерева <mathtex>_{1}T</mathtex> = (leftбез ребра <mathtex>_{1}uv</mathtex> + rightравен <mathtex>_P(T/uv,x)=x(x-1)^{1n-2}</mathtex>) / 2 midпо нашему предположению. Вершину <mathtex>_{2}v</mathtex> = binarySearch(T[midможно окрасить <mathtex>_{x-1}</mathtex>]способом, T, leftтак как её цвет должен только лишь отличаться от цвета вершины <mathtex>_{2}u</mathtex>, right. Итого: <mathtex>_P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{2n-1}</mathtex>.<br>) mid<mathtex>_{3}\Leftarrow</mathtex><br> = leftОбратно, пусть <mathtex>_{3}G</mathtex> + (mid— граф, у которого <mathtex>_P(G,x)=x(x-1)^{n-1}</mathtex>. Тогда верны два следующих утверждения:<ol> <li> - leftГраф <mathtex>_{1}G</mathtex>связен, потому что если было бы две компоненты связности (или больше) + , то <tex>P(midG,x)</tex> делился бы на <mathtex>_{x^2}</mathtex> - leftбез остатка.<mathbr />_{2}</mathli>) A[mid <li>В графе <mathtex>_{3}G</mathtex>] = T[midколичество рёбер равно <mathtex>_{n-1}</mathtex>, так как по одной из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена] '''spawn''' mergeMT(T], теорема 4), leftколичество рёбер в графе соответствует коэффициенту при <mathtex>_x^{n-1}</mathtex>, midвзятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<br /><mathtex>_{P(G,x)=x(x-1)^{n-1}</math> =x\left(x^{n-1}-{n- 1, left<math>_\choose 1}x^{n-2}</math>, mid<math>_+{n-1 \choose 2}</math> x^{n-3}-...+(- 1, A, left<math>_)^{3n-1}</math>\right) mergeMT=x^{n}-(T, mid<math>_n-1)x^{n-1}</math> + ...+(-1, right<math>_)^{n-1}x}</tex><br /math>, mid<math/li>_{2}</mathol>, rightИз этих двух утверждений (связность и <mathtex>_{2}n-1</mathtex>ребро) следует, A, midчто граф <mathtex>_{3}G</mathtex> + является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1и 3). '''sync'''}}
Оценим время выполнения данного алгоритма сверху при возможности запускать неограниченное количество потоков независимо друг от друга. Оба массива содержат <math>n_== Коэффициенты хроматического многочлена =={{Теорема|about=1} + n_{2} |statement= nСвободный член хроматического многочлена равен <tex>0</mathtex> элементов. К моменту рекурсивных вызовов |proof=По определению хроматического многочлена графа <mathtex>n_{2} \leqslant n_{1}G</mathtex>, значит, его значение в точке <mathtex>n_{2} = 2 * n_{2} / 2 \leqslant (n_{1} + n_{2}) / 2 = n / 2x</mathtex>. В худшем случае один из двух рекурсивных вызовов сольет равно количеству способов раскрасить вершины <mathtex>n_{1} / 2G</mathtex> элементов правильным образом в <mathtex>T[left_{1} \dots right_{1}]x</mathtex> с цветов. Количество способов раскрасить граф в <mathtex>n_{2}0</mathtex> элементами цветов равно <mathtex>T[left_{2} \dots right_{2}]0</mathtex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно . То есть <mathtex>n_{1} / 2 + n_{2} \leqslant n_{1} / 2 + n_{2} / 2 + n_{2} / 2 = P(n_{1} + n_{2}G,0) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 * n / 40</mathtex>. Так как рекурсивные вызовы функции выполняются параллельноИз этого следует, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это что <mathtex>TP(3 * n / 4G,x)</mathtex>. Тогда сумарное время работы алгоритма слияния будет равно кратен <mathtex>Tmerge(n) = Tmerge(3 * n / 4) + \Theta(\log(n)) = \Theta(\log^2(n))x</mathtex>, т.к. асимпототика каждого вызова функции - следовательно его свободный член равен <mathtex>\Theta(\log(n))0</mathtex>, т.е. время, затрачиваемое на бинарный поиск. }}
{{Теорема|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> и <mathtex>A[leftA \dots rightA]v</mathtex> в одну и помещающего отсортированный массив удалением возникших при этом кратных ребер.Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/><mathtex>B[leftB P(G,x) = {P(K_{n},x) + a_{1}P(K_{n-1},x) + a_{2}P(K_{n-2},x) + \ldots = x^{\dots leftB underline{n}} + rightA a_{1}x^{\underline{n- leftA]1}}+a_{2}x^{\underline{n-2}}+\ldots}</tex><br/math>Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.}}
mergeSortMT2(A, leftA, rightA, B, leftB):{{Теорема n |about= r - p + 1 if n 3|statement=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof= 1: B[leftB] = A[leftA]Индукция по количеству вершин.<br/> else'''База индукции:'''<br/> создадим новый массив T[1 Теорема верна для графа <mathtex>\dotsG</mathtex> из одной вершины, потому что <tex> n] mid = P(leftA + rightAG,x) =x</tex>.<br/ 2 newMid = mid - leftA + 1> '''spawnИндукционный переход''' mergeSortMT2(A<tex>n \to n+1)</tex>:<br/>Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, leftAто есть <tex>G</tex> является <tex>O_{n+1}</tex>, midто его хроматический многочлен <tex>P(G, Tx)=x^{n+1}</tex> обладает доказываемым свойством. Теперь предположим, что для всех <tex>(n+1,m) mergeSortMT2</tex>-графов теорема верна. Возьмем <tex>(An+1, mid 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}, rightAx)=P(G, Tx)-P(G_{2}, newMid 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/> '''sync'''<tex>{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}</tex> ,<br/> mergeMT<tex>{P(TG_{2}, x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}</tex> , newMid<br/>где <tex>a_{1}</tex>, newMid <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}, Bx)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots</tex>.Видно, leftB)что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}}
Оценим данный алгоритм сверху при условии{{Теорема|about=4|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3)''' видно, что возможен запуск неограниченного при увеличении количества независимых потоковребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Из предыдущих пунктов Так как для пустого графа второй коэффициент равен <tex>0<math/tex>TmergeSort(n) , то утверждение верно для любого графа.}} == Источники информации == TmergeSort(n / * Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2) + Tmerge-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (nУчебники для вузов. Специальная литература) = TmergeSort(n / . ISBN 978-5-8114-1068-2) + \Theta(\log^2(n)) = \Theta(\log^3(n))</math>* Харари Ф. — Теория графов: Изд. 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 {{---}} Хроматический многочлен]] [[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]
Анонимный участник

Навигация