Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
x к так называемому представлению со смешанными основаниями. При этом преобразовании вы- полняем только операции многомодульной арифметики. Все выполняемые действия по вычислению знака основаны на представлении числа x по ки- тайскому алгоритму в виде x = q 1 + q 2 · m 1 + q 3 · m 1 · m 2 + . . . + q n · m 1 · m 2 · . . . · m n−1 , (3.5) где 0 6 q i < |m i |, q 1 — остаток от деления x на m 1 . Коэффициент q n на- зывается старшим членом числа x. В этой форме знак числа x совпадает со знаком его старшего члена. Отметим, что в форме со смешанными основаниями мы имеем x = n P i=1 q i · M i , где M i = m 1 m 2 . . . m i−1 и M 1 = 1; частные M i /M i−1 различны для различных позиций i. Если m 1 = m 2 = . . . = m n = P , то получим представление с фиксированным основанием P — представление в P -ичной системе счисления. При определении знака удобно, чтобы последний модуль m n в векторе оснований был равен 2, поскольку нужно знать, в какой половине множества возможных чисел лежит результат (если q n = 0, то x > 0; если q n = 1, то x < 0). Например, на рис. 3.3 числа 0, 1, 2, 3, 4, 5 образуют нижнюю половину множества возможных чисел, соответствующую значению q n = 0, а числа 6, 7, 8, 9, 10 — верхнюю половину, соответствующую значению q n = 1. Предположим теперь, что нам дано представление x = [a 1 , a 2 , . . . , a n ] от- носительно вектора оснований β = [m 1 , m 2 , . . . , m n ] и требуется определить знак числа x в симметричной системе. Нам нужно преобразовать число x к форме (3.5) и определить знак старшего члена. Для этого необходимо най- ти цифры q 1 , q 2 , . . . , q n , содержащиеся в (3.5). Очевидно, что из (3.5) вытекает x ≡ q 1 (mod m 1 ), следовательно, q 1 = a 1 Мы получили первую цифру. Далее возьмем разность x − q 1 (вычитая q 1 из каждого остатка, представляющего x). Имеем x − q 1 = q 2 · m 1 + q 3 · m 1 · m 2 + . . . + q n · m 1 · m 2 · . . . · m n−1 . Первая цифра (в смешанном представлении) числа x−q 1 равна нулю, следо- вательно, первые цифры всех последующих чисел можно не рассматривать. Будем считать, таким образом, что длина вектора x − q 1 равна n − 1. Затем ЗАДАЧИ И УПРАЖНЕНИЯ 113 найдем (m 1 ) −1 (mod β r ), где β r = [m 2 , . . . , 2], и вычислим (многомодульное) произведение (x − q 1 )(m 1 ) −1 , для того чтобы получить вторую цифру q 2 Будем продолжать этот процесс до тех пор, пока не вычислим значение q n ∈ {0, 1}, которое является индикатором знака числа x. Пример 3.9.7. Определим знак числа x = [4, 2, 0, 1] с вектором основа- ний β = [7, 5, 3, 2] в симметричной системе относительно β. Очевидно, что q 1 = 4, и x 0 = x − 4 = [0, 3, 2, 1] или, как было объяснено выше, x 0 = [3, 2, 1], поскольку вектор оснований можно сократить до вектора β 0 = [5, 3, 2]. Для того чтобы получить вторую цифру q 2 , вычислим (m 1 ) −1 (mod β 0 ) = 7 −1 (mod β 0 ) = [3, 1, 1]. Умножив x 0 на этот элемент, получим x 0 · (m 1 ) −1 = [4, 2, 1]. Следовательно, q 2 = 4, тогда, вычитая q 2 из последнего модулярного выражения, получим x 00 = [0, 1, 1] или x 00 = [1, 1] для β 00 = [3, 2]. Далее вычисляем (m 2 ) −1 (mod β 00 ) = 5 −1 (mod β 00 ) = [2, 1] и, умножая x 00 на этот элемент, получаем [2, 1]; поэтому q 3 = 2. Вычитая q 3 из последнего модулярного выражения, получаем x 000 = [0, 1], или x 000 = 1 для β 000 = [2]. В заключение вычисляем (m 3 ) −1 (mod β 000 ) = 3 −1 (mod β 000 ) = [1] и, умножая x 000 на этот элемент, получаем [1], откуда следует, что q 4 = 1. Поэтому x является отрицательным числом. Действительно, x = 4 + 4 · 7+ +2 · 7 · 5 + 1 · 7 · 5 · 3 = 207 (mod 7 · 5 · 3 · 2) = 207 (mod 210) = −3. ¤ Задачи и упражнения 1. Найти остаток от деления числа 45 44 + 43 2 + 2 42 на 7. 2. Доказать, что 6 делит n(n + 1)(n + 2) для любого натурального числа n. 3. Доказать, что 5 n+2 + 6 2n+1 делится на 31 при любом натуральном n. 4. На какую цифру оканчивается число 3( 3 3 )? 5. Найдите две последние цифры у числа 7 N , где N — год Вашего рождения. 114 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 6. Определить, на сколько нулей оканчивается число 100!. 7. Найти все целые решения уравнения: а) 5x + 3y = 1; б) 47x − 111y = 89. 8. С помощью алгоритма Евклида найти наибольший общий делитель чисел: а) 6188 и 4709; б) 81719, 52003, 33649 и 30107. 9. Найти неприводимое разложение числа 82798848. 10. Составить таблицу простых чисел, меньших 130. 11. Решить сравнение: а) 256x ≡ 179 (mod 337); б) 111x ≡ 75 (mod 321). 12. Составить таблицы Кэли для операций сложения и умножения в кольце Z 2 × Z 3 13. Решить систему сравнений: а) x ≡ 4 (mod 5), x ≡ 6 (mod 7), x ≡ 9 (mod 11); б) x ≡ 2 (mod 3), x ≡ 4 (mod 5), x ≡ 7 (mod 11), x ≡ 3 (mod 13), x ≡ 6 (mod 17). 14. Используя многомодульную арифметику с вектором оснований β = [3, 5, 7], вычислить a + b, a − b, a · b и b −1 (mod β), где a = 9, b = 23. 15. Относительно вектора оснований β = [3, 5, 7] найти многомодульные пред- ставления чисел 127, −127, 537 и −537 в виде симметричной системы остат- ков и системы наименьших неотрицательных остатков. 16. Найти знак числа x = [6, 3, 1, 1] с вектором оснований β = [7, 5, 3, 2] в сим- метричной системе относительно β. 17. Используя многомодульную арифметику с вектором оснований β = [3, 5, 7], вычислить 2 11 − 7 13 Глава 4 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 4.1. Виды и способы задания графов Во многих прикладных задачах изучаются системы связей между раз- личными объектами. Объекты называются вершинами и отмечаются точка- ми, а связи между вершинами называются дугами и отмечаются стрелками между соответствующими точками (рис. 4.1). Такие системы и образуют графы. Граф может изоб- • • • • ¡ ¡ ¡ ¡ ¡ µ H H H H H Y @ @ @ R m µ ª ¸ 1 2 4 3 Рис. 4.1 ражать сеть улиц в городе: вершины графа — пере- крестки, а дуги — улицы с разрешенным направлением движения (улицы могут быть с односторонним и дву- сторонним движением). В виде графов можно предста- вить блок-схемы программ (вершины — блоки, а ду- ги — разрешенные переходы от одного блока к друго- му), электрические цепи, географические карты и мо- лекулы химических соединений, связи между людьми и группами людей. Перейдем к точным определениям. Графом называется алгебраическая система G = hM; Ri, где R — двух- местный предикатный символ. Элементы носителя M называются вершина- ми графа G, а элементы бинарного отношения R ⊆ M 2 — дугами. Таким образом, дугами являются пары вершин (a, b) ∈ R. При этом дуга (a, b) на- зывается исходящей из вершины a и заходящей в вершину b. Изображение графа G = hM; Ri получается путем расположения различ- ных точек на плоскости для каждой вершины a ∈ M, причем если (a, b) ∈ R, то проводится стрелка (дуга) из вершины a к вершине b. 116 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пример 4.1.1. Изображение графа G с множеством вершин M = {1, 2, 3, 4} и множеством дуг R = {(1, 1), (1, 2), (2, 3), (3, 4), (4, 3), (4, 1)} представлено на рис. 4.1. ¤ При задании графа для нас не имеет значения природа a b • • ¡ ¡ ¡ ¡ ¡ µº : Рис. 4.2 связи между вершинами a и b, важно только то, что связь существует и информация о связях содержится во множестве дуг R. Однако часто возникают ситуации, при которых та- кой информации оказывается недостаточно, например, в слу- чаях, когда имеется несколько дуг, исходящих из вершины a и заходящих в вершину b. Такие дуги называются кратными (рис. 4.2). Тогда используется понятие мультиграфа. Мультиграфом G называется тройка hM, U, P i, в которой M — множе- ство вершин, U — множество дуг, а P ⊆ M × U × M — трехместный пре- дикат, называемый инцидентором и представляемый следующим образом: (a, u, b) ∈ P тогда и только тогда, когда дуга u исходит из вершины a и за- ходит в вершину b. Отметим, что любой граф можно представить в виде мультиграфа. Граф G = hM; Ri называется ориентированным (орграфом), если най- дется дуга (a, b) ∈ R такая, что (b, a) / ∈ R. Если же отношение R симметрич- но, т. е. из (a, b) ∈ R следует (b, a) ∈ R, то граф G называется неориентиро- ванным (неорграфом). Если одновременно пары (a, b) и (b, a) принадлежат R (рис. 4.3а), то информацию об этих дугах можно представить множеством [a, b] {(a, b), (b, a)}, называемым ребром, которое соединяет вершины a и b. При этом вершины a и b называются концами ребра [a, b]. Ребра изобража- ются линиями (без стрелок), соединяющими вершины (рис. 4.3б ). • • ¼ * a b • • ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ a b а б Рис. 4.3 4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ 117 Если в мультиграфе вместо дуг рассматриваются ребра, то мультиграф также называется неориентированным. Отметим, что если в орграфе G = hM; Ri к каждой дуге (a, b) ∈ R добавить пару (b, a), то в результате образуется неорграф , который будем называть соответствующим данному орграфу G и обозначать через F (G). Пример 4.1.2. Орграфу G, изображенному на рис. 4.1, соответствует неорграф F (G), изображенный на рис. 4.4. ¤ Введенные в § 2.2 понятия морфизмов алгебраиче- • • • • ¡ ¡ ¡ ¡ ¡ H H H H H @ @ @ m ¢ ¢ ¢ ¢ ¢ 1 2 4 3 Рис. 4.4 ских систем для графов представляются следующим об- разом. Пусть G = hM; Ri, G 0 = hM 0 ; R 0 i — графы. Тогда отображение ϕ: M → M 0 является гомоморфизмом, ес- ли для любых вершин a, b ∈ M из (a, b) ∈ R следует (ϕ(a), ϕ(b)) ∈ R 0 . Биекция ϕ: M ↔ M 0 является изо- морфизмом графов, если (a, b) ∈ R ⇔ (ϕ(a), ϕ(b)) ∈ R 0 . Пример 4.1.3. Рассмотрим граф G, состоящий из множества вершин {1, 2, 3, 4} и множества дуг [1, 2] ∪ [3, 4] ∪ {(1, 3), (2, 4), (3, 2), (4, 1)} (рис. 4.5а). Граф G 0 = h{a, b, c}; [a, b] ∪ [b, c] ∪ {(a, c), (b, b)}i является гомоморфным образом графа G при гомоморфизме ϕ, в кото- ром ϕ(1) = a, ϕ(2) = b, ϕ(3) = c, ϕ(4) = b (рис. 4.5б ). Граф G 00 , по- казанный на рис. 4.5в, изоморфен графу G посредством изоморфизма ψ, при котором ψ(1) = a, ψ(2) = b, ψ(3) = c, ψ(4) = d. Отображение χ: {1, 2, 3, 4} ↔ {1, 2, 3, 4}, при котором χ(1) = 2, χ(2) = 1, χ(3) = 4, χ(4) = 3, является автоморфизмом графа G. ¤ • • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ µ ¾ ¾ @ @ @ @ @ @ @ @ @ R 1 2 4 3 • • • - ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ A A A A A A A A A ±° ²¯ a c b • • • • - @ @ @ @ @ @ @ @ @ I ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ª - b a d c а б в Рис. 4.5 118 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G = hM; Ri — граф, в котором множество вершин имеет n элементов: M = {a 1 , a 2 , . . . , a n }. Матрицей смежности A G = (A ij ) графа G называется матрица порядка n, определенная следующим образом: A ij ( 1, если (a i , a j ) ∈ R, 0, если (a i , a j ) / ∈ R. Если A ij = 1, то вершина a j называется последователем вершины a i , а a i — предшественником a j . Вершины a i и a j называются смежными, если A ij = 1 или A ji = 1. Если G — мультиграф, то в матрице смежности A G элемент A ij по опреде- лению равен числу дуг, исходящих из вершины a i и заходящих в вершину a j (i, j ∈ {1, . . . , n}). Пример 4.1.4. Граф G, изображенный на рис. 4.6, имеет матрицу смежности • • • • • a 5 a 1 a 2 a 3 a 4 - ¡ ¡ ¡ ª m m Рис. 4.6 A G = 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 . ¤ Отметим, что если G — неорграф, то матрица смежности A G симметрична, т. е. не меняется при транспонировании: A T G = A G Петлей в графе G называется дуга, соединяющая вершину саму с собой. Если G — граф без петель, то в матрице смежности A G по главной диагонали стоят нулевые элементы: A G = 0 0 ∗ ∗ 0 . |