Классификация соответствий.

1. Функциональное соответствие (функция). Это соответствие, в котором любому элементу области отправления соответствует не более одного элемента области прибытия. Функциональное соответствие называется взаимнооднозначным, если обратное ему соответствие также является функциональным.

2. Отображение. Отображением называется соответствие, область определения которого совпадает с областью отправления, т.е. это соответствие определено для всех элементов области отправления.

3. Отношение. Отношением называется соответствие область отправления, которого совпадает с областью прибытия, т.е. оно определено на одном множестве, и показывает связи элементов одного множества.

Отношения могут разделяться по количеству связываемых ими элементов.

1. - унарные отношения, могут рассматриваться как характеристика самого элемента, параметра или признака.

2. - бинарные отношения показывают связь двух элементов.

3. - …отношения более высоких порядков.

Рис 3.3. Виды отношений по количеству связей.

Отношения, как и соответствия можно классифицировать по типу свойств, между которыми устанавливается связь элементов. Например, отношение соседства, отношения следования и т.д.

В зависимости от направленности отношения можно разделить на отношения ориентированные и отношения неориентированные.

Отношения ориентированные отображают связь между элементами только в одном направлении (следование).

Неориентированные отношения показывают связь в обоих направлениях (соседство). Их можно рассматривать как два противоположно направленных ориентированных отношения.

Классификация отношений по виду связываемых ими характеристик.

1. Отношение упорядоченности. Показывает на порядок связываемых ими объектов. Отношение упорядоченности могут возникать между объектами для которых имеет смысл порядок, то есть можно сказать, что какой-либо объект находится впереди или после другого.

2. Отношение иерархичности. Показывает подчиненность одних объектов к другим.

3. Отношение соседства. Показывает связь соединения объектов между собой . Данное отношение не направлено в отличии от предыдущих.

4. Отношение следования. Рассматривается как частный случай отношения упорядоченности.

2. Графы. Теория графов. Основные определения.

Граф – это множество элементов V с заданным на них множеством бинарных отношений U.

* U – это множество отношений, поэтому одинаковых отношений (то есть нескольких отношений между теми же элементами, в том же направлении) в нем быть не может.

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

М

Вершины

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

Множество бинарных отношений между вершинами называется множеством дуг или множеством ребер.

В зависимости от ориентированности отношений графы делятся на ориентированные и неориентированные.

Ребро называется инцендентным вершине и вершина называется инцендентной ребру, если ребро заканчивается на этой вершине.

Вершины называются смежными, если они связаны одним ребром. Ребра называются смежными, если они инцендентны одной вершине.

Степенью вершины называется количество ребер инцендентных с ней.

Для ориентированных графов для вершин существуют понятия «полустепень захода» и «полустепень исхода».

Полустепень захода – количество дуг входящих в вершину.

Полустепень исхода – количество дуг исходящих из вершины.

Вершиной стоком в ориентированном графе называется вершина, у которой полустепень исхода равна нулю, а полустепень захода не равна нулю.

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