XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 44
Текст из файла (страница 44)
Тогда Ь1(а ч х) = [а х]» = [а]» О» [х]» = Ьг(а) 0 Ь1(х), и равенство (4.3) выполняется. В то же время если бы гомоморфиэм Ь1 мы задали как нроектирующиб, т.е. положили бы Ь1 (х) = Ь1(хм ..., х„) = х; 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ (для некоторого фиксированного 1, 1 (1( н), тогда Ь|(аох) = = О'хи а Ьз(а) оЬ|(х) = [а]ь Оь [х;]ь = [а.х;]ь ф а х;.
Таким образом, в этом случае семейство (Ьм Ьз) не будет многосортным гомоморфизмом, при том что каждое отображение семейства будет гомоморфнзмом соответственно группы и кольца. Заметим, что, если группы векторов рассмотренных модулей взять соответственно как аддитивную группу целых чисел и аддитивную группу вычетов по модулю й, многосортный гомоморфизм превращается в обычный канонический гомоморфизм кольца Е. б. Пусть векторами левого модуля М1 являются векторы какого-то конечномерного линейного пространства С над полем действительных чисел [1'1/], а скалярами модуля служат линейные операторы, действующие в этом пространстве.
Пусть размерносщь пространства Ю равна н. В качестве векторов модуля Мз рассмотрим линейное пространство действительных матпрцц-сгаолбцов щцпа н х 1, а скаляров — квадратные матрицы н-го порядка (см. пример 2.12.г). Зафиксировав в пространстве .С базис, зададим отображение Ь1 так, чтобы оно каждому вектору из Б сопоставляло столбец его координат в данном базисе, а отображение Ьз пусть для каждого линейного оператора, действующего в пространстве Ю, дает его матрицу в том же базисе. Основываясь на известных результатах линейной алгебры [1У], можно утверждать, что тем самым определен многосортный изоморфизм модуля М1 на модуль Мз. Замечание 4.6. Как и для обычного „односортного" случая, в теории многосортных алгебр можно доказать теоремы, аналогичные теоремам 4.3 и 4.4 и связывающие понятия многосортного гомоморфизма и мновосортпноб фактор-алзебры.
Не рассматривал этот вопрос подробно, заметим, что переход от многосортной алгебры А = ((А;);ау, й) к ее фактор-алгебре 273 Вопросы и задачи осуществляется на основе многосортпной конгруэнцни— такого семейства отношений эквивалентности (р; С А7);ег, что для любых попарно эквивалентных элементов а;, Ь; Е А;, е Е Х, т.е. таких, что а; р; 6;, имеет место также и эквивалентность (а;„...а;„м) р; (6;,... 6;„ю), какова бы ни была п-арная операция ы Е Й типа (ео,ем...,ев). Тогда любая такая операция может быть распространена на семейство факепор-множестве ((А;/р;)его, Й) согласно равенству [а;, ...а;„ю),в — — [а;,)р, ...[ае„)р,. и. Определенную таким образом многосортную алгебру называют фактор-алгеброй исходной алгебры А = ((А;);ее, Й) относительно многосортнои конгруэнции (р;);еу.
Многосортные алгебры широко используются в современном теоретическом программировании'. Вопросы и задачи 4.1. Показать, что отношение < (см. пример 4.1[б]) на носителе поля г является отношением линейного порядка, т.е. для любых двух элементов а,Ь Е г имеет место а ( (Ь или Ь < а.
4.2. ДОКаэатЬ СЛЕдуЮщИЕ ИЗОМОрфИЗМЫ: Вв "=' ЗЕ, .˄— — 8А, где дм ..., 9в — попаРно Различные пРостые числа, а [А[ = и (см. примеры 3.3.б, 3.9 и 3.11). 4.3. Установить, сохраняет ли отношение, введенное в примере 4.4.а, на множестве Е отношение делимости: га [ и (еп делит и). 4.4. На множестве всех отображений множества М в себя определено отношение т: у т 9, если и только если ль(у) = ль(о). ' Об использовании покатил многосортной алгебры в программировании смл Гоеен Две.А., Мезееер Ж. 274 4.
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Доказать, что в общем случае это отношение, будучи эквивэ. лентностью, не является конгруэнцией относительно компози- ции отношений. Построить пример. 4.5. Имеет ли место изоморфизм Ес~ И Еь,? 4.6. Определить группы движений цилиндра и тора, рассуждая так же, как и при решении задачи 2.20. Доказать, что первая изоморфна группе жз/Е, а вторая — жз/Е~ Ы (В/Е) И Ы Б1 х Б1. 4.7. Доказать, что полукольцо бинарных отношений на и-элементном множестве (ам ...,а ) изоморфно полукольцу квадратных матриц порядка и над полукольцом В (см.
3). 4.8. Найти все разложения булевой алгебры Вз в виде Вз м В х Вз ш Вз х В. 4.9. Доказать, что любой гомоморфный образ решетки, диаграмма Хассе которой изображена на рис. 4.5, изоморфен либо ей самой, либо одноэлементной решетке.
Рис. 4.5 4.10. Найти все гомоморфные образы решетки, диаграмма Хассе которой изображена на рис. 3.5, которые не изоморфны ей самой, а также не изоморфны однозлементной решетке. 5. ТЕОРИЯ ГРАсХ>ОВ Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них. Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кенингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями — пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо — граф. Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинаркыя отношений (см. 1.3).
Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный.
Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать. 276 б. 7ЕОРИЯ ГРАФОВ Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д.
В настоящее время теория графов охватывает большой материал и активно развивается. При ее изложении ограничимся только частью результатов и основной акцент сделаем на описании и обосновании некоторых широко распространенных алгоритмов анализа графов, которые применяются в теории формальных языков. 5.1. Основные определения Неориентироваиные графы Ориентированные графы Неориентированный граФ О задается двумя множествами Ориентированный гра4 С задается двумя множествами С=(У, Е), С=(Ъ; Е), где Ъ' — конечное множество, элементы которого называют вершина.ни или узлами; Е— где Ъ' — конечное множество, элементы которого называют вершинами или узлами; Е— Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами.
Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.
Построение математического определения графа осуществляется путем формализации и „объектов", и „связей" как элементов некоторых (как правило, конечных) множеств. Основные понятия для неориентированных и ориентированных графов удобно вводить „параллельно". Такое изложение позволит наглядно сопоставить соответствующие понятия.
6.1. Осиоввме овределевют 277 множество иеу«орлдочеиных «ар на У, т.е. подмножество множества двухэлементных подмножеств У, элементы которого называют ребрами. Для каждого ребра (и,е)ч Е считаем, что и и е — различные вершины. Если ребро е = (и, е), то говорят, что ребро е соединяет вершины и и е, и обозначают это ит~и; если необходимо, указывают имя графа С: и о е. Вершины и и е, соединеные ребром (ине), называют смежными, а 'также концами ребра (и,е). Если и~-~е, говорят, что вершины и и е связаны от«ношением непоереде«тесиной досглижимост«и.
Ребро е называют инцидент«- ным вершине е, если она является одним из его концов. Ст«е«енью вершины е вазывают число дяе всех инцидентных ей ребер. множество у«орлдочениых «вр на У, т.е. подмножество множе- ства У х У, элементы которого называют дугами. Если дуга е = (и, е), то говорят, что дуга е ведет нз вершины и в вершину е, и обозначают это и т тд если необходимо, указывают имя графа С: и -+с ш Вершины и и е, такие, что из вершины и в вершину е ведет дуга (и ~ с), называют смежными, причем и называют началом, а и — котщом дуги (и, е).
Дугу, начало и конец которой есть одна и та же вершина, называют «ептлей. Если и -+ е, то говорят, что вершины и и е связаны от«ношением непосредст«венной досшижимоет«и. Дугу (и,е) называют эаходли4еб в вершину е и исходящей из вершины и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
