N в Z, является биекцией:

0 0 1--1 2 1 3-2 4 2

Инъективность означает, что никакой элемент множества Z не является образом двух разных элементов множества N. Сюръек-тивность означает, что всякий элемент множества Z является образом хотя бы одного элемента множества N. Биекции называют также взаимно однозначными соответствиями (one-to-one correspondence), поскольку они устанавливают соответствия между элементами множеств А и В. Биективная функция, отображающая множество А в себя, называется перестановкой (permutation) множества А.

Если функция / биективна, можно определить обратную (inverse) функцию f~l соотношением

f~l(b) = а тогда и только тогда, когда f(a) = Ь.

Например, для рассмотренной выше функции f(n) = ( - 1)п[~га/2] обратная функция вычисляется по формуле

если т 0, 1, если т < 0.

Упражнения

5.3-1 Пусть А и В - конечные множества, и /: А -> В - некоторая функция. Покажите, что

а.если / - инъекция, то А \В\;

б.если / - сюръекция, то А \В\.

5.3-2 Будет ли биекцией функция /: N -> N, заданная формулой /(ж) = ж + 1? Тот же вопрос для функции Z -> Z, заданной той же формулой.

5.3-3 Дайте определение обратного к бинарному отношению. (Если отношение является биекцией, то определение должно давать обратную биекцию в описанном выше смысле.)

5.3-4* Постройте биекцию /: Z -> Z x Z.

Рис. 5.2 Ориентированные и неориентированные графы. (а) Ориентированный граф (V,E), где V = {1,2,3,4,5,6} и Е = {(1, 2), (2, 2), (2, 4), (2, 5), (4,1), (4, 5), (5, 4), (6, 3)}. Ребро (2, 2) является ребром-циклом, (б) Неориентированный граф G = (V, Е), где V = {1,2,3,4,5,6} и Е = {(1, 2), (1, 5), (2, 5), (3, 6)}. Вершина 4 является изолированной (не имеет смежных вершин), (в) Подграф графа (а), получающийся его ограничением на множество вершин {1, 2, 3, 6}.

5.4. Графы

В этом разделе мы рассмотрим основные понятия, связанные с ориентированными и неориентированными графами. Следует иметь в виду, что терминология здесь не вполне устоялась и в разных книгах можно встретить разные определения, но по большей части различия невелики. Мы вернёмся к графам в главе 23, где рассматриваются различные алгоритмы на графах.

Ориентированный граф (directed graph) определяется как пара (V,E), где V - конечное множество, а Е - бинарное отношение на V, т.е. подмножество множества V x V. Ориентированный граф иногда для краткости называют орграфом (digraph). Множество V называют множеством вершин графа (vertex set); его элемент называют вершиной графа (vertex; множественное число vertices). Множество Е называют множеством рёбер (edge set) графа; его элементы называют рёбрами (edges). На рисунке 5.2 (а) показан ориентированный граф с множеством вершин {1, 2, 3, 4, 5, 6}. Вершины изображены кружками, а рёбра - стрелками. Заметим, что граф может содержать рёбра-циклы (self-loops), соединяющие вершину с собой.

В неориентированном (undirected) графе G = (V, Е) множество рёбер (V) состоит из неупорядоченных (unordered) пар вершин: парами являются множества {и, v}, где и, v £ V и и ф v. Мы будем обозначать неориентированное ребро как (и, v) вместо {и, v}; при этом для неориентированного графа (и, v) и (v, и) обозначают одно и то же ребро. Неориентированный граф не может содержать рёбер-циклов, и каждое ребро состоит из двух различных вершин («соединяя» их). На рис. 5.2 (б) изображён неориентированный граф с множеством вершин {1,2,3,4,5,6}.

Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (и,v) ориентированного графа говорят, что оно выходит из (incident from, leaves) вершины и и входит (incident to, enters) в вершину v. Например, на рис. 5.2 (а) имеется три ребра, выходящих из вершины 2 ((2, 2), (2, 4), (2, 5)) и два ребра, в неё входящих ((1,2), (2,2)). Про ребро (и, v) неориентированного графа говорят, что оно инцидентно вершинам (incident on vertices) и и v. Например, на рис. 2.5 (б) есть два ребра, инцидентные вершине 2 (рёбра (1,2) и (2,5)).

Если в графе G имеется ребро (и, v), говорят, что вершина v смежна с вершиной и (is adjacent to и). Для неориентированных графов отношение смежности является симметричным, но для ориентированных графов это не обязательно. Если вершина v смежна с вершиной и в ориентированном графе, пишут и -> v. Для обоих рисунков 5.2 (а) и 5.2 (б) вершина 2 является смежной с вершиной 1, но лишь во втором из них вершина 1 смежна с вершиной 2 (в первом случае ребро (2,1) отсутствует в графе).

Степенью (degree) вершины в неориентированном графе называется число инцидентных ей рёбер. Например, для графа рис. 5.2 (б) степень вершины 2 равна 2. Для ориентированного графа различают исходящую степень (out-degree), определяемую как число выходящих из неё рёбер, и входящую степень (in-degree), определяемую как число входящих в неё рёбер. Сумма исходящей и входящей степеней называется степенью (degree) вершины. Например, вершина 2 в графе рис. 5.2 (а) имеет входящую степень 2, исходящую степень 3 и степень 5.

Путь длины к (path of length к) из вершины и в вершину v определяется как последовательность вершин (г>о, v\,v2,..., vk), в которой v0 = и, vk = v и (f8-i, vi) & Е для всех г = 1, 2,..., к. Таким образом, путь длины к состоит из к рёбер. Этот путь содержит (contains) вершины v0, vt,..., vk и рёбра (v0, vt), (иь v2),..., (vk-i, vk). Вершину vq называют началом пути, вершину vk - его концом; говорят, что путь ведёт из vq в vk. Если для данных вершин и ж и существует путь р из и в и, то говорят, что вершина и достижима из и по пути р (и is reachable from и via р). В этом случае мы пишем (для ориентированных графов) и и.

Путь называется простым (simple), если все вершины в нём различны. Например, на рис. 5.2 (а) есть простой путь (1,2,5,4) длины 3, а также путь (2,5,4,5) той же длины, не являющийся простым.

Подпуть (subpath) пути р = (г>о, v±,..., vk) получится, если мы возьмём некоторое число идущих подряд вершин этого пути, т.е. последовательность (иг-, • • •, vj) ПРИ некоторых i,j, для которых 0 г j к.