Обсуждение участника:AKhimulya — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 18 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Многопоточная сортировка слиянием ==
+
{{Определение
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
+
|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='''Стягивание ребра''' (англ. ''edge contraction'') — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
        '''spawn''' mergeSortMT(array, left, mid)
+
{{Теорема
        mergeSortMT(array, mid + 1, right)
+
|statement=
        '''sync'''
+
Пусть <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=
        merge(array, left, mid, right)
+
Рассмотрим все произвольные раскраски графа <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>.
 +
}}
 +
'''Замечание:'''
 +
Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.
  
В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [[Сортировка слиянием#.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>T(n) = T(\frac{n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
+
Хроматический многочлен любого графа <tex>G</tex> равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе <tex>G</tex>.
  
===Многопоточное слияние===
+
{{Теорема
Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex>T[left_{1} \dots right_{1}]</tex> и <tex>T[left_{2} \dots right_{2}]</tex> в массив <tex>A[left_{3} \dots right_{3}]</tex>:
+
|statement=
# Убедимся, что размер <tex>T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex>T[left_{2} \dots right_{2}]</tex>
+
Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\backslash uv</tex> и <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
# Возьмем <tex>x = T[mid_{1}]</tex> - середину первого массива (<tex>x</tex> также является и медианой этого массива)
+
|proof=
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex>mid_{2}</tex> такое, что <tex>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
+
Следует из предыдущей теоремы.
# <tex>mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
+
}}
# <tex>A[mid_{3}] = 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>
+
<tex>P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}</tex>, так как первую вершину полного графа <tex>K_{n}</tex> можно окрасить в любой из <tex>x</tex> цветов, вторую — в любой из оставшихся <tex>x-1</tex> цветов и т. д. Очевидно, что если <tex>x</tex> меньше <tex>n</tex>, то и многочлен равен <tex>0</tex>, так как один из его множителей <tex>0</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> = binarySearch(T[mid<tex>_{1}</tex>], T, left<tex>_{2}</tex>, right<tex>_{2}</tex>)
 
            mid<tex>_{3}</tex> = left<tex>_{3}</tex> + (mid<tex>_{1}</tex> - left<tex>_{1}</tex>) + (mid<tex>_{2}</tex> - left<tex>_{2}</tex>)
 
            A[mid<tex>_{3}</tex>] = T[mid<tex>_{1}</tex>]
 
            '''spawn''' mergeMT(T, left<tex>_{1}</tex>, mid<tex>_{1}</tex> - 1, left<tex>_{2}</tex>, mid<tex>_{2}</tex> - 1, A, left<tex>_{3}</tex>)
 
            mergeMT(T, mid<tex>_{1}</tex> + 1, right<tex>_{1}</tex>, mid<tex>_{2}</tex>, right<tex>_{2}</tex>, A, mid<tex>_{3}</tex> + 1)
 
            '''sync'''
 
  
Оба массива содержат <tex>n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex>n_{2} \leqslant n_{1}</tex>, значит,<br><tex>n_{2} = 2 \cdot \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}</tex>.<br>
+
=== Хроматический многочлен нуль-графа ===
В худшем случае один из двух рекурсивных вызовов сольет <tex>\frac{n_{1}}{2}</tex> элементов <tex>T[left_{1} \dots right_{1}]</tex> с <tex>n_{2}</tex> элементами <tex>T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br>
+
{{Определение
<tex>\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>\Theta(\log(n))</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex>T_{merge}(n) = T_{merge}(\frac{3}{4}n) + \Theta(\log(n)) = \Theta(\log^2(n))</tex>
+
|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>0</tex>, т.е. граф без рёбер.}}
 +
<tex>P(O_{n},x)=x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>O_{n}</tex> можно независимо окрасить в любой из <tex>x</tex> цветов.<br>
 +
'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).
  
===Сортировка с многопоточным слиянием===
+
=== Хроматический многочлен простой цепи ===
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex>A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex>B[leftB \dots leftB + rightA - leftA]</tex>
+
Пусть <tex>T_n</tex> — простая цепь, состоящая из <tex>n</tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</tex> цветов, вторую и последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P(T_n, x) = x(x - 1) ^ {n - 1}</tex>.
  
    mergeSortMT2(A, leftA, rightA, B, leftB):
+
=== Хроматический многочлен цикла ===
        n = r - p + 1
+
{{Теорема
        '''if''' n == 1
+
|about=
            B[leftB] = A[leftA]
+
хроматический многочлен цикла
        '''else'''
+
|statement=
            создадим новый массив T[1 <tex>\dots</tex> n]
+
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.
            mid = (leftA + rightA) / 2
+
|proof=
            newMid = mid - leftA + 1
+
Рассмотрим случай <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>
            '''spawn''' mergeSortMT2(A, leftA, mid, T, 1)
+
Пусть <tex>P(С_k, x) = (x - 1)^k + (-1)^k(x - 1)</tex>.<br>
            mergeSortMT2(A, mid + 1, rightA, T, newMid + 1)
+
Рассмотрим случай <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>).
            '''sync'''
+
Заметим, что граф <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|простой цепью]].
            mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
+
Тогда <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>.
 +
}}
 +
=== Хроматический многочлен колеса ===
 +
{{Определение
 +
|definition=Колесо — это граф с <tex>n</tex> вершинами (<tex>n \le 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=
 +
хроматический многочлен дерева
 +
|statement=
 +
Граф <tex>G</tex> с <tex>n</tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)=x(x-1)^{n-1}</tex>.
 +
|proof=
 +
<tex>\Rightarrow</tex><br>
 +
Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-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)=x(x-1)^{n-1}</tex>.<br>
 +
<tex>\Leftarrow</tex><br>
 +
Обратно, пусть <tex>G</tex> — граф, у которого <tex>P(G,x)=x(x-1)^{n-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\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> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1 и 3).
 +
}}
  
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex>T_{mergeSort}(n) = T_{mergeSort}(\frac{n}{2}) + T_{merge}(n) = T_{mergeSort}(\frac{n}{2}) + \Theta(\log^2(n)) = \Theta(\log^3(n))</tex>.
+
== Коэффициенты хроматического многочлена ==
 +
{{Теорема
 +
|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>.
 +
}}
  
===Реализация===
+
{{Теорема
Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex>N_{ind}</tex>. Допустим, <tex>n</tex> много больше <tex>N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. на которых Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
+
|about=
::'''Сортировка с однопоточным слиянием''' будет иметь асимптотику <tex>\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}) + n) = \Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>:
+
2
::::<tex>\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex> операций нужно на последовательную сортировку массива длиной <tex>\frac{n}{N_{ind}})</tex>.
+
|statement=
::::<tex>\Theta(n)</tex> необходимо на последовательное слияние.
+
Старший коэффициент хроматического многочлена равен <tex>1</tex>.
::'''Многопоточное слияние''' будет работать за <tex>\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))=\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)})</tex>:
+
|proof=
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex>min(N_{ind}, \log(n))</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex>\Theta(\log(n))</tex>
+
Воспользуемся рекуррентной формулой:<br/>
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
+
<tex>P(G,x) = P(G_{1},x) + P(G_{2},x)</tex>,<br/>
::::<tex>T_{merge}'(n) = 2T_{merge}'(\frac {3}{4}n) + \Theta(\log(n)) = \Theta(n^{(\log_{\frac{4}{3}}2)})</tex>
+
где <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/>
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
+
<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 {{---}} Хроматический многочлен]]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Раскраски графов]]

Текущая версия на 01:30, 25 ноября 2014

Определение:
Пусть дан фиксированный граф [math]G[/math] и фиксированное число красок [math]x[/math]. Количество способов правильной [math]x[/math]раскраски графа [math]G[/math] называется хроматическим многочленом (англ. chromatic polynomial). Обозначение: [math]P(G,x)[/math].


Рекуррентные формулы для хроматических многочленов

Определение:
Стягивание ребра (англ. edge contraction) — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за [math]G/uv[/math] граф, полученный из графа [math]G[/math] стягиванием ребра [math]uv[/math].
Теорема:
Пусть [math]u[/math] и [math]v[/math] - несмежные вершины графа [math]G[/math]. Если [math]G_1=G\cup uv[/math], а [math]G_2=G/uv[/math], то [math]P(G,x)=P(G_1,x)+P(G_2,x)[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим все произвольные раскраски графа [math]G[/math]. Рассмотрим те из них, при которых вершины [math]u[/math] и [math]v[/math] окрашены в разные цвета. Если добавить к графу [math]G[/math] ребро [math]uv[/math], то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых [math]u[/math] и [math]v[/math] одного цвета. Все эти раскраски останутся правильными и для графа, полученного из [math]G[/math] слиянием вершин [math]u[/math] и [math]v[/math].
[math]\triangleleft[/math]

Замечание: Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.

Следствие: Хроматический многочлен любого графа [math]G[/math] равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе [math]G[/math].

Теорема:
Пусть [math]u[/math] и [math]v[/math] — смежные вершины графа [math]G[/math]. Если [math]G_1=G\backslash uv[/math] и [math]G_2=G/uv[/math], то [math]P(G,x)=P(G_1,x)-P(G_2,x)[/math].
Доказательство:
[math]\triangleright[/math]
Следует из предыдущей теоремы.
[math]\triangleleft[/math]

Примеры хроматических многочленов

Хроматический многочлен полного графа

[math]P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}[/math], так как первую вершину полного графа [math]K_{n}[/math] можно окрасить в любой из [math]x[/math] цветов, вторую — в любой из оставшихся [math]x-1[/math] цветов и т. д. Очевидно, что если [math]x[/math] меньше [math]n[/math], то и многочлен равен [math]0[/math], так как один из его множителей [math]0[/math].

Хроматический многочлен нуль-графа

Определение:
Нуль-граф (пустой граф, вполне несвязный граф; англ. null graph, empty graph, edgeless graph) — регулярный граф степени [math]0[/math], т.е. граф без рёбер.

[math]P(O_{n},x)=x^{n}[/math], так как каждую из [math]n[/math] вершин нулевого графа [math]O_{n}[/math] можно независимо окрасить в любой из [math]x[/math] цветов.
Примечание: Нулевой граф [math]O_{n}[/math] также можно обозначать [math]\overline{K_{n}}[/math] (дополнительный граф для полного графа [math]K_{n}[/math]).

Хроматический многочлен простой цепи

Пусть [math]T_n[/math] — простая цепь, состоящая из [math]n[/math] вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из [math]x[/math] цветов, вторую и последующие в один из [math]x - 1[/math] цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда [math]P(T_n, x) = x(x - 1) ^ {n - 1}[/math].

Хроматический многочлен цикла

Теорема (хроматический многочлен цикла):
Пусть [math]C_n[/math] — цикл длины [math]n[/math]. Тогда хроматичсекий многочлен цикла [math]P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим случай [math]n = 3[/math]: [math]P(C_3, x) = x(x - 1)(x - 2) = (x - 1)(x^2 - x) = (x - 1)^3 + (-1)^3(x - 1)[/math], что удовлетворяет формулировке теоремы.
Пусть [math]P(С_k, x) = (x - 1)^k + (-1)^k(x - 1)[/math].
Рассмотрим случай [math]n = k + 1[/math]. По теореме о рекурентной формуле для хроматических многочленов: [math]P(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)[/math] (где [math]e[/math] — любое ребро [math]C_{k + 1}[/math]). Заметим, что граф [math]C_{k + 1} / e[/math] изоморфен [math]C_k[/math]. Заметим, что граф [math]C_{k + 1} \setminus e[/math] является простой цепью.

Тогда [math]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)=[/math][math](x-1)^{k+1}+(-1)^{k+1}(x-1)[/math].
[math]\triangleleft[/math]

Хроматический многочлен колеса

Определение:
Колесо — это граф с [math]n[/math] вершинами ([math]n \le 4[/math]), образованный соединением единственной вершины со всеми вершинами ([math]n - 1[/math])-цикла.

Пусть [math]W_n[/math] — колесо с [math]n[/math] вершинами. Выбрав и зафиксировав один из [math]x[/math] цветов на вершине, связнной со всеми остальными, имеем [math] P_{C_{n - 1}}(x - 1) [/math] вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса [math]P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2))[/math].

Хроматический многочлен дерева

Теорема (хроматический многочлен дерева):
Граф [math]G[/math] с [math]n[/math] вершинами является деревом тогда и только тогда, когда [math]P(G,x)=x(x-1)^{n-1}[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]
Сначала покажем, что хроматический многочлен любого дерева [math]T[/math] с [math]n[/math] вершинами есть [math]x(x-1)^{n-1}[/math]. Доказательство индукцией по числу [math]n[/math]. Для [math]n=1[/math] и [math]n=2[/math] результат очевиден. Предположим, что [math]P(T',x)=x(x-1)^{n-2}[/math] для любого дерева [math]T'[/math] с количеством вершин равным [math]n-1[/math]. Пусть [math]uv[/math] — ребро дерева [math]T[/math], такое что [math]v[/math] является висячей вершиной. Хроматический многочлен дерева [math]T[/math] без ребра [math]uv[/math] равен [math]P(T/uv,x)=x(x-1)^{n-2}[/math] по нашему предположению. Вершину [math]v[/math] можно окрасить [math]x-1[/math] способом, так как её цвет должен только лишь отличаться от цвета вершины [math]u[/math]. Итого: [math]P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{n-1}[/math].
[math]\Leftarrow[/math]
Обратно, пусть [math]G[/math] — граф, у которого [math]P(G,x)=x(x-1)^{n-1}[/math]. Тогда верны два следующих утверждения:

  1. Граф [math]G[/math] связен, потому что если было бы две компоненты связности (или больше), то [math]P(G,x)[/math] делился бы на [math]x^2[/math] без остатка.
  2. В графе [math]G[/math] количество рёбер равно [math]n-1[/math], так как по одной из теорем о коэффициентах хроматического многочлена (Коэффициенты хроматического многочлена, теорема 4), количество рёбер в графе соответствует коэффициенту при [math]x^{n-1}[/math], взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:
    [math]{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}[/math]
Из этих двух утверждений (связность и [math]n-1[/math] ребро) следует, что граф [math]G[/math] является деревом (см. Дерево, эквивалентные определения, утверждения 1 и 3).
[math]\triangleleft[/math]

Коэффициенты хроматического многочлена

Теорема (1):
Свободный член хроматического многочлена равен [math]0[/math].
Доказательство:
[math]\triangleright[/math]
По определению хроматического многочлена графа [math]G[/math], его значение в точке [math]x[/math] равно количеству способов раскрасить вершины [math]G[/math] правильным образом в [math]x[/math] цветов. Количество способов раскрасить граф в [math]0[/math] цветов равно [math]0[/math]. То есть [math]P(G,0)=0[/math]. Из этого следует, что [math]P(G,x)[/math] кратен [math]x[/math], следовательно его свободный член равен [math]0[/math].
[math]\triangleleft[/math]
Теорема (2):
Старший коэффициент хроматического многочлена равен [math]1[/math].
Доказательство:
[math]\triangleright[/math]

Воспользуемся рекуррентной формулой:
[math]P(G,x) = P(G_{1},x) + P(G_{2},x)[/math],
где [math]G_{1}[/math] — граф, полученный из [math]G[/math] добавлением отсутствующего в [math]G[/math] ребра [math]uv[/math], а [math]G_{2}[/math] — граф, полученный из [math]G[/math] слиянием вершин [math]u[/math] и [math]v[/math] в одну и удалением возникших при этом кратных ребер. Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:
[math]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}[/math]

Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный [math]1[/math].
[math]\triangleleft[/math]
Теорема (3):
Коэффициенты хроматического многочлена составляют знакопеременную последовательность.
Доказательство:
[math]\triangleright[/math]

Индукция по количеству вершин.
База индукции:
Теорема верна для графа [math]G[/math] из одной вершины, потому что [math]P(G,x)=x[/math].
Индукционный переход ([math]n \to n+1)[/math]:
Предположим, что теорема верна для всех графов на [math]n[/math] вершинах. Рассмотрим графы на [math]n+1[/math] вершине. Индукционный переход будем доказывать индукцией по количеству ребер графа [math]G[/math]. Если [math]G[/math] не содержит ребер, то есть [math]G[/math] является [math]O_{n+1}[/math], то его хроматический многочлен [math]P(G,x)=x^{n+1}[/math] обладает доказываемым свойством. Теперь предположим, что для всех [math](n+1,m)[/math]-графов теорема верна. Возьмем [math](n+1,m+1)[/math]-граф [math]G_{1}[/math] и его ребро [math]uv[/math]. Обозначим за [math]G[/math] граф, полученный из [math]G_{1}[/math] удалением ребра [math]uv[/math] ([math]G=G_{1}-uv[/math]), а за [math]G_{2}[/math] — граф, полученный из [math]G_{1}[/math] слиянием вершин [math]u[/math] и [math]v[/math]. Тогда из рекуррентной формулы следует:
[math]P(G_{1},x)=P(G,x)-P(G_{2},x)[/math]. Так как [math]G[/math][math](n+1,m)[/math]-граф, а в [math]G_{2}[/math][math]n[/math] вершин, то для [math]G[/math] и [math]G_{2}[/math] теорема верна:
[math]{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}[/math] ,
[math]{P(G_{2},x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}[/math] ,
где [math]a_{1}[/math], [math]a_{2}[/math][math]a_{n+1}[/math], [math]b_{1}[/math], [math]b_{2}[/math][math]b_{n}[/math] — некоторые неотрицательные целые числа. Из этих равенств получаем:
[math]P(G_{1},x)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots[/math].

Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.
[math]\triangleleft[/math]
Теорема (4):
Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.
Доказательство:
[math]\triangleright[/math]
Из доказательства Теоремы (3) видно, что при увеличении количества ребер графа на [math]1[/math], второй коэффициент также увеличивается на [math]1[/math]. Так как для пустого графа второй коэффициент равен [math]0[/math], то утверждение верно для любого графа.
[math]\triangleleft[/math]

Источники информации

  • Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
  • Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. ISBN 978-5-397-00622-4
  • Wikipedia — Chromatic_polynomial
  • Wikipedia — Хроматический многочлен