А.А. Вороненко - Решение избранных задач по курсу дискретной математики, страница 3

Следовательно, множество А содержит ровно о = 2" ' функций. 16 ВБЯТИС Яо ПОЛНОТА В Р, 11.6.1(1). Выяснить, полна ли система функций А = (ху,х Ч у,х В у, ху ~ уз Ч гх). я Составим критериальную таблицу Из таблицы видно, что система А не является полной, так как А С ° ' П.6.2(4). Выяснить, полна ли система функций А = (Х~ = (0101), Х, = (ШО 1000), 1о = (ОПО 1ОО1)1, я Составим критериальную таблицу Из таблицы видно, что система А не является полной, так как А С л.

11.6.3(1). Выяснить, полна ли система А =- фй М) 0 (Х ~ М). м рассмотрим функцию т(х, у, х) = ху Ч уг ~/ хх из множества о'й М, а также функции х у = х 9 у 9 1 и х = х 9 1 нз множества Х ~ М, Составим критериальную таблицу: Ясно, что (А! З ((т(х, у, г),х у, У)! = Рз, так что система А полна в Рз. 11.6.11. Доказать, что если Х монотонна и зависит существенно не менее чем от двух переменных, то система 10, Х) полна в Ро. 17 ° в Функция д ьз О ф Т! 0 о'. Так как функция у монотонна и зависит существенно хотя бы от одной переменной, то у(О..О) = О, так как иначе ~ еа 1 и пе зависит существенно ни от одной переменной.

Таким образом 7(0..0) = 1 и 1" (с Тс. Так как 7(0..0) = 1 и функция существенно зависит от хотя бы одной переменной, то существует набор на котором функция при!!имает 3!гаченис О, но тогда оца не являс'Гся монотонной; таким образом, у ф М. Поскольку множество М П 1, пе содержит функций, существенно зависящих от двух переменных, то у нелинейна, а значит, нелинейна и 7. Таким образом система функций является полной в Рз. в П.6.5(1).

Из полной в Рз системы А = (1,х,ху(т.9у),хну!в хус! уз 9 зх1 выделить всевозможные базисы. ~ Составим критериальпую таблипу г4 войдет в базис в любом случае, а яз оставшихся функций можно выбрать любые две. Искомые базисы 8! = (!!,.!з Я Вз = (Л 1з Я Вз =- (Л.

уз Я. П.6.8(4,6). Выяснить, можно ли расширить до базиса в Рз множество А: 4. А = (х Ч у, ху) б. А = (х 61 у, х . у ) 4. Составим критериальную таблицу Из таблицы видно, что можно дополнить до базиса нелинейной функцией, принадлежащей Тс и Т! (например, конъюнкцией ху). П,6.16. Доказать, что если (' (с То О Т! О о', то Г' — шефферова функция. ° Утверждение следует из того, что М С Тс О Т! и Ь С Тс 0 Т! (.! о'.

П.6.16. Подсчитать число шефферовых функций в Рз(Х"). ° Если у ф Тз О Т! О о. то ( — шефферова функция, а значит, число шефферовых функций в Рз(Х") равно А! = (Тс Г! Т! О о((Ю = (Тс О Т ~(п! ~Т О Т Г! б"~(тЦ 22<-2 !, 22" ' 22"-2 22" ' — ! 2 П.6.10(4). Выяснит!в при каких и > 2 функция у(х') = 19 ,'~ х;х,. !©<!<я является шефферовой. 4 Очевидно, что у ф Тс. Кроме того, у ф Т!, если количество слагаемых х;х,,1 < ! < ! < и, нечетпо. Количество слагаемых (") = (" М печетпо при и = 4й + 2 или п = 4!с + 3. Двойственная функция имеет вид 1* = у 9 (и — 1) 2 х, (й 1 9 ("), поэтому у самодвойственна при и = !ьп 41+ 3. Окончательно имеем, что функция является шефферовой при и = 4)с + 2. Занятие №8 ГРАФЫ: ИЗОМОРФИЗМ, СВЯЗНОСТЬ Множество А дополнить до базиса нельзя, так как функции х У у и ху принадлежат одним и тем же предполным классам.

6. Составим критериальную таблицу 18 'Л.1.34(6.1,6.2,6.3). Среди пар графов, изображенных на рисунках, указать пары изоморфных и пары неизоморфных графов. ° 4 Для любой из пар графов нужно либо построить взаимнсюднозначпое соответствие между вершинами и ребрами, либо указать, почему два данных графа неизоморфны. — Рис. 6.1: Строим взаимноодпозпачное соответствие так, кзк показано на рисунке, Рнс.

1 Рис. 2 б) 1» -- Рис. 6.2: Графы пеизоморфны, так как в графе на рис. 6.2(а) вершины степени 4 смежны с разными вершинами степени 2, а в графе на рис. 6.2(б) — с одной. — Рис. 6.3: Рассмотрим дополнения этих графов (рис. 2). Нетрудно видеть, что дополнения графов изоморфны =~ изоморфны сами графы. Ъ'1.1.13(1). Пусть 5(С) — наименьшая нз степеней графа С, не имеющего петель и кратных ребер и содержащего и вершин (и > 2). Доказать, что если с(С) > (и — 1)/2, то граф связен. ~ Пусть граф С не связен.

Тогда в нем есть два множества вершин. между которыми нет ребер. Выберем по 1 вершине нз каждого множества. По условию, степени этих вершин не меньше, чем —. Следовательно, минимальное число вершин в таком графе равно 2 ( — "' + 1) = и+ 1, что противоречит условию (в графе ровно и вершин) => граф С связный. Ъ'1.1.12. Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины ( > 3 содержит простой цикл. Справедливо ли аналогичное утверждение для маршрутов четной длипыу м В мультиграфе замкнутый маршрут из трех ребер всегда является простым циклом; М.1.2(1).

Обозначим через и;(С) число вершин степени 1 в графе С. Построить все попарно пеизоморфпые графы без петель и кратных ребер, у которых пв(С) = 1, пз(С) = и4(С) = 2 н кч(С) = 0 при ~ ф 2»3,4. м Число вершин графа равно 5. Пусть д — число ребер в графе. »» ~, Ыес и; = 2с ~ о = 8 »=1 В полном графе с и вершинами п(а — 1)~2 ребер, что при и = 5 составляет 10 ребер. Следовательно, исходный граф может быть получен нз полного удалением двух ребер либо при одной вершине, либо при разных. Во втором случае невозможно получить нз вершины степени 4 вершину степени 2. Следовательно, такой граф только один: Предположим, что для других натуральных 1 (1 = 2к + 1,й б И) это не так.

Значит, существует замкнутый маршрут наименьшей длины, не являющийся простым циклом: пв ° ° °; с»з гь» ° ° с»» ° ° °, вс Тогда, если длина маршрута о;,..., с; четная, то исключим из первоначального замкнутый маршрут »»''" »»з иначе удалим маршрут иь,...,вь В результате оставшийся маршрут будет иметь нечетную длину, 21 Если полученный маршрут не содержит простой цикл, то мы пришли к противоречию, поскольку изначально выбирался маршрут наименьшей длины. Если же полученный маршрут содержит простой цикл, то мы также приходим к противоречию, так как, по предположению, исходный маршрут не содержит простого цикла.

Следовательно, в мультиграфе всякий замкнутый маршрут нечетной длины 1 > 3 содержит простой цикл. Для маршрутов четной дллшы утверждение неверно: 3 ЪЧ.1.22. Пусть у графа без петель и кратных ребер п вершин и 6 компонент связности. Доказать, что число ребер в нем не меньше, чем и - 6 р р ~=-'~~.В ° р, .- р .-р графа (п > 2) число ребер больше 1" — ф1 — :-~~~, то он связный. м Число ребер в графе максимально, если каждая из компонент связности — полный граф. Тогда при фиксированных и и з выясним, возможно ли при перенесении вершины из одной компоненты связности в другую каким-то образом увеличить число ребер во всем графе.

Рассмотрим две компоненты связности, в одной из которых 1, а в другой т вершлш. Считая, что первоначально компоненты содержали максимальное число ребер то есть ' ' и ', перенесем из компоненты 111-1) т~т-1) 61 в компоненту з одну вершину н посчитаем, насколько изменилось число ребер в компонентах 61 и 6,„. Число изменится на величину пл — (1 — 1), которая положительна при т >1> 2. При 1 = 1 сократить число вершин в меньшей компоненте невозможно: это приведет к уменьшению числа компонент. Количество ребер в графе максимально тогда и только тогда, когда г — 1 компоненты связности состоят из одной вершины, а оставшаяся— нз остальных вершин. ЪЧ.1.20(1). Граф (без петель и кратных ребер) называется самодополнительньлм, если он изоморфен своему дополнению.

Показать, что 22 если граф салюдо1юлнительный, то число вершин в нем равно либо 41 (1 > ) ), либо 41+ 1 (1 > О), ~ В полном графе с и всршинамн и — "' ребер. Из изоморфностп графа своему дополнению следует совпадение числа их ребер. В сумме количество ребер равно п(п — 1) п(п — 1), 2 2 :2 Э с я=41, 1>1 п=4(+1, л>0 ЪЧ.1,21(1).

Выяснить, сколько существует попарно пеизоморфпых графов без петель и кратных ребер, имеющих 6 вершин н 11 ребер. ° я В полном графе с 6 вершипамн число ребер равно —, = 1о =) в 6616-1) графе С -- дополнении к графу С вЂ” 15 — 11 = 4 ребра . Рассмотрим всс попарно пеизоморфпые графы, дополнительные к графу С, (1) Рассмотрим графы, включающие в себя циклы: (а) цикл нз 4 ребер Ф (Ь) цикл из 3 ребер; тогда 1Ъ' ребро — либо входит в ту же компоненту связности, что и цикл, — либо образует вторую компоненту. (2) Рассмотрим ацнклнческие графы. Не существует связного графа, состоящего из 6 вершин н 4 ребер: в связном графе с 6 вершинами должно быть не меньше 5 ребер, Следовательно, искомые графы будут состоять как минимум нз 2 компонент связности.