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

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлены хроматические многочлены цикла и колеса)
(больше англоязычных терминов)
Строка 14: Строка 14:
  
 
=== Хроматический многочлен цикла ===
 
=== Хроматический многочлен цикла ===
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P_{С_n} = (x - 1)^n + (-1)^n(x - 1)</tex>
+
Пусть <tex>C_n</tex> — цикл длины <tex>n</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_{С_n} = (x - 1)^n + (-1)^n(x - 1)</tex>
  
 
=== Хроматический многочлен колеса ===
 
=== Хроматический многочлен колеса ===
Строка 22: Строка 22:
 
=== Хроматический многочлен дерева ===
 
=== Хроматический многочлен дерева ===
 
{{Определение
 
{{Определение
|definition='''Стягивание ребра''' — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
+
|definition='''Стягивание ребра''' (edge contraction) — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=

Версия 21:59, 24 ноября 2014

Определение:
Пусть дан фиксированный граф [math]G[/math] и фиксированное число красок [math]x[/math]. Количество способов правильной [math]x[/math]раскраски графа [math]G[/math] называется хроматическим многочленом (chromatic polynomial). Обозначение: [math]P(G,x)[/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) — регулярный граф степени 0, т.е. граф без рёбер.

[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]C_n[/math] — цикл длины [math]n[/math]. По рекурентной формуле для хроматических сногочленов Тогда хроматичсекий многочлен цикла [math]P_{С_n} = (x - 1)^n + (-1)^n(x - 1)[/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].

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

Определение:
Стягивание ребра (edge contraction) — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за [math]G/uv[/math] граф, полученный из графа [math]G[/math] стягиванием ребра [math]uv[/math].
Теорема (хроматический многочлен дерева):
Граф [math]G[/math] с [math]n[/math] вершинами является деревом тогда и только тогда, когда [math]P(G,x)=x(x-1)^{n-1}[/math].
Доказательство:
[math]\triangleright[/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]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]

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

Теорема:
Пусть [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]

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

Теорема (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