Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 251
Текст из файла (страница 251)
Инъекции в англоязычной литературе иногда называются функциями однозначного соответствия (опе-1о-опе Йпсйоп). Функция г': А — В называется биекнией (Ьцесйоп), если она является одновременно инъекцией и сюръекцией. Например, функция г'(и) = ( — 1)" )и/21 является биекцией, отображающей множество неотрицательных целых чисел на множество целых чисел: О -+ О 1 — — 1 2 — + 1 3 -+ — 2 4 — + 2 Данная функция является инъекцией, поскольку ни один элемент множества целых чисел не является образом более одного аргумента. Она также является сюръекцией, поскольку каждое целое число является образом некоторого элемента множества неотрицательных целых чисел. Следовательно, рассматриваемая функция является биекцией. Биекции называют также взаимно однозначнымн соответствиями (опено-опе сопезропс)енсе), поскольку они делят все элементы областей определения и значений на пары.
Биекция множества А относительно себя самого иногда называется лврвсюиановкой множества А. Если функция г" является бнекцией, обратная ((пчетзе) к ней функция определяется следующим образом: 1 '(Ь) = а тогда и толью тогда, когда 1(а) = Ь. Например, вот функция, обратная к )' (и) = ( — 1)" )и/21: 2т если т > О, — 2т — 1 если т < О. Упражнения Б.3-1.
Пусть А и  — конечные множества, а г": А -  — неюторая функция. Покажите, что а) если 1 — инъекция, то (А) < (В); б) если г" — сюръекция, то ~А( > ~В). Б.3-2. Пусть имеется функция г'(х) = х+ 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). Если (и, о) — ребро неориентированного графа С = (К Е), то оно соединяет вершины (!псЫеп! оп) и и о и называется инцидентным этим вершинам. Если в графе С имеется ребро (и, о), то говорят, что вершина о смежна (аб!а- сепг) с вершиной и. Для неориентированных графов отношение смежности является симметричным (в случае ориентированных графов это утверждение неверно). Если вершина о смежна с вершиной и, то пишут и -+ ю. На рис. Б.2а и рис. Б.2б вершина 2 является смежной с вершиной 1, поскольку ребро (1, 2) имеется в обоих графах. Вершина ! смежна с вершиной 2 только на рис.
Б.2б. Степенью (беягее) вершины в неориентированном графе называется число ребер, соединяющих ее с другими вершинами. Например, вершина 2 на рис. Б.2б имеет степень 2. Вершина, степень которой равна О (как, например, у вершины 4 на рис. Б.2б), называется изолированной (!зо!агеб). В ориентированном графе различают исходящую степень (ош-оейгее), которая равна количеству выходящих из вершины ребер, и входяьцую степень (!п-бейгее), которая равна количеству входящих в вершину ребер. Степень (бейгее) вершины в ориентированном графе равна сумме ее входящей и исходящей степеней.
Так, на рис. Б.2а вершина 2 имеет входящую степень 2, исходящую — 3, так что степень данной вершины равна 5. Путь (маршрут) длины й от вершины и к вершине и' в графе С = (!г, Е) представляет собой последовательность (оо,щ,оз,...,оь) вершин, такую что и = оо, и' = оь и (ю; 1,о;) Е Е для 1 = 1,2,...,к. Длиной пути называется количество составляющих его ребер. Путь содержит (соп!а!пз) вершины оо, о!, оз,..., оь и ребра (оо, о1), (ом оз),..., (оь ы оь). Всегда имеется путь нулевой длины из вершины в нее саму Если имеется путь р из вершины и в вершину и', то говорят, что вершина и' достижима (геасЬаЫе) из и по пути р, что иногда в ориентированном графе С записывается как и -» и'.
Путь является простым (з!шр!е), если все вершины пути различны. Например, на рис. Б.2а путь (1, 2, 5, 4) является простым путем длины 3; путь (2, 5, 4, 5) простым не является. Подпуть (зпЬра!Ь) пути р = (оо, щ,..., оь) представляет собой непрерывную подпоследовательность его вершин, т.е. для любых О < 1 < у < к последовательность вершин (о;, кч+1,..., о ) является подпутем р.
В ориентированном графе путь (оо, о1,..., ьь) образует цикл (сус!е), если оо = = и, и путь содержит по крайней мере одно ребро. Цикл называется простым, если кроме того все вершины о1,оз,...,оь различны. Петля является циклом с длиной ! . Два пути — (оо, о1,..., оь и по) и (ц~, о1~,..., оь, оо) — образуют один и тот же цикл, если существует такое целое у, что о,' = об+у! ь,ьв ь для 1 = О, 1,..., /с — 1 (один цикл получен из другого сдвигом). На рис. Б.2а путь Приложение Б. Множества и прочие художества 1215 (1,2,4,1) образует тот же цикл, что и пути (2,4,1, 2) и (4,1,2,4). Этот цикл простой, цикл (1, 2, 4, 5, 4, 1) таковым не является. Цикл (2, 2), образованный ребром (2, 2), представляет собой петлю. Ориентированный граф, не содержащий петель, называется простым.
В неориентированном графе путь (оо, сы..., оь) образует (нростой) цикл, если /с > 3, ео = оь и все вершины ос, оз,..., оь различны. Например, на рис. Б.2б путь (1, 2, 5, 1) является циклом. Граф без циклов называется ациклическим (асусйс). Неориентированный граф является связным (соппессед), если любая его вершина достижима из другой по некоторому пути. Для неориентированного графа отношение "быть достижимым из** является отношением эквивалентности на множестве вершин. Классы эквивалентности называются связными квмяонентаии (соппессед сошропепсз) графа. Например, на рис.
Б.2б имеются три связных компонента: (1,2,5), (3, 6) и (4). Каждая вершина в (1, 2, 5) достижима из другой вершины этого множества. Неориентированный граф считается связным тогда и только тогда, когда он состоит из единственного связного компонента. Ориентированный граф называется сильно связным (зсгопя1у соппессед), если любые его две вершины достижимы друг из друга.
Любой ориентированный граф можно разбить на сильно связные каияоненты (зсгопя!у соппессес1 сошропепсз), которые определяются как классы эквивалентности отношения взаимной достижимости. Ориентированный граф считается сильно связным тогда и только тогда, югда он состоит из единственного сильно связного компонента Граф на рис. Б.2а состоит из трех таких компонентов: (1, 2, 4, 5), (3) и (6). Все пары в множестве (1, 2, 4, 5) являются взаимно достижимыми. Вершины (3, 6) не образуют сильно связный юмпонент, поскольку из вершины 3 нельзя достичь вершины 6. Два графа С = ()г, Е) и С' = (У', Е') изоморфны (1зошогрЬ1с), если существует биекция г": У -+ Г, такая что (сс, ц) Е Е тогда и только тосда, югда (Г" (и), С' (ю)) Е Е'.
Другими словами, мы можем перенумеровать вершины С, превратив их в вершины С', сохранив при этом ребра между вершинами в неизменном состоянии. На рис. Б.За показана пара изоморфных графов С и С' с множествами вершин У = (1, 2, 3,4, 5, 6) и Ъ" = (и, е, со, х, у, г) соответственно. Отображение Р на Г выглядит следующим образом: г (1) = и, г" (2) = о, 1 (3) = и, 1' (4) = х, 7" (5) = у, Г" (6) = г. Графы на рис. Б.Зб неизоморфны.
Хотя оба изображенных здесь графа имеют по 5 вершин и 7 ребер, граф в верхней части рисунка имеет вершину степени 4, которой нет у нижнего графа. Мы говорим, что граф С' = (Ъ", Е') является нодграфом (авЬдгарЬ) С = = Я Е), если 1г' С У и Е' С Е. Если в графе С = (1г Е) выбрано подмножество Ъ" С У, то подграфом графа С, порожденным (1попсео) множеством вершин Г, является граф С' = (Ъ", Е'), где Е' = ((и,с) Е Е: и,с Е У) . 1216 Часть Ч!П. Приложения: математические основы Рис. Б.З. Изоморфиые и иеизоморфиые графы Подграф, порожденный множеством вершин (1, 2,3,61 на рис. Б.2а, показан на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
