- •1. Оценки хроматического числа. Теорема Брукса.
- •2. Разбиение чисел на слагаемые. Диаграммы Ферре. Число всех отображений, число сюръективных отображений конечных множеств (элементы в и неразличимы).
- •1. Реберное хроматическое число. Теорема Визинга.
- •Примеры.
- •2. Раскраска карт. Бихроматичность карт.
- •1. Числа Стирлинга второго рода. Первый способ рекуррентного вычисления чисел Стирлинга второго рода.
- •2. Число ребер в планарном графе. Планарность графов и .
- •1. Числа Стирлинга второго рода. Второй способ рекуррентного вычисления чисел Стирлинга второго рода.
- •2.Свойства двойственного графа плоского графа.
2. Число ребер в планарном графе. Планарность графов и .
Следствие 13.6. Для связного планарного (n, m)-графа m 3n – 6 при n 3.
Не теряя общности, будем считать, что G — плоский граф. Прежде всего заметим, что всякое ребро плоского графа либо разделяет две различные грани, либо является мостом (см. свойство 4). Поскольку G — граф без петель и кратных ребер, то всякая грань ограничена по крайней мере тремя ребрами (исключение составляет лишь случай, когда G — дерево с тремя вершинами, но для такого графа неравенство m 3n – 6 очевидно). Поэтому число 3f является оценкой снизу удвоенного числа ребер графа G, т. е. 3f 2. Отсюда, учитывая формулу Эйлера f = m – n + 2, получаем требуемое неравенство.
Утверждение 13.7. Граф K5 не планарен.
Действительно, для графа K5 имеем , . Поэтому неравенство превращается в неверное: 9 > 10, т. е. граф K5 не может быть планарным.
Утверждение 13.8. Граф K3,3 не планарен.
Для рассматриваемого графа n = 6, m = 9. Поэтому, если бы он был планарным, то для любой его плоской укладки выполнялось бы f = 5 согласно следствию 13.5. В то же время всякая грань двудольного графа K3,3 должна быть ограничена по меньшей мере четырьмя ребрами. Следовательно, 2m 4f, т. е. . Противоречие.
БИЛЕТ 21
1. Числа Стирлинга второго рода. Второй способ рекуррентного вычисления чисел Стирлинга второго рода.
Число разбиений m-элементного множества на k непустых подмножеств обозначим через S(m, k) и будем называть его числом Стирлинга второго рода.
Утверждение 8.1. А. S(m, m) = 1 при m 0.
Б. S(m, 0) = 0 при m > 0.
В. S(m, k) = S(m –1, k – 1) + kS(m –1, k) при 0 < k < m.
Пункты «А» и «Б» очевидны. Для доказательства пункта «В» заметим, что множество R всех разбиений X = {x1, x2,…, xm} на n частей распадается на множества R1 = { R | одноэлементное множество {xm} является элементом разбиения } и R2 = R \ R1. Очевидно, | R1 | = S(m – 1, k – 1). Поставим в соответствие каждому разбиению R2 разбиение ’ множества X \ {xm}, полученное из удалением элемента xm из той части, которой он принадлежал. Поскольку каждое разбиение ’ множества X \ {xm} будет поставлено в соответствие ровно k разбиениям множества X (образованным из ’ путем добавления xm к какой-нибудь из k частей), то | R2 | = kS(m – 1, k).
Доказанные равенства позволяют вычислять значения по треугольнику Стирлинга для больших значений m и k. В таблице 3 приводятся числа Стирлинга второго рода для 0 m, k 8 .
|
|||||||||
m \ k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
1 |
|
|
|
|
|
|
|
2 |
0 |
1 |
1 |
|
|
|
|
|
|
3 |
0 |
1 |
3 |
1 |
|
|
|
|
|
4 |
0 |
1 |
7 |
6 |
1 |
|
|
|
|
5 |
0 |
1 |
15 |
25 |
10 |
1 |
|
|
|
6 |
0 |
1 |
31 |
90 |
65 |
15 |
1 |
|
|
7 |
0 |
1 |
63 |
301 |
350 |
140 |
21 |
1 |
|
8 |
0 |
1 |
127 |
966 |
1701 |
1050 |
266 |
28 |
1 |
В этой таблице каждое значение, кроме крайних можно получить как сумму чисел, находящихся над ним, а именно числа, расположенного в точности над ним и умноженного на k, и числа над ним с левой стороны.
Утверждение 8.2. Для любого k 2
Пусть (X1, X2, …, Xk ) — произвольное разбиение X на k непустых подмножеств. Пусть xm Xk
(можно взять и другой элемент, это не существенно). Всего имеется возможностей выбрать подмножество Xk с | Xk | = r и xm Xk . После этого останется S(m – r, k – 1) возможностей разбить оставшееся множество X \ Xk на k – 1 непустых подмножеств. Следовательно,