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