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

(а) В од)1ой компоненте связности 5 вершины, в другой — 1; таких графов несколько: — степень вершин не превосходит 2; т3; — степень вершин не превосходд т 4. -- степень вершин не превосходд ор Рис.З оз Рис,4 о, Рис.2 Риси ~Ь) В одной компоненте связности 4 вершины, в другой — 2 Возможны 2 варианта: — степени вершин не превосходят 2, — степени вершин не превосходят 3. ~с) в каждой из компонент связности по 3 вершины.

Занятие № 9 ГРАФЫ: ДЕРЕВЬЯ, ИЗОМОРФИЗМ 'И.1,26. Доказать, что во всяком дереве с и > 2 вершинами содержится не менее двух висячих вершин. м Пусть у дерева р вершин, д ребер н рс висячих вершин. ~', сейл; = 29 для любого графа. Кроме того, лля любого дерева выполнено равенство р 4- 1. т и обрюоь, 24 = ~ бей1а =рс+ ~) йейо„>рс+2(р-рс) =ьрс ~ ~2(р-й) =2 1=1 деви>1 Ъ'1.1.29(2). Изобразить все попарно неизоморфные деревья с 6 ребрами и 4 висячими вершинами. ° й Каждая вершина степени и ) 2 добавляет и — 2 висячих.

Следовательно, в дереве есть либо одна верпппьз степени 4, либо две вершины степени 3, 'Л.3.1(в). Построить код плоского корневого дерева, изображенного па Рис. 1, ~ 1-й способ. По определению код искомого дерева Р равен Оа11, где о1 — код его поддерева ь ь Код З1 по определению равен азаз, где о в и аз — коды его левого и правого поддеревьев. Аналогично получим аз = Оаз1. Код аз из определения вычисляется без труда: оз = 0010П, Позтому код дерева Ю равен а = Оа11 = Оазаз1 = ООаз1аз1 = 0000101110010111.

Рис.2 Риси 2 Рис.б Рис,б Рис.4 Риси Рис.2 Рис.з и Да, существуют (см. рис. б, 6, 7). Рис.б Рис.б 2-й способ. Т. к. код дерева можно получить с помощью обхода ~учитывая, что ребра укладки дерева, инцидентнью корню, пронумерованы по чнсовой стрелке), то сразу получаем искомый код: а = 0000101110010111. У1,3.212). Построить плоское корневое дерево по его коду: а = 00110101000111.

4 Представляем искомый код в виде а = а~аоана4, где а1 = 0011, се1 = аз = 01, ао = 000111 — коды поддеревьев дерева с кодом а. Учитьвая, что а1 —— Оа~1, а4 — — 0511, строим данное дерево. У1,1.36. Выяснить, существуют ли в графах, изображенных на рисунке, подграфы, гомеоморфные К4 1Рис. 4).

ЗВД4ЯТ)4Е Яо 10 ГРАФЫ: ПЛАИАРНОСТЬ, РАСКРАСКИ, ОРГРАФЫ ЪЧ.2.Ц2). Применяя критерий Понтршъшн Куратовского, выяснить, планерны ли изображенные па рисунке графы. !(,. ° й Применим критерий Повтрягина-Куратовского к данным графам: в каждом из них существует подграф, гомеоморфный Код ~см. Рис. 4, 5, 6). У1.2.13. Плоский связный граф бл висячих вершин, каждая грань которого, включая и внешнюю, ограьшчепа циклом длины 3, называется ьчриангрллциеб.

Покнзать, что триангуляция с и > 3 вершипамн имеет Зп — 6 ребер и 2п — 4 граней. м Пусть триангуляция с и вершиннмн имеет т ребер и г граней, тогда., поскольку каждой грани трангуляции по условию принадлежит ровно 3 ребра, а каждое ребро принадлежит ровно 2 разлпчным граням, то имеем гп = 31/2. Далее, по формуле Эйлера и — ш + ~ = 2 =: и — 3~/2 + )' = 2 =ь ~ = 2п — 4, т = Зп — 6. Рис.з Рис.2 Риси Рис.4 Рис.б Рис.

Б 'ЪЧ.2.17(1). Показать, что плоский кубический граф, граница каждой грани кото1юго имеет не менее 5 вершин, содержит по крайней мере 20 вершин, Првести пример такого графа. ~ Так как граф кубический, то степень каждой вершины равна 3 =~ колпчество ребер в графе гп = Зп/2 (т. к, каждому ребру принадлежат ровно 2 вершины). Поскольку по условию каждой грани принадлежит не менее 5 вершин, количество граней в графе у < 2т/5 = Зп/5. Из формулы Эйлера и — т + г" = 2 получаем 2 < и — Зп/2+ За/5, откуда и, > 20. Отметпм, что примером удовлетворяющего условию графа может служить центральная проекция на плоскость правильного двенадцатигренника (додеказдра).

ЪЧ.2,18. Найти хроматические числа и хроматические индексы графов, изображенных на рисунке. Ф Заметим, что граф, изображенный на Рис. 1 изоморфен графу, изображенному на Рис. 2, а граф изображенный на Рис. 3 изоморфен графу, изображенному на Рис. 4, поэтому их хроматические индексы и хроматические числа совпадают. Для хроматических индексов верны неравенства: тахс1еяе <;г'(С) 4 шахг(еби+ 1. ело иеп Найдем ЯС) и т'(С) для графов на Рис. 1, 3, 5, 6. 28 Для графа на Рис. 1 ~(С) > 3, ~'(С) > 3. Для графа на Рис. 3 Я(С) > 3, 1с~(С) > 4. Для графа на Рис.

5 ~г(С) > 3, ~'(С) > 3. Для графа на Рис. 6 ~(С) > 3, ~(С) > 3, 'Л,1.54. Бескоишдрнмм ориентированным мультиграфом называется мультиграф, не содержащий контуров. Доказать, что в бесконтурном р(1) = я(1) »~ 6(1 — Ц д(Г) =я(1) йд(~-1) (.) ЗВ,НЯТИЕ № П АВТОМАТЫ д(1) = я(Г) Чд(1-1) Х: ИГ) = Ф) 1сй»-1) д(0) = 1 31 ориептироваппом мультиграфе существует вершина с нулевой полусте- пенью исхода. ° я Начнем движение с л»обой вершипы н па очередном шагу в качестве следующей будем выбирать любую вери»»»»»у, в которую есгь ребро из текущей. 'Т.к. граф бесконтурный, то на каждом шагу мы будем попадать в пепосещенную ранее вершину. С другой стороны, множество вершин графа конечно, поэтому рано или поздно мы придем в вершину, полустепень исхода которой равна О.

'Л.1.60. Показать, что в любом турнире существусг гампльтовова цепь. я Докажем утверждение методом математической индукции. Для туряира с и = 1 вершиной утверждение верно. Далее, пусть оно верно для пекоторого турш»ра с и вершипамя, Добавим к нему еще одпу вершипу »»„+». Пусть с» - »»2 — ... — с„— гамильтонов путь в старом графе. Если есть дуга с„+» — ~ иь то есть путь и„,„» - с» - ... -+ с„, Если епгь дУга с» — с„э» и с„+» -~ сьь», то есть пУть ьй -~ ...

— и; -+ о„,.„» — » п,+» -~... — с„. И»»аче есть путь п»-+ па — ... — ~с„— ~ и„,». В каждом из трех случаев в новом графе есть гамильтонов путь. ТЪ'.2.13(1). Для функции у из Р~~~ построить схему над множеством, состоящим из элемента едипичпой задержки и фупкций, порожденных дизъюнкцней, конъюнкцией и отрицанием: я Сначала построим схему из функциональных элементов пад множе- ством, состоящим из дизъюякции, копъюша»ии я отрицания для следу- ющей совокупности булевых функций: Получеппая схема из функциональпых элемептов, реализующая фупкции (*), будет состоять из двух входных каналов (по переменным я, й) и двух выходных (по переменным й, д): Теперь замкнем выходной капал по переменной д на входной канал д. Так как»1(0) = 1, то после элемента единичной задержки мы поставим элемент, реализуюпп»й отрицание - .

А для того, чтобы при прохождепии элемента едяпичиой задержки мы пе теряли зиа"»ение»1, то перед элементом единичной задержки также поставим элемент, реализующий отрицание - . »л 1Ъ'.2.14(З). По схеме реализующей функцию у из Р, од, построить канонические уравнения, каноническую таблицу и диа»раь»му Мура: Заметим, что в ней состояния 0 и 1 эквивалентны =ь ях можно объеди- нить: и Пусть вериьий элемент задержки соответствует состоянию йм а нижний ' д2.

Канонические уравнения данной функции имеют вид: 1У.2.13(9). Для функции у из Р~цо~д, построить схему над множеством, состоящим из элемента единичной задержки и функций, порожденных дизыонкцией, коныонкцией и отрицанием. у задается диаграммой Мура: Восстанавливаем каноническую таблицу: ~ По заданной диаграмме Мура восстановим каноническую таблицу: По канонической таблице восстанавливаем диаграмму Мура.

Занятие № 12 Автомлты Строим схему: По канонической таблице мы можем восстановить канонические урав- нения. Для этого мы будем строить ДНФ для каждой из функций я® рй), Ч1(г), Ч»(Г) (для сокращения записи вместо я(г), Ч1(г — 1), Ч»(1 — 1) бУдсм писать т, Чм Ч»).

р(5) = Т й Ч, й Ч» ~ и $ Ч, = х '~ В й Ч» Ч й Ч1 Ч1 И) =- Ъ й Ч1 й Ч» М х й Чг й Ч» Ч»(г) = УйЧ~ йЧ» ЧтйЧ1 Ч тйЧ1 й Ч» ч,(о) = ч,(о) = о Для упрощения восприятия схемы мы используем функции, порожденные не только днзъюякцией, конъюнкцией н отрицанием, по и сложсюь ем по пюб 2. Заметим, что Ч»(5) = тйЧ1 йЧ»~яйЧ1 чтйЧ, йЧ»= = Ч1й(МЕЧ»)~лйЧ1 Ж.2.1(24). Построить диаграмму Мура, каноническую таблицу и канонические уравнения для функции /(У") = р(1)у(2)... р(Ф)... из Р» од, где р(1) есть $-я цифра после запятой в двоичном разложении числа ~5.

и Для решения задачи необходимо, прежде всего, найти двоичное разложение числа 5/7 — 1/2 = 3/14 > О =ь 3/14 — 1/4 < О =ь 3/14 — 1/8 = 5/56 => 5/55 - 1/15 = 1/3(5/7 - 1/2) = (5/7) = (О,(1О1))». По Этому разложению Восстанавливаем ннформациО1п|ое дерево, Понятно, что в диаграмме будет 3 состояния, и входные данные будут фиктивными (несугцественными). о * о(1), 1(1) По диаграмме Мура мы восстанавливаем каноническую таблицу (доопределенные ячейки выделены щусиеом): Состояния Таким образом, замечаем, что в диаграмме Мура у нас будет три состояния.

Используя уравнение и информационное дерево, восстановим ее, По диаграмме Мура мы восстанавливаем каноническую таблицу: 37 Затем по канонической таблице восстанавливаем канонические уравне- ния. д(8) = оз(8 — 1) 04(8) =Ы-1) а(8) =Ч (8)-а(8-1) Ч1(0) = Чз(0) = О. В Ж.2.1(16). Построить диаграмму Мура, каноническую таблипу и канонические уравнения для функции Д(Р) = р(1)р(2)... р(8)... из Р2,од~ где т (8) „ если 8-нечетное Ы8) = х(8) Ю р(8 — 1), если 8-четное, ~ Используя описанную в условии формулу, восстановим информациошюе дерево.