А.В. Чашкин - Задачи с некоторых семинаров по дискретной математике (1156387)
Текст из файла
Задачи с некоторых семинаров по дискретной математикеПреподаватель — Александр Викторович Чашкин7 семестр, 2005 г.Эти задачи вместе с решениями были записаны и набраны Сергеем Гладких, в дальнейшем текст былнемного перевёрстан DMVN Corporation. Исправлены замеченные опечатки.Последняя компиляция: 26 января 2006 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.1. Булев кубОпределение. Булев куб: {0, 1}n =: Bn =: E2n — множество последовательностей из нулейи единиц длины n.nPРасстояние Хемминга: α, β ∈ {0, 1}n , d(α, β) =|αi −βi | — число несовпадающих координат.i=1PВес набора: ||α|| = w(α) =αi — число ненулевых координат.
k-й слой булевого куба: всенаборы с весом k.Будем говорить, что α 6 β, если для каждого i выполняется αi 6 βi .Два набора α и β будем называть сравнимыми, если α 6 β либо β 6 α, в противном случае —несравнимыми.Цепь — множество попарно сравнимых наборов, антицепь — множество попарно несравнимых.Для сравнимых наборов α и β определим интервал I = {γ|α 6 γ 6 β}, |I| = 2d(α, β) . I такженазывают гранью, а d(α, β) — ее размерностью.Задача 1. Найти число k-мерных подпространств в n-мерном пространстве над Z2 .Решение.
Каждое k-мерное подпространство задается своим базисом. Посчитаем, сколькими способами можно выбрать k линейно независимых векторов в n-мерном булевом пространстве. Для первого вектора имеем 2n − 1 возможностей — можем брать все, кроме нулевого.Для второго 2n − 2 — все, кроме кратных первому.
Для i-го — 2n − 2i−1 — все, кроме линейнойоболочки первых i − 1. таким образом, общее число k-мерных базисов в n-мерном пространстверавно (2n − 1)(2n − 2) . . . (2n − 2k−1 ). Но не все они задают различные подпространства. Числоk-мерных базисов в каждом k-мерно подпространстве равно (2k −1)(2k −2) . . . (2− 2k−1), и все онибудут эквивалентны.
Отсюда получаем, что число k-мерных подпространств равно отношениюэтих чисел, то есть(2n − 1)(2n − 2) . . . (2n − 2k−1).(1)(2k − 1)(2k − 2) . . . (2− 2k−1)Определение. Сферой радиуса k с центром в α в булевом кубе будем называть множествоSk (α) = {β|d(α, β) = k}.1(2)Очевидно, |Sk (α)| = Cnk . Аналогично, шар — это Bk (α) = {β|d(α, β) 6 k}.Задача 2. Найти среднее расстояние между двумя вершинами.Решение. Заметим, что среднее расстояние между двумя вершинами в точности равносреднему расстоянию от некоторой фиксированной вершины до остальных. В качестве такойвершины возьмем (0, .
. . , 0). Сумма расстояний от нее до остальных равнаP фиксированнойkCkn = n2n−1 . Эту величину надо поделить на количество вершин — в результате получимn2n−1= n2 . 2nЗадача 3. Найти число k-мерных граней, проходящих через фиксированную вершину.Ответ: Cnk .Задача 4. Найти число k-мерных подпространств, проходящих через фиксированную вершину.Решение. Вспомним задачу 1. Ситуация та же, только теперь в каждом базисе один вектор(с концом в этой вершине) — фиксирован. То есть из числителя и знаменателя дроби (1) нужноубрать первый сомножитель:(2n − 2)(2n − 3) .
. . (2n − 2k−1).(2k − 2)(2k − 3) . . . (2− 2k−1)(3)Задача 5. Найти порядок дроби (1).Решение.(2n − 1)(2n − 2) . . . (2n − 2k−1)= 2n(n−k) n−kQ(2k − 1)(2k − 2) . . . (2− 2k−1)i=1где Cr =rQi=11−12i. Оценка дробиCnCn−k CknQ1−i=11−12i12ikQi=11−= 2n(n−k)12iCn,Cn−k Ck(4)будет зависеть от отношения k к n. Если k = ō(n),Cnто нам хватит очевидной оценки Cn−k< 2k , так как эта величина не повлияет на порядок.
ВCkобщем случае нам понадобится более точная оценка на Cn . Получим ее.Cn = Cn−1 −Cn−1Cn−2 Cn−2Cn−2= Cn−2 − n−1 − n + 2n−1 >n222211111> Cn−2 − Cn−2+ n > . . . > C2 − C2+ . . . + n > . (5)n−122424Таким образом,Cn166 4.Cn−k CkCk(6)Определение. Эллипсом с фокусами α, β будем называть, как обычно, множество всехнаборов с условием, чтобы сумма расстояний до фокусов была равна некоторой фиксированнойконстанте k.Задача 6. Найти количество наборов в n-мерном булевом эллипсе.Решение.
Итак, эллипс Vk (α, β) = {γ|d(α, γ) + d(β, γ) = k}. Будем рассматривать нетривиальный случай, когда l = d(α, β) < k. Зафиксируем те n − l координат, которые являются2общими у α и β и рассмотрим соответствующее подпространство El (α, β). В нем, кроме самихфокусов, будет 2l −2 элементов. Сумма расстояний от каждого из них до фокусов будет равна l.Зафиксируем один из таких элементов γ, и рассмотрим подпространство En−l (γ) всего булевогокуба, ортогональное к El и проходящее через γ. Для любого элемента γ ′ из этого подпространства сумма его расстояний до фокусов будет равна l + d(γ, γ ′ ).
Значит, в нашем эллипсе будутлежать такие γ ′ , для которых d(γ, γ ′ ) = k − l. Их число — это число элементов сферы радиусаn−llk − l в (n − l)-мерном пространстве, то есть Cn−lk−l . Таким образом мы получили (2 − 2)Ck−lнаборов, лежащих в Vk . Однако, нерассмотренными остались еще элементы подпространствEn−l (α) и En−l (β), порождённых самими фокусами.
Пусть α′ ∈ En−l (α) и d(α, α′) = a, тогдаd(α, α′) + d(β, α′) = 2a + l. То есть нас интересуют те α′ , для которых 2a = k − l. Если k − lнечетно, таких не существует вовсе, а если четно, их будет Cn−lk−l . Таким образом, окончательный2ответ будет выглядеть так:(0,k − l = 2m + 1;n−l|Vk | = (2l − 2)Ck−l+ Cn−l , k − l = 2m.(7)k−l22.
Булев куб. Графы.Определение. k-м слоем булевого куба {0, 1}n называют множество всех его вершин, вескоторых (число ненулевых координат) равен k.Пусть A — подмножество k-го слоя, причем k < n2 . Подмножество B k +1-го слоя называетсятенью множества A, если расстояние (число различающихся координат) между любыми двумявершинами этих множеств равно 1.Задача 1. Доказать, что |A|(n − k) 6 |B| · (k + 1).Решение. Рассмотрим множество всех ребер, соединяющих вершины из A с вершинами изB.
Так как из каждой вершины, лежащей в A, выходит ровно n − k ребер (столько, скольконулевых координат у этой вершины), то их общее число равно |A|(n − k). С другой стороныиз каждой вершины, лежащей в B выходит не более |B|(k + 1) ребер (по числу ее ненулевыхкоординат), а значит |A|(n − k) 6 |B|(k + 1), что и требовалось доказать. Определение. Будем называть антицепью набор вершин, любые две из которых несравнимы.Задача 2. Мощность максимальной антицепи в Bn не превышает Cn[n/2] .Решение. Для произвольной антицепи L построим антицепь, содержащую не меньше элементов, чем в было в исходной, и при этом не превышающей по мощности Cn[n/2] .
Пусть A1 —Tподмножество элементов L, лежащее на первом слое, а B2 — его тень. Заметим, что A2 B2 = ∅,так как иначе A2 содержало бы элементы, сравнимые с элементами из A1 . Более того, элементыL с весом больше 2х должны быть несравнимы с элементами B2 , так как если бы они былибольше каких-то элементов из B2 , то тем более были бы больше соответствующих элементовиз A1 .
Все это означает, что исключив из L множество A1 и добавив вместо него B2 , мы сноваполучим антицепь, причем с мощностью не меньшей, чем мощность L. Продолжая действоватьаналогичным образом, мы рано или поздно поднимемся к слою с максимальной мощностью.Такую же операцию произведем, спускаясь сверху. Если n нечетно, из двух максимальных слоев выберем любой, и спроектируем все на него. Получим антицепь с максимальной мощностьюCn[n/2] . 3Определение.
Гранью планарного графа называют цикл, не содержащий внутри себя вершин.Задача 3. Доказать формулу Эйлера В − Р + Г = 2 для графов на плоскости.Решение. Докажем по индукции по числу граней. Если грань одна (база индукции), тоВ − Р = 1 и соотношение выполнено. Пусть теперь утверждение доказано для k граней. Еслиесть k + 1 грань, уберем любое ребро, разделяющее две грани, при этом число граней такжеуменьшится на один и по предположению индукции получим В − (Р − 1) + (Г − 1) = 2, а значити В − Р + Г = 2.
Задача 4. Доказать непланарность K3,3 и K5 .Решение. Предположим, что K3,3 планарен, тогда, согласно формулы Эйлера, он долженсодержать 5 граней. Из каждой вершины K3,3 выходит три ребра, т. е. каждой вершине соответствует 4 грани. Откуда получаем на число вершин следующее условие: В 6 C4Г = C45 = 5,что неверно. Значит, K3,3 не планарен. Непланарность K5 будет доказана в ходе решения следующей задачи. Задача 5. Доказать достаточность пяти красок для раскраски вершин планарного графас условием, чтобы никакие две вершины одного цвета не принадлежали одному ребру.Решение. Доказывать будем по индукции по числу вершин.
Сначала докажем, что найдетсявершина, из которой выходит не более 5 ребер. Пусть Γ1 , . . . , Γm — множество граней графа,B1 , . . . , Bn — множество его вершин, и P1 , . . . , Pk — множество его ребер. Пусть также P (Bi ) —число ребер, выходящих из i-й вершины, а P (Γi) — число ребер, ограничивающих i-ю грань.mPКаждое ребро принадлежит двум граням, следовательноP (Γi) = 2P .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
