4) Основные виды отношений

1. Отношения эквивалентности - отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Любое отношение эквивалентности, заданное на множестве, разбивает это множество на непересекающиеся подмножества.

2. Отношением квазипорядка на множестве X называется отношение R ⊂ X × X, обладающее свойствами рефлексивности и транзитивности.

3. Отношения порядка:

Нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным.

Строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным.

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

4. Отношением полного порядка называется отношение порядка, обладающее дополнительно еще и свойством полноты. Оно удовлетворяет аксиомам: x ≥ x; x1 ≥ x2 и x2 ≥ x3 ⇒ x1 ≥ x3; x1 ≥ x2 и x2 ≥ x1⇒ x1 = x2; ∀x1, x2 ∈ Х ⇒ x1 ≥ x2 или x2 ≥ x1.

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

5.1) Экстремальные элементы множеств

В соответствии с отношением порядка говорят, что при x₁ ≤ x₂ элемент x₁ предшествует элементу x₂ или x₂ следует за x₁.

Пусть имеется подмножество X′ ⊂ X, где X упорядоченное множество, т.е. множество, для элементов которого определено отношение порядка. Тогда мажорантой множества X′ называется элемент x_max ∈ X, следующий за всеми элементами множества X′, x_max ≥x (x_max ∈ X). При этом мажоранта может и не принадлежать множеству X′. Если же x_max∈ X′, то x_max называется наибольшим элементом, или максимумом множества X′.

Минорантой множества X′ называется элемент x_min ∈ X, предшествующий всем элементам множества X′. Если элемент x_min ∈ X′, то он называется наименьшим элементом, или минимумом множества X′.

5.2)Отображение множеств

Пусть X и Y - два непустых множества. Закон G, согласно которому любому элементу x ∈ X ставится в соответствие элемент y ∈ Y, называется однозначным отображением X в Y, или функцией, определенной на X и принимающей значения на Y.

Используются следующие формы записи: G: X → Y или y = G(x), x ∈ X, y ∈ Y.

В случае однозначного отображения элемент y = G(x) называется образом элемента x.

Возможна ситуация, когда каждому x ∈ X отображение G ставит в соответствие некоторое подмножество G(x) ⊂ Y. Тогда образом элемента x будет подмножество G(x), а отображение G, будет называться многозначным отображением.

Отображение является, таким образом, всюду определенным соответствием, т.е. частным случаем соответствия и определяется тройкой множеств (X, Y, G).

6) Общие понятия теории графов. Ориент. И неориент графы.

Множество точек (вершин, узлов) и множество линий (ребер, дуг), которые соединяют эти точки, называются графом.

Графом называется упорядоченная пара множества X (мн-во вершин) и мн-во его двухэлементных подмножеств.

Граф G задается множеством точек (вершин) X={x₁,..x_n} и множеством линий (ребер) A={a₁,..,a _m}, соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).

Ребра графа – линии, соединяющие вершины, указывают на соответствие между вершинами в графе. Запись g(x_i, x_j) говорит, что ребро g инцидентно вершинам x_i, x_j и вершины x_i, x_j инцидентны ребру g. Две вершины x_i, x_j называются смежными, если они определяют ребро графа. Два ребра графа называются смежными, если их концы имеют общую вершину.

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

Неориентированное ребро, если порядок расположения его концов (направление

стрелок) в графе не принимается во внимание. Ориентированное, если этот поря-

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

Для каждого графа G(Х) существует обратный граф.G-1(Х), полученный

изменением ориентации каждого из ребер графа G(Х) на противоположную.

Полным неориентированным графом называется граф U(Х), ребрами

которого являются всевозможные пары g(x_i, x_j,) для двух возможных x_i, x_j ∈X,

i≠j

Полным ориентированным графом U₀(Х) - граф, у которого любые две вершины соединены хотя бы в одном направлении.

Петля - начальная и конечная вершины совпадают. Петля обычно считается неориентированной.

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

Дополнением графа G(Х) является такой граф Gk(Х), ребра которого совместно с графом G(Х) образуют полный U(Х) граф.