В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 33
Текст из файла (страница 33)
рашены одинаково. Например, раскрашивания /ь /з. показан. ные на рнс. З.б,а, б, эквивалентны, так как при совмещении фц гуры Ф с раскрашиванием /г с фигурой, получаемой иэ фигуре, Ф с раскрашивапнем /, врагцением на угол н/2 (против часов~3 стрелки), совьгещаемые элементы раскрашены одинаково (сц на рнс. 3.8,е результат вращении фигуры Ф с раскрлшиваниец /з на угол и/2; сравните с рис. З.й,а). Пры этом У(ьдХ /, (1) ч» =/з((п/2) 8), .3.2.8. Производящая функции запаса классов эквивалентности Прехвалоын, что сохраняются усвоена, аписа»с~не в рсхд. Здб н йду, Пус за ас м мжество ыюв эквннслснтностн Рюяф . Вовпвкзег вопрос: к ко в врамзводяюлн функцвя запас ~ы(Р)У Зная орсювсдмпую функцвю запаса, монна рсывть некоторые дасгзточно сломвые «омбннвторпые задачи.
Дейст ктелыю, пусть, нвпрнюп Д= (гв гм, ы( ) а, (гз) Ь н известна крюышдюгюя функпня ввпюл, предо нелсон*я виде ~ Н (Р) - У с„. -Ь » (т. е. приведенная к ы!ду многсчленв, где суммнровввне в вмрвмеюн со)»вез в)ювх плотен ос ясен целым всат)геке е замы \, й, 1 довленюрюс Юнм равшспу в»+с=в). Н тогда нзвсспнг н есе числа с . вырюкавнпне полз ст а к»ассов вквн в евыюстн ыс* "Ь». втн числа дают ответы нз многие прюывдные комыюаторвме звдвчн, чвстнастн, если гь — ценз, позволяют апр дечнть ым о рвзлнюмк (попарно неювнввлевтных) рвснмюнввннй прв заданной «омбнввцнн нв то .
Твк, в условиях прнмера Ззу число с,л «рвывет мглнчеюсз различных рвскр в~кап»1пй фнсуры Ф генка что 3 зле евт* окрсюены в красный цвет, в Š— в голубой; се +с», +сь»+ +с з — коакчсство различных рвскрвюнввнкй фигуры Ф танах, что, оо «рвй. кей ыере, 2 элемента опряыенм пыубой пест. Для практического построения производящей функции запаса классов эквмналентности воспользуемся следующей теоремой. теорема 3.! (сослепа лоос). пронмюдяюая фр«хакк заносе хюсмм .зкззе еюхсюн рдозлегзорют равенству Яю(Р) Р(П, Х, ~ ыз( ), ~ (г (г)Р ° ° ~) (м (гД") (3.32) Р гюд гюд гюд ГДЕ Р(П, Х, Гь Гв, Г ) — анзпаеай ННДЫЮ ГРУ Пм О.
ЛЕИСЮУЮШсй Ве Х Следствие. Если веса юд(г), гш/(, выбраны равными ). та. число классов эквввалентности равно Р(П, Х, ))((, ..., ))Т(). (333) пример 323, используя примеры 3.23 в азу, опредыыч пронзволявим 4. умквню запаса классах зквнввлы»тнсстл. В сиду теоремы Пойв. прн ыгн" Рмулу [3.31), внеем 133 1 ХЮ(Р) Р(б,«,н+Ь,Е*+ЬХ И+Ь.н'+Ьб +ЬП вЂ” ((н+Ь)'4- с 4 4. 2(е Ь- Ь) (а'+ Ь') + ( + Ь) (Н'+ Ы)*). (Ззч) Воспользовавшись равенством (3.34), определим, сколькими ропарно неэквнвалентиыми способами ложна раскрасить фигуру Ф так, чтобы три ее элемеита были окрашены в красный цвет, з два — в голубой.
Для этого найдем коэффициент с прн члене Сб'ьт В ПРОИЗВОДЯЩЕЙ фУНКЦИН ЗанЗСа КЛаССОВ ЭяеииааскгясетИ, 1 приведенной к виду многочлена. Очевидно, что с= (!из+2) = ь — (19+2) =3, т. е. существуют трн попарно неэквнвалентныс 1 способа раскрашивания с заданной комбинацией цветов. Используя теперь следствие из теоремы Пойа, получаем, что общее число попарно неэквивалентных способов раснрашивзниз, выражаемое формулой (3.33), равно (2т+2 2т+2т) !2 4 3.2.9.
Обоснование теоремы Пойа Для доказатслэегва теоремы Пайа потребуются векоторыс вспоиогатсльные утверждения. Для любого натурального числа ! обозначим й (1 2.. /). утвермзенне 3.1З. Пусте д" — «е шуташенсе аюм!е! ам ю Х. с 1, „ Е / 1...„ю, Гетра й Хн = ~) Пн ! с с (3 зь! Ше ! " — мнакестш всех отобрт сенна Ш ! ! . Ь Лымзател сгзс нрееедем мзлгнм еб на Ь Омннюю, что зрн Ь 1 рамнютс (з.зв) вююлняетсн. пгсж ыю сзрззедсн о н нрн з — 1 (где з>з). Пснежем еп\ зинслненте нрн З: П дни=(П Хай( Х а!) (~ П с! ())(Х с!) с ° !с с с- 1- еш! с Х а!Па ) Х,' Йл! Ут ержденне З.гз.
Пусте Х,..., Х, — нелишне юдмниюстш .ннсюес! Ш Х. сбрзэуюмне разбитым лнюшсгш Х. т. е. й«с «. Х,й«! бт нр с П д (м~(г)1"', г-' гый (зле) рече!аврам «аа«фывыа йу, гае х - (х,,..., х,). ом леан теса ы(11 функций чвп ва формуле а я н(у! 11 Ряайбл!)Б ' ° ! Очевидно, что между функциями из рассматриваемого запа. са н функциями из НТ можно установить взаимна однозначное соответствие.
Для зтво каждой функпин )! Х Н рассматриваемого запаса поставим в соответствие функцию фущй" такую, чта Угщ(1, ..., й) рг(Х!) =Цх,), где х,!ыХ!. При таком соответствии. очевмдно, в(!р!)=в()), а следовательно, производящая функция рассматриваемого запаса совпадает с производящей функцией запаса Лх. Но тогда для доказательства утверждения 3.1б осталось заметить, ыо в силу утверждения 3.13 производящая функцня запаса й" выражается формулой (3.3б) (здесь ан=(вя(г!))ац где Н=(г!, ..., г )). Теперь докажем теорему Пайа. Пусть б — множество значений весов элементов )щбх и Н(И) =()!ы)(х(в(() =И), где Ищб. Пусть группа б действуег на НЯ и прн этом у)щН(И] й) определяется по правилу (й)) (х) =)(й-гх), хияХ. Заметим, что У(свН(И), Уйепб й) (, а счедовательяо, т)еаН(И), Убепб б)щН(И).
Покажем, что введенное отображение (й, ()-ьй) прямого произведения б)(НЯ в НЯ действительно удовлетворяет условиям (3.19), (3.21). Условие (3.19) очевидным образом выполняется. Покажем справедливость (3.20). Действительно, Уй. дскб, обозначив )=Д(, имеем ((бй)() Я =(Най)-гх) =((й-! (й-!х) ) =) (й-!х) = = (й() (х) = (б (Щ) (х), хщХ. Используя лемму Берисайда, получаем ткып (нрйг 1 д )бымрй(х( Б1, ! (3.37) (о( Заметим, что УРщбх/ РгвН(И), где И=в(Р), откуда (З.йй) УРщНх! РщН (в (Р) ) ) 1зз багга дама щ (Х,(, ! 1,..., а.
ус!де яаемаыхыыаа фуыыма в~в фуыына «а йх, арннвмамынх настоянные значения на «агапам мз Хь равна Пусть бш/). В силу (3.33) имеем (Рсш/(л/ (ю(Р)=б)ы ыН(б)/ . Покажем также противоположное включение Пусть РгевН(б)/ . РассматРнм пРоизвольнУю фУнкцню /сюрг, а также класс зквивалентиости Реи)(к/ — такой, что /шР. Тогда ю !Р) = =ю(/)=б, а следоватеаьно, в силу (333) РспН(б)/ .
Такию образом, Р, РггшН(б)/, Г/)Р~~Б, откуда в силу утверждения б.б Р Рь т. е, Ргш(ршйк/ )ю(Р)=б). Итак, мм доказали„ что Убеа/) (Райк/- (ю (Р) =б) =Н (б)/ (3.39) Используя теперь тот факт, что Н(б,)ПН(бт)=)И при бтчьбт, в силу (3.39) получаем, что (Н(б)/ )бш/)) — разбиение множества /тл/, откуда, воспользовавшись (3.37), в также тем, что УршН(б)/ ю(Р)=б, имеем м!Р) ~', Х м!Р) Х, Л)Н!и)/ Гюл"/ Лют) Г НИН- Люб 1 лл — ~ а ! б ю !1!а) (к/ = В !- Люб )О!К б 1 мб)- люб !и! -о /юбмн(а))к/-/) 1 3 мб) (6(Ф л о !об и!л))к/ -В !3 <3ДО) !б!Хюб / б е-!л/-П Звмсжм даве, чю Ькюп подсюлолке т„рлвапвлст мвомсство Х лс тссвбпм хм„.,„хсммст, где а!к) — чпсло армм.
Ооазеечнм ю!к)=. 1Хгг)г), где г 1, ..., Д(к). Нетрудна мщсп. мо К/ /лот!ю (1,..., д!КВ Ис ми: тлюХю /!л) с, Ио то да, лспольлус утвсрмдслпс 3 16, в сп у !3 40) получаем ~ -а-+Х м!ВГюл'/ !о)к о /ю!/юл"!к/ б о Ик) г )О)люп 1-1 гюд ! П (~ ! л!г)!')/г!К) )и! б 1=! л — „Р(б/Д ~ мс(), 3 !м,(г)У,.... Ю ( .!г)! ). гг я гюй Задачи н упражиеннв 1. На квадратных листах бумаги пишут пятизначные числа от 0 до 99999. Есин в некотором числе менее пяти значапшх цифр, то его дополняют слева нулями (например, пишут 00536 вместо 336). Считается, что после вращения листа на угол ц цифры О, 1, 3 не менянмся. а цифры 6. 9 переходят друг в дру. га.
Сколько нужно иметь листов бумаги длн записи всех чисеа с учетои возможности вращения пистону 2. Составляются ожерелья из плоских бусин трех цветов, ок. рашенных одинаново с обеих сторон. Каждое ожерелье состоит из шести бусин. Определить число различных ожерелий. 3. Определить, сиолькимн сшкобамн можно раскрасить тре. мя цветами пронуэгерованные элементы фигуры Ф. Два способа раскрашивания считаются одинаковыми, если один получается из другого вращением фигуры на плоскости (вокруг центра Ф) Варианты фигуры Ф доиазапы на рис.
3.9, а. б. 4. Определить, сколькими способами эюжно раскрасить тре. мя цветамн (ирасиым, голубым, зеленым) пронумерованные элеыенты фвгуры Ф, предполагая, что л, элементов должны быть окрашены в ирасный цвет. в,— в голубой, нз — в зеленый. Два способа раскрашивания считаются олпнаковыми, если один по. лучается из другого вращением фигуры на плоскости (вокруг центра Ф). Варианты фигуры Ф показаны иа рис. 3.9,п.
б. Со. ответствующие им наборы значений пь пг, нз равны ш=3, лз= =4, па=2 или л,=1, не=4, па=4. а) ф рэс. З.з б. Решить задачи 3 и 4 в предположении, что два способа расирашивзння счнтакпся олинаиовымн, если один получается из другого вращенаеы фигуры Ф на плоскости [вокруг центра Ф) нли в результате осевого преобразованяя симметрии. КОНЕЧНЫЕ ГРАФЪ| И СЕТИ ГЛАВА 4 4.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ Прежде чем определить понятие конечного графа в наиболее общей форме, представим себе на плоскости (или в вещественном аффнпном пространстве произвольной размерности й) некоторое конечное множество У точек и конечный набор Х линий, соединяющих некоторые пары точек нз У.
Указанной геометрической конфигуралией описывается, например, схема автомобильных порог, связывающих города некоторой области (рнс. 4.!). Для многих задач оказывается несущественным, соединены ли точки конфигурапни отрезками прямых илн криволинейными дугамн (напрамер, при решении задачи о нахождении маршрута движения по дорогам. связывающего два заданных городе и прокодящего через минимальное число дорог).
Важно лишь то, что каждая линия соединяет какие-либо две из заданного набора точек. Прн рассмотрении подобных задач достаточно ограничиться псследовашгем совокупности двух коночных множеств У, Х, где У в нелустое множество, Х вЂ некотор набор паэ элементов иа У вида (а, ю). Введенная пара множеств (У, Х) допускает также многочисленные другие ннтерпреталии я является предметом детального изучения в математике. Зле. менты миокшства У будем ° взывать нержинами, а злементы набора Х вЂ” ребрамп В общем случае в наборе Х могут встречаться лары с олинаковыми элементами аида (а, а), а также одинаковые пары.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
