Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 57
Текст из файла (страница 57)
п — и) вершин являются изолированными, равно 2 2) Показать, что число графов без изолированных вершин в 'М„, и и — я равно ~1 — 1)ь( ')2~ а=о 3) Показать, что почти все и-графы не имеют изолированных вершин. 6.4. Пусть подмножество '6 с 'б„состоит из Х попарно различных графов.
Показать, что число попарно неизоморфных графов в '6 не меньше Х(п!. 6.5. Пусть ф„, -- число попарно неизоморфных связных графов с т ребрами. Показать, что: 1) 1б1т) < ~~~ ((')); 1 — ( З -~- Л -~- п ы ] < п < пй-1 2 2) У(пе) < (2т)'и при т — ~ оо. 6.6. Показать, что число попарно неизоморфных псевдографов, не имеющих изолированных вершин и обладающих т ребрами, не превосходит (от)п', где с константа, не зависящая от т. 286 Гл. 7Ш. Элементы комбинвторини Плоское ориентированное корневое дерево, в котором дуги ориентированы к корню, называется дихотомическим, если степень полузахода каждой вершины либо равна О 1такие вершины будем называть висячими), либо равна 2 (такие вершины будем называть внутреннимн).
6.15. Ц Доказатгч что каждое дихотомическое дерево с т внутренними вершинами имеет ровно т + 1 висячих вершин. 2) Пусть 1 число попарно различных дихотомических деревьев с т внутренними вершинами. Доказать, что 1в — — 1г — — 1, а при т > 1 = ~1ь1 в=в 3) Доказать,что йы = ~ '). 1 /2тд т+1 гп Плоское ориентированное корневое дерево будем называть почти дихогпомическим, .если все дуги ориентированы к корню, степень полузахода каждой вершины находится в пределах от О до 2, каждая вершина с полустепеныо захода, равной 1, является концом дуги, исходящей из висячей вершины (т.
е. вершины с полустепенью захода, равной О). Вершина почти дихотомического дерева называется внутренней, если степень полузахода отлична от О. Пусть 1 я число попарно различных почти дихотомических деревьев с т внутренними вершинами, Й из которых имеют полустспень захода, равную 1, и пусть 1,„число попарно различных почти дихотомических деревьев с т внутренними вершинами.
6.16. 1) Показа~в, что 1 я =1 ь~ ' ), где 1 вели/т — й -Ь 11 чина, определенная в предыцущей задаче. 2) Доказать,что 1ы < 2""', где 2 < с < 3. Обозначим через Фп множество всех попарно различных формул над множеством связок 11~, йе, †) и множеством переменных Х" = = 1ехм хг, ..., хл). ФоРмУлы считаютсЯ Различными, если они пРедставляют собой различные слова в алфавите 1Ч, й, —, 1,), хы хг,...
..., хп). Пусть Фп лг подмножество тех формул из Фп, которые содержат ровно гп связок и в которых отрицания встречаются только над символами переменных. Пусть Т„п, . множество почти дихотомичсских деревьсв, имеющих т внутренних вершин, и таких, что каждая висячая вершина помечена символом алфавита Хп = 1хы хг, ..., х„), каждая внутренняя вершина, имеющая полустепень захода, равную 1, помечена символом —, а каждая из остальных внутренних вершин — символом из алфавита 1Ч, й ). 6.17. 1) Установить изоморфизм между множествами Ф„,„н Т„ 2) Доказать, что ~Фп,„~ < (сп) ы., где с --. константа, не зависЯщаЯ отп ит. 288 1"ж 'ыП1.
Эеементм комбинаторики 1".) 1".) 1.") ~ Р~1С) = ~ ~ ди(и, и) = ~ д Д,и, и) + 2~ ди1,и, и). с низ ы=з р=г ы=1 ы<р (г)-г Но д„1и, р) = 2'г), если и ~ д. Поэтому Ррып) = — (2) + 4 (2) ((2) 1) (2 (2)) 4 (2) Полагая в 12) д = ЗУпр(п), получаем, что доля тех графов С й 'Ми, 1 для которых р1С) — — ) ) > ~) — — ( ), не превосходит —. Отсюда 1ГпЗ вытекает, что для почти всех графов р1С) = — (2)11+ е„).
где 2 ~,2г' 1пп еи = О. 6.18. Пусть р1С) число пар различных вершин графа С из 'йо, для которых не существует цепи длины меньшей, чем 3, соединяющей /оЗ эти вершины. Пусть р1п) = 2 1гг ~ р1С). ОеМы 1 и. 3 1) Показать, что р1п) = — ( ') ( ) 2) Показать, что у почти всех и-графов отсутствуют вершины, расстояние между которыми больше 2. 3) Используя результаты задачи 6.18, 2), показать, что у почти всех п-графов радиус и диаметр равны 2. 6.19. Показать, что среднее число гамильтоновых циклов в графах С из ейи равно (п — 1)!/2нт". 6.20.
1) Найти среднее число р1п) циклов длины 3 для графов С из 'эи. 2) Найти дисперсию Рр1п) числа циклов длины 3 для графов С из '6„. 3) Показать,. что для почти всех графов С Е 'еа, число р1С) циклов длины 3 удовлетворяет асимптотическому равенству р1С) р1п) при и -з со. 6. 21. 1) Найти среднее число р1п, пе) циклов длины 3 для графов С из и)о 2) Показать, что дисперсия Рр1п, т) числа циклов длины 3 для графов С из 'йи „, удовлетворяет неравенству Р(р)1п, т) < п~1ти/и), где гу = (2).
3) Показать, *его если т = т1п) и 1пп 1т/п) = оо, то для почти всех гРафов С из 'йт число Р1С) циклов длины 3 УдовлетвоРЯет асимптотическому равенству зз р1С) — ( — ) при и — ~ со. 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,..., и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
