Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 59
Текст из файла (страница 59)
3) .) у б. Опенка е тпеораи ерайтое и еетпей 289 6.22. Найти среднее число й-вершинных независимых множеств в графах С из 'й, 6.23. Пусть р(С) целочисленный неотрицательный параметр, а Р(п) его сРеднее значение длЯ гРафов С из тйп. Показать, что если 11ш р(п) = О, то для почти всех графов р(С) = О. 6.24. Используя неравенство Чебышева (2), показать, что у почти всех (и, т(п))-графов, где ти(п) = [п,т1п(п1тттт)), число изолированных вершин равно п(1 — е(п)), где 11ш е(п) = О.
Глава 1Х МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ О 1. Структура граней и-мерного куба. Покрытия и тесты для таблиц Гранью единичного и-мерного куба В" называется множество В",'"''„"' = ((оы ..., о„) е В": ов = оы ..., оа = он). Множество (3е,, 3„) называется направлением, число Й " рангом, а число и — й — размерностью грани В";" „" ". Кооом грани С = = В","; '" называется вектор у(С) длины и, в котором у„= = оз, ..., у,„= пь, а остальные координаты есть --. Например, у(В,",; ' ) = (О 1 ). Одномерные грани называются ребрами куба. Обозначим множество векторов длины п, с координатами из множества (О, 1, ---) через Са. На множестве С" зададим частичный порядок, полагая б < Д, если вектор 13 может быть получен из Н путем замены некоторых (быть может, ни одной) координат набора Н, равных О или 1, на --. Отношение б < 13 между кодами граней С и Н соответствует отношению С С Н между гранями.
Положим ~~ее~~ равным числу прочерков в наборе о и С~,' — — )Н е С": Йсь(! = й!. Тогда Свн = В", С," соответствует множеству ребер куба В", С„' . множеству граней куба В"', имеющих размерность к. Инльервалом 1(а, 13) куба В" называется множество вида (у е Во: Н < у < 13), где Н, ,3 вершины из В" такие, что а < 13. Число рбх,,3) называется размерностью интервала. Пусть М вЂ” матрица с элементами из множества (О, 1). Будем говорить, что строка б матрицы М покрывает некоторый столбец )3, если на их пересечении стоит 1. Матрицу с т строками и п столбцами будем называть матриаей р змернотни т х п.
Подмножество А строк матрицы М называется покрытием (множества столбцов) матрены М, если для каждого столбца матрицы М найдется строка из множества А, покрывающая этот столбец. Покрытие называется кратчайищм, если оно имеет минимальную мощность среди всех покрытий матрицы М. Мощность с)М) кратчайшего покрытия у' Ь Стпрукпзура граней и-верного куба 291 называется глубиной матрицы М.
Пусть каждой строке а матрицы М приписано неотрицательное число иАВ), называемое весом сгпроки Н. Весом лноясесп~ва А строк матрицы М называется число ю(А) = ~~~ ю(сТ). Покрытие А матрицы М называется минаиаль- неА ныл (относительно весовой функции ю), если оно имеет минимальный вес среди всех покрытий матрицы М. Покрытие называется тупикть вьья, если удаление из него любой строки приводит к множеству, не являющемуся покрытием. Покрытие называется грпдпенткым, если оно может быть получено в результате следующей пошаговой продедуры.
На первом пзаге выбирается строка аы имеющая наибольшее число единиц, а из М вычеркиваются строка Йз и все столбцы, имеющие в пересечении с Нз единицу. В результате получается матрица Мы Пусть сделано к шагов, на которых выбрано множество строк Ау = 1аы ..., Пь) и получена матрица Мь.
На (й -1-1)-м шаге в матрице Мь выбирается строка аяеь с наибольшим числом единиц и т. п. Процедура заканчивается, если матрица Мъ не содержит единиц. Полученное при этом множество Ая и является градиентным покрытием. Результат процедуры неоднозначен, поскольку выбор строки на каждом шаге, вообще говоря, не является однозначным. Через Вг(М) будем обозначать максимальную мощность градиентного покрытия матрицы М.
Множество А строк матрицы М называется пзеспзом, если в подматрице, образованной строками из А, столбцы с номерами 1 и у различны, когда столбцы с номерами 1 и у различны в матрице М. Тест называется миншнальнььн, если он имеет минималызую мощность среди всех тестов матрицы. Тест называется тупиковым, если после удаления любой строки получается множество, не являющееся тестом. Количество строк в тесте называется его длиной. 1.1.
Показать, что грань куба В" размерности к является его интервалом размерности к и наоборот. 1.2. Показать следующие утверждения: 1) число различных граней куба В", имеющих заданное направление ~зы ..., 1ь), равно 2ь; 2) две различныо грани одного направления не перегекакьтся; 3) объединение всех граней куба В", имеющих заданное направление, дает весь куб В"'; 4) число всех граней ранга к куба В" равно („) 2"; 5) общее число граней куба В" равно 3"; 6) число граней размерности Й, содержащих заданную вершину аЕВ",равно( ); 7) число граней размерности к, содержащих заданную грань раз- /и — 1з мерности 1, равно ( ); 292 Гл. 1Х.
Мцццмиэвцил булев х функццй 11110000001111 00111100111100 3) М = 11000111100110 11111110000000 00000001111111 0110 0011 1001~ 1100 111000 100100 010010 001001 ЦМ= 2)М= 110000 011000 001100 ОООГ10 000011 100001 11100 01110 5) М = 00111 10011 11001 1010010 1001001 0101010 0010110 0100101 4)М= 6)М= 8) пересечение двух граней (если оно не пусто) является гранью; 9) число к-мерных граней, пересекающихся с заданной 1-мерной евы 1ю П гранью куба В"., равно ~~ ( ) 2' 1(, '.). з=о 1.3. 1) Пусть С, Н, .Е грани куба В"'. Показать, что если СйНфЯ, СйЕфИ, НйГфо, то Сй(НйЕ)ф-'ю. 2) Если а, )3 †. вершины из В", то пусть В(а, В) —.
грань куба В" с кодом у, получающимся из набора а расстановкой прочерков в тех ого координатах, которые отличаются от соответствующих координат набора В. Показать, что для трех произвольных вершин а, Д, у из В" множество В)Не, )з) й В(~3, у) й ВЯ, Н) состоит из единственного набора д = (ды ..., б„), где д, = а,Д 'ЦД;у, Ч у,сее 11 = 1,..., и).
3) Пусть Е(А) множество робер куба В", целиком содержащихся в подмножестве А С В". Показать, что для любого целого т такого, что 0 ( т ( 2о з, и любого А С В" такого, что ~А~ = 2" ~ -~- т, выполнено неравенство ~Е(А)~ > тп. 1.4. Пусть пы пз,...,п„ -- целые неотрицательные числа такие, что ~ 2"' = 2". Тогда в В" существуют попарно непересекающиеся грани Сы Сз, ..., С, размерностей, соответственно раве ных пы пз, ..., п„такие, что О Се С Всч ~.—.-1 1.5.
Грани С и Н куба В" называются несравнимь ми, если не выполняется ни одно из включений С С Н, Н С С. 1) Показать, что существует множество граней куба В", состоящее из ~ ) ~ ! попарно несравнимых граней. 2) Показать, что мощность всякого множества попарно несравнимых граней куба В" не превосходит . 2" ~"1з1.
ЯЦ3)/ 1.6. Найти глубину матрицы М: у 1. Сгарукгаура граней и-мерного куба 293 1.7. Найти минимальные мощности градиентных покрытий матриц М из задачи 1.6. 1.8. Найти числа кратчайших покрытий матриц М из задачи 1.6. 1.9. Найти числа тупиковых 1юкрытий матриц М из задачи 1.6. 1.10. Пусть М матрица с п ненулевыми столбцами, а в каждой ее строке не менее й единиц. 1) Показать, что с(М) < п — й+!. 2) Показать, что оценка достижима. 1.11.
Пусть М матрица линейного (и, й)-кода, Показать, что ~(М) < 1з 1.12*. Пусть матрица М размерности т х и имеет не менее з единиц в каждом столбце. Доказать, что: 1) ~(М) < 1+ — [п —; 2) Ьг(М) ( 1+ — [п * е т е т 1.13а. Пусть в матрице М с и, ненулевыми столбцами существует подматрнца М' с т строками такая, что число столбцов подматрицы М', содержащих менее е вдиниц, не превосходит г„. Доказать, что максимальная мощность Ег(М) градиентного покрытия матрицы М удовлетворяет неравенству Ег (М) ~ ~1 + га + е т.
1.14. Пусть матрица т имеет и, ненулевых столбцов, а ее глубина равна р. Дока. зать, что Ег(М) ( 1 + 9+ ([п — ) /[п (1 — — ). 1.15. Пусть двоичная матрица М имеет п = 2(2" — 1) столбцов и д+ 2 строк, причем множество Е, номеров единичных координат ртй строки матрицы М имеет вид Е,=(2' ~,2' "+1,...,2' — 1,п — 2' ~+1,п — 2' ~,...,п — 2'+2) при 1 ( 1 ( У, Еа з —— (1, 2,..., 2" — Ц, Е„ з — †(2а, 2а + 1,...,п).
Найти отношение мощности градиентного покрытия к мощности кратчайшего покрытия. 1.16. Множество Я С В" называется (по к)-протеакаю1аим, если в каждой а-мерной грани куба В" находится хотя бы одна вершина множества Ле. Пусть Е(п, а) = пцп [Х[, гдв минимум берется по всем (по й)-протыкающим множествам. Доказать, что: 1) Ци, 1) = 2а з; 2) Ь(п, и — 1) = 2; 3) 1(п, .2) < [2а,13); 4) т < Ь(п, п — 2) < т, + 2, где т — наименьшее целое, для ко- т торого [ ) ) п; [т,/ 2) [и/ь[ 5)цп,й)< ~ ~( п,); е=о 294 Гл.
1Х. Минимизации булевых функций 6)Ь1п,к)>2" "Цг,к) 1к<г<п); 7) Л(п, й) < 1+ 2" ь 1п ( ) + 2" "'. 1.17*. Пусть 1 < 1 < к ( и и М„ие -- матрица, строки которой соответствуют наборам из В",, а столбцы наборам из В,", и пусть 1 на пересечении строки и столбца, стоит тогда и только тогда, когда набор, соответствующий столбцу, содержит все единицы набора, соответствующего строке.
1) Найти ~(Ми и г ~). 2) Показать, что ЯМи ь ~) > ~ — ~ — 1...~ [... [[[. 3) Показать, что ДМ„„ь е) = 1+ 1 при и. > 11+ 1)й. 4) Показать, что (~) ( ) < ~(М„ь р) < 1+ ( ) (1+ 1и ( )) ( ). 5) Показать, что <1Ми,л г,и е) ~ (г) ) + (1 — 1 ч-г)(2), где г остаток от деления и на 1 — 1, а д = 1п — г)/0 — 1). 1.18. Пусть М вЂ” матрица размерности т х и, уг — положительное число. Показать, что в М можно найти множество строк А мощности, не превышающей и/р, такое, что после вычеркивания всех столбцов, покрываемых строками из А, получается подматрица, в каждой строке которой менее уг единиц. 1.19.
Найти длину минимального теста матриц М из задачи 1.6. 1.20. Найти длины минимальных тестов для матрицы М, если: 1) множество столбцов матрицы М есть В"; 2) множество столбцов матрицы М есть В~",, 3) множество столбцов матрицы М есть О В" 4 о<ь<игг 4) множество столбцов матрицы М есть В„" еэ' В", (й > 0). 1.21. Через М~г~ будем обозначить матрицу, составленную нз сумм по модулю 2 всевозможных неупорядоченных пар столбцов ~по~ Гопы матрицы М. Например, если М = [ОП~, то Моо = '[ПО~. 001 011 Показать, что множество строк матрицы М с номерами гы ..., гь тогда и только тогда является тестом (минимальным., тупиковым тестом), когда множество строк матрицы М~г~ с теми же номерами является ее покрытием (кратчайшим, тупиковым покрытием).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
