Дискретная математика (стр. 3 )

Соответствие называется сюръективным, если ОЗ = B.

Образом элемента а в множество B при соответствии G называется множество всех b Î B, соответствующих элементу a Î A. Прообразом элемента b в множество А при соответствии G называется множество всех a Î A, которым соответствует b Î B.

Инъективное соответствие – соответствие, в котором прообразом любого элемента b из области значений ОЗ является единственный элемент a из области определения ОО.

Функциональное (однозначное) соответствие – соответствие, в котором образом любого элемента а из области определения ОО является единственный элемент b из области значений ОЗ.

Соответствие называется биективным (взаимно однозначным), если оно:

а) всюду определено;

б) сюръективно;

в) функционально;

г) инъективно.

Соответствие

не полностью определенное,

сюръективное (ОЗ = В),

не функциональное,

инъективное

Не полностью определенное,

инъекция,

не сюръекция,

функция

Всюду определенное,

сюръекция,

не инъекция,

функция

Всюду определенное,

сюръективное,

инъективное,

функциональное,

биективное

Пример. А = {Иванов, Петров, Сидоров};

В = {2, 3, 4, 5};

R Í A ´ B = {(Иванов, 4), (Петров, 4), (Сидоров, 2)}.

Найти область определения и область значений соответствия R, образ элемента «Иванов», прообраз элемента 2, определить свойства соответствия R (сюръективность, функциональность, инъективность, биективность, является ли R всюду определенным).

ООR = {Иванов, Петров, Сидоров}. Так как область определения соответствия совпадает со множеством А, то соответствие является всюду определенным.

ОЗR = {4, 2}. Область значения соответствия не совпадает со множеством В, поэтому соответствие не является сюръективным.

Образ элемента «Иванов» = {4}, прообраз элемента 2 = {Сидоров}.

Соответствие R является функциональным, потому что у каждого элемента из области определения не более одного образа из области значений. Соответствие не является инъективным, так как элемент 4 имеет более одного прообраза (Иванов и Петров). В силу вышесказанного соответствие R не является биекцией.

Контрольные вопросы

1. Пусть x ΠX, y ΠY и R – отношение между элементами множества, выражаемое соотношением xRy. Укажите, в каких случаях R можно рассматривать как функцию?

а) X – множество студентов, Y – множество учебных дисциплин, xRy означает «x изучает y».

б) X – множество спортсменов, Y – рост в единицах длины, xRy означает «x имеет рост y».

2. Пусть А = {-2, -1, 0, 1, 2}, а В = {0, 1, 2, 3, 4, 5}. Определим соответствие
¦ Í А ´ В как ¦ =  {(-2, 5), (-1, 2), (0, 1), (2, 5)}. Каковы свойства соответствия f ?

3. Пусть ¦ Í R ´ R, где R – множество действительных чисел. Найдите область значений и область определения следующих функций:

а) ¦(х) = х 2 + 4; б) ¦ (х) = ;

4. Соответствие G определено графически. Найти образы и прообразы:
чисел 1, 2, 4; отрезков [1, 2], [2, 4].

 

4. Виды графов

4.1. Понятие графа

Графом G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е – множество ребер).

Число вершин графа (порядок графа) G обозначим p, а число
ребер – q.

Пусть v1, v2 – вершины, е = (v1, v2) – соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность – отношение между разнородными элементами.

Пример.

Данная диаграмма изображает граф, имеющий четыре вершины и пять ребер. В этом графе вершины v1 и v2 смежны, а вершины v1 и v3 не смежны. Смежные ребра: e1 и e5. Несмежные ребра: e1 и e3. Ребро е1 инцидентно вершинам v1 и v2, вершина v1 инцидентна ребрам е1 и е4.

Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е – дугами.

Граф называют неориентированным, если он не имеет ориентированных ребер. Для краткости неориентированный граф называют также неографом. Иногда каждое ребро такого графа представляют как две дуги, направленные в противоположные стороны. Неориентированные графы можно считать частными случаями ориентированных графов, соответствующих симметричным бинарным отношениям, т. е. таким ориентированным графам, которые наряду с каждой дугой (u, v) содержат и дугу (v, u).

Граф, полученный после замены всех дуг в ориентированном графе на ребра, называется основанием.

Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными (параллельными) ребрами, а граф называется мультиграфом или квазиграфом.

Максимальное число ребер, соединяющих две вершины графа, называется мультичислом графа.

Граф называется простым, если каждую пару вершин соединяет не более чем одно ребро и в графе отсутствуют петли.

Если вершины и/или ребра графа помечены (обозначены), то граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с p вершинами обозначается Kp.

Граф G’(V’, E’) называется подграфом графа G(V, E) (обозначается G’ Ì G), если V’ Ì V, а E’ – множество всех ребер G, оба конца которых принадлежат V’.

Двудольный граф (или биграф, или четный граф) – это граф G(V, E), такой что множество V разбито на два непересекающихся множества V1 и V2, причем всякое ребро из Е соединяет вершину из V1 с вершиной из V2. Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если ½V1½ = m и ½V2½ = n, то полный двудольный граф обозначается Km,n.

Пример. Диаграмма графа K3,3.

Граф, состоящий из простого цикла с k вершинами, обозначается Ck.

Пример. С3 – треугольник.

Количество ребер, инцидентных вершине v, называется (локальной) степенью (или валентностью) вершины v и обозначается d(v):

0 £ d(v) £ p – 1

Если степени всех вершин равны k, то граф называется регулярным (однородным) степени k.

Пример. Диаграмма регулярного графа степени 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d–(v) и d+(v).