Алгоритмы - построение и анализ (1021735), страница 250
Текст из файла (страница 250)
если любая пара элементов А может быть связана отношением В. Например, отношение "<" на множестве натуральных чисел является отношением линейного порядка, в то время как отношение "быть потомком" на множестве людей таковым не является, поскольку могут быть люди, которые не являются потомками друг друга. Упражнения Б.2-1. Докажите, что отношение подмножества "С" на множестве всех подмно- жеств Х является отношением частичного, но не полного порядка. Б.2-2. Покажите, что для любого положительного ть отношение "тождественности по модулю и" является отношением эквивалентности на множестве целых чисел. (Мы говорим, что а ве Ь(шос(ть), если существует такое целое число д, что а — Ь = дп.) На сколько классов эквивалентности разбивает множество целых чисел это отношение? ьДля того чтобы отношение "может поместиться а*' было отношением частичного порядка, надо считать, что ящик может поместиться сам а себя.
Часть Ч11!. Приложения: математические основы 1210 Б.2-3. Приведите пример отношения, которое а) рефлексивно и симметрично,но не транзитивно; б) рефлексивно н транзитивно, но не симметрично; в) симметрично и транзитивно, но не рефлексивно. Б.2-4. Пусть Я вЂ” конечное множество, а  — отношение эквивалентности на Я х Я. Покажите, что если  — антисимметрично, то все классы эквивалентности содержат по одному элементу. Б.2-5. Профессор полагает, что всякое симметричное и транзитивное отношение В должно быль рефлексивным.
Он предлагает следующее доказательство: из а Н 6 в силу симметрии следует 6 В а, а применение транзитивности к этому выводу дает а В а. Прав ли профессор Б.З Функции Для данных двух множеств А и В функция )' представляет собой бинарное отношение на А х В, такое что для каждого а е А существует ровно одно 6 Е В, такое что (а, 6) Е г". Множество А называется областью определения (с1ошша) функции г", а множество  — областью значений (собоша1л).
Иногда для функция используется запись ~: А - В; кроме того, если (а,Ь) е ~, то мы записываем 6 = ( (а), поскольку значение 6 однозначно определяется по значению а. Интуитивно функцию ~ можно рассматривать как операцию, которая ставит в соответствие каждому элементу А элемент В.
Никакому элементу А не может быть поставлено в соответствие два различных элемента В, однако один и тот же элемент В может соответствовать разным элементам А. Например, бинарное отношение ~ = ((а, Ь): а, Ь Е Х и Ь = а шос1 2) является функцией г": Х вЂ” + (О, Ц, поскольку для каждого натурального числа а имеется ровно одно число Ь из (О, 1), такое что Ь = а шос1 2.
Например, 0 = З" (0), 1 = У (1), 0 = У (2) и т.д. Бинарное же отношение д = ((а,,Ь): а, Ь Е Х и а + Ь вЂ” четно) функцией не является, поскольку и (1, 3), и (1, 5) являются элементами д, так что элементу а = 1 соответствуют более одного элемента Ь, такого что (а, Ь) Е д. Если у нас имеется функция Г": А - В, и 6 = 1'(а), то а называется арументом функции ), а Ь вЂ” значением функции ~ от данного аргумента а.
Можно определить функцию, указывая ее значения для каждого элемента из области определения. Например, можно определить Г (и) = 2п для п Е 1Ч, что означает У = ((п,2п): п Е )ч'). Две функции )' и д называются равными, если у них 1211 Приложение Б. Множества и прочие художества одинаковые области определения и значений и если для любого а из области определения / (а) = д (а). Конечная последовательность длины и представляет собой функцию /, область определения которой — множество из и целых чисел (0,1,...,и — Ц.
Зачастую конечная последовательность записывается как список ее значений: (У (О), У (1),..., /(и — 1)). Бесконечной носледовательностью называется функция, область определения которой — целые неотрицательные числа. Например, последовательность чисел Фибоначчи, определенная рекуррентным соотношением (3.21), представляет собой бесконечную последовательность (О, 1, 1,2, 3, 5,8,13,21,...).
Если область определения функции / является декартовым произведением, дополнительные скобки вокруг аргументов в записи обычно опускаются. Например, если у нас есть функция /: Аз х Аз х х А„- В, то мы можем записать Ь = /(аз,аз,..., а„), а не Ь = /((аз, аз,...,а„)). Кроме того, в этом случае аргументом называется каждый элемент а;, хотя технически единым аргументом функции / является кортеж из и элементов (аз, аз,..., а ). Если Ь = / (а) для некоторой функции /: А — В, то иногда говорят, что Ь есть образ (ппайе) а.
Образ подмножества А' С А определяется как / (А') = (Ь б В: Ь = У (а) для некоторого а Е А') . Множество значений (гапйе) функции / представляет собой образ ее области определения, т.е. /(А). Например, множеством значений функции /: Х вЂ” + М, определенной как / (и) = 2п, является У (Х) = (гп: гп = 2п для некоторого и Е М) . Функция называется наложением или сюръекцией (звг1ес11оп), если ее множество значений совпадает с областью значений. Например, функция У (и) = 1п/2) представляет собой наложение множества неотрицательных целых чисел на множество неотрицательных целых чисел, так как каждый элемент этого множества служит значением / для некоторого аргумента.
Функция же / (и) = 2п не является наложением Ь1 на Х, поскольку, например, число 3 не является значением / ни для какого аргумента; однако эта функция является наложением Х на множество четных натуральных чисел. Сюръекцию /: А — В иногда называют отоброэкением А на В. Функция /: А -+ В называется вложением или иньекцией (1п1есиоп), если различным аргументам / соответствуют различные значения, т.е. из а ~ а' вытекает / (а) ф / (а'). Например, функция / (и) = 2п является вложением множества Х в Х, так как каждое четное число Ь является отображением не более одного элемента из области определения, а именно Ь/2.
Функция / (и) = 1п/21' вложением не является, поскольку значение 1, например, получается для двух 1212 Часть ЧШ. Приложения: математические основы аргументов — 2 и 3. Инъекции в англоязычной литературе иногда называются функциями однозначного соответствия (опе-1о-опе Йпсйоп). Функция г': А — В называется биекнией (Ьцесйоп), если она является одновременно инъекцией и сюръекцией.
Например, функция г'(и) = ( — 1)" )и/21 является биекцией, отображающей множество неотрицательных целых чисел на множество целых чисел: О -+ О 1 — — 1 2 — + 1 3 -+ — 2 4 — + 2 Данная функция является инъекцией, поскольку ни один элемент множества целых чисел не является образом более одного аргумента. Она также является сюръекцией, поскольку каждое целое число является образом некоторого элемента множества неотрицательных целых чисел. Следовательно, рассматриваемая функция является биекцией.
Биекции называют также взаимно однозначнымн соответствиями (опено-опе сопезропс)енсе), поскольку они делят все элементы областей определения и значений на пары. Биекция множества А относительно себя самого иногда называется лврвсюиановкой множества А. Если функция г" является бнекцией, обратная ((пчетзе) к ней функция определяется следующим образом: 1 '(Ь) = а тогда и толью тогда, когда 1(а) = Ь. Например, вот функция, обратная к )' (и) = ( — 1)" )и/21: 2т если т > О, — 2т — 1 если т < О. Упражнения Б.3-1.
Пусть А и  — конечные множества, а г": А -  — неюторая функция. Покажите, что а) если 1 — инъекция, то (А) < (В); б) если г" — сюръекция, то ~А( > ~В). Б.3-2. Пусть имеется функция 1 (х) = х+ 1. Будет ли она биекцией, если ее область определения и область значений — натуральные числа? А если ее область определения и область значений — целые числа? Приложение Б. Множества и прочие художества 1213 Б.З-З. Дайте определение обратного к бинарному отношению. (Если отношение является биекцией, то определение должно давать обратную функцию.) *Б.3-4.
Приведите пример биекции 1: Е-+ Е х е. Б.4 Графы В этом разделе будут рассмотрены два типа графов — ориентированные и не- ориентированные. Следует иметь в виду, что терминологию в этой области еще нельзя назвать вполне устоявшейся, так что в литературе можно встретить определения, отличающиеся от приведенных здесь, хотя в основном эти отличия незначительны. Вопрос о представлении графов в памяти компьютера рассматривался в разделе 22.1.
Ориентированный граф (гйгесгед ягарЬ) С опрелеляется как пара (Ъ; Е), гле У вЂ” конечное множество, а Š— бинарное отношение на У. Множество Ъ' называется множеством вершин (чеггех зе1) графа С, а его элементы — вершинами. Множество Е называется множествам ребер графа С, а его элементы— ребрами. На рис. Б.2а изображен ориентированный граф с множеством вершин (1, 2, 3, 4, 5, 6).
Вершины на рисунке показаны кружками, а ребра — стрелками. Обратите внимание на возможность существования ребер-циклов, или нетель (зе1Б1оорз), т.е. ребер, соединяющих вершину с самой собой. В неориентированном графе (ппгйгес1еб ятарй) С = (У, Е) множество ребер Е состоит из неупорядоченных пар вершин, т.е.
ребро является множеством (и, о), где и,о е У и и ф о. По соглашению для ребер используется запись (и,о), причем и (и, о), и (о, и) обозначают одно и то же ребро неориентированного графа. В неориентированном графе петли запрещены, так что каждое ребро содержит две разные вершины. На рис. Б.2б показан неориентированный граф с множеством вершин (1,2,3,4,5,6). Многие определения выглядят одинаково и для ориентированных, и для не- ориентированных графов, хотя некоторые отличия, естественно, имеются. Если (и, с) — ребро направленного графа С = (К Е), то ребро выходит из (1псЫепг Рнс. Б.2.
Ориентированные и неориевтированяые графы 1214 Часть У!(!. Приложения: математические основы йош, 1еаче) вершины и и входит в (!псЫеп! го, еп!ег) вершину о. Например, на рис. Б.2а из вершины 2 выходят ребра (2, 2), (2, 4) и (2, 5), а входят в вершину 2 ребра (1,2) и (2,2). Если (и, о) — ребро неориентированного графа С = (К Е), то оно соединяет вершины (!псЫеп! оп) и и о и называется инцидентным этим вершинам. Если в графе С имеется ребро (и, о), то говорят, что вершина о смежна (аб!а- сепг) с вершиной и. Для неориентированных графов отношение смежности является симметричным (в случае ориентированных графов это утверждение неверно). Если вершина о смежна с вершиной и, то пишут и -+ ю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
