51. Что выделяет функцию из трех известных бинарных отношений

Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {a, b, c, d, e}.

Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX - горизонтальная ось, а OY - вертикальная ось) и на каждой отметим точки, представляющие элементы множества X (рис. 1).

Считая метки a, b, c, d, e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x, y) такими, что (x, y)  . На рисунке 2 изображено множество точек, соответствующее отношению= {(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.

Рис. 2. Бинарное отношение 

Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношения  дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y. Граф бинарного отношения  изображен на рисунке 3.

Рис. 3. Граф бинарного отношения

Для бинарных отношений, определенных на конечных множествах, часто используется матричный способ задания. Пусть на некотором конечном множестве X задано отношение a. Упорядочим каким-либо образом элементы множества X = {x₁, x₂, ..., x_n} и определим матрицу отношения A = [a_ij] следующим образом:

Таким образом, матрица отношения , представленного графом на рисунке 3, имеет вид

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

52. Примеры среды систем как линейных метрических пространств

(только пункт 1)

53. Классификация множеств по мощности

Основная характеристика множества есть его количество его элементов или его мощность..

Количество элементов в некотором множестве называется его численностью. Запись вида n(D)=12 обозначает, что число элементов в этом множестве D равно12.

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

Множество называется счетным, если оно равномощно множеству натуральных чисел. В противном случае множество называется несчетным.

Множество, содержащее конечное число элементов, называется конечным множеством, а множество, содержащее бесконечное число элементов – бесконечным множеством.

Множества называется конечным, если элементы их можно пересчитать.

Множество называется бесконечным, если число их элементов нельзя пересчитать или нельзя, по крайней мере, указать правило, которое позволяет теоретически установить число их элементов.

54. Каковы основные этапы построения полного оптимального потока в ориентированном графе(Форда-Фалкерсона).

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Неформальное описание

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

   1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .

   2. Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему — уменьшаем на .

   3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

4. Возвращаемся на шаг 2.

Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению