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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показано 20 промежуточных версий 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 из раздела [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2 слияние двух массивов].<br>
+
'''Следствие:'''
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <math>T(n) = T(n / 2) + \Theta(n) = \Theta(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
+
Хроматический многочлен любого графа <tex>G</tex> равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе <tex>G</tex>.
  
===Многопоточное слияние===
+
{{Теорема
Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов <math>T[left_{1} \dots right_{1}]</math> и <math>T[left_{2} \dots right_{2}]</math> в массив <math>A[left_{3} \dots right_{3}]</math>:
+
|statement=
# Убедимся, что размер <math>T[left_{1} \dots right_{1}]</math> больше либо равен размеру <math>T[left_{2} \dots right_{2}]</math>
+
Пусть <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>.
# Вычислим <math>x = T[mid_{1}]</math> - середину первого массива (<math>x</math> также является и медианой этого массива)
+
|proof=
# При помощи бинарного поиска найдем <math>mid_{2}</math> такое, что <math>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</math>
+
Следует из предыдущей теоремы.
# <math>mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</math>
+
}}
# <math>A[mid_{3}] = x</math>
 
# Сольем <math>T[right_{1} \dots mid_{1} - 1]</math> и <math>T[right_{2} \dots mid_{2}]</math> в <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>
 
Рассмотрим псевдокод данного алгоритма:
 
  
    // если <math>right \leqslant left</math> возвращает <math>left</math>
+
== Примеры хроматических многочленов ==
    // если <math>x \leqslant T[left]</math>, возвращает <math>left</math>
+
=== Хроматический многочлен полного графа ===
    // иначе возвращает наибольший индекс <math>i</math> из отрезка <math>[left; right]</math> такой, что <math>array[i - 1] < x</math>
+
<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)
 
   
 
    // слияние <math>T[left_{1} \dots right_{1}]</math> и <math>T[left_{2} \dots right_{2}]</math> в <math>A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</math>
 
    mergeMT(T, left<math>_{1}</math>, right<math>_{1}</math>, left<math>_{2}</math>, right<math>_{2}</math>, A, left<math>_{3}</math>):
 
    n<math>_{1}</math> = right<math>_{1}</math> - left<math>_{1}</math> + 1
 
    n<math>_{2}</math> = right<math>_{2}</math> - left<math>_{2}</math> + 1
 
    if n<math>_{1}</math> < n<math>_{2}</math>:
 
        swap(left<math>_{1}</math>, left<math>_{2}</math>)
 
        swap(right<math>_{1}</math>, right<math>_{2}</math>)
 
        swap(n<math>_{1}</math>, n<math>_{2}</math>)
 
   
 
    if n<math>_{1}</math> == 0:
 
        return
 
    else
 
        mid<math>_{1}</math> = (left<math>_{1}</math> + right<math>_{1}</math>) / 2
 
        mid<math>_{2}</math> = binarySearch(T[mid<math>_{1}</math>], T, left<math>_{2}</math>, right<math>_{2}</math>)
 
        mid<math>_{3}</math> = left<math>_{3}</math> + (mid<math>_{1}</math> - left<math>_{1}</math>) + (mid<math>_{2}</math> - left<math>_{2}</math>)
 
        A[mid<math>_{3}</math>] = T[mid<math>_{1}</math>]
 
        '''spawn''' mergeMT(T, left<math>_{1}</math>, mid<math>_{1}</math> - 1, left<math>_{2}</math>, mid<math>_{2}</math> - 1, A, left<math>_{3}</math>)
 
        mergeMT(T, mid<math>_{1}</math> + 1, right<math>_{1}</math>, mid<math>_{2}</math>, right<math>_{2}</math>, A, mid<math>_{3}</math> + 1)
 
        '''sync'''
 
  
Оценим время выполнения данного алгоритма сверху при возможности запускать неограниченное количество потоков независимо друг от друга. Оба массива содержат <math>n_{1} + n_{2} = n</math> элементов. К моменту рекурсивных вызовов <math>n_{2} \leqslant n_{1}</math>, значит, <math>n_{2} = 2 * n_{2} / 2 \leqslant (n_{1} + n_{2}) / 2 = n / 2</math>. В худшем случае один из двух рекурсивных вызовов сольет <math>n_{1} / 2</math> элементов <math>T[left_{1} \dots right_{1}]</math> с <math>n_{2}</math> элементами <math>T[left_{2} \dots right_{2}]</math> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно <math>n_{1} / 2 + n_{2} \leqslant n_{1} / 2 + n_{2} / 2 + n_{2} / 2 = (n_{1} + n_{2}) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 * n / 4</math>. Так как рекурсивные вызовы функции выполняются параллельно, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <math>T(3 * n / 4)</math>. Тогда суммарное время работы алгоритма слияния будет равно <math>Tmerge(n) = Tmerge(3 * n  / 4) + \Theta(\log(n)) = \Theta(\log^2(n))</math>, т.к. асимптотика каждого вызова функции - <math>\Theta(\log(n))</math>, т.е. время, затрачиваемое на бинарный поиск.  
+
=== Хроматический многочлен нуль-графа ===
 +
{{Определение
 +
|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>).
  
===Сортировка с многопоточным слиянием===
+
=== Хроматический многочлен простой цепи ===
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <math>A[leftA \dots rightA]</math> и помещающего отсортированный массив в <math>B[leftB \dots leftB + rightA - leftA]</math>
+
Пусть <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 <math>\dots</math> 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).
 +
}}
  
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <math>TmergeSort(n) = TmergeSort(n / 2) + Tmerge(n) = TmergeSort(n / 2) + \Theta(\log^2(n)) = \Theta(\log^3(n))</math>.
+
== Коэффициенты хроматического многочлена ==
 +
{{Теорема
 +
|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>.
 +
}}
  
===Литература===
+
{{Теорема
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. - Introduction to Algorithms, Third Edition
+
|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> и <tex>v</tex> в одну и удалением возникших при этом кратных ребер.
 +
Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>
 +
<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 — Хроматический многочлен