множества

отношения

функции

графы

 

МНОЖЕСТВА

Высказывательная функция (предикант) - функция, задающая множество, например: X: P(x)

Собственное подмножество - АÍB, A¹B => A - с.п. В

Универсум - множество, содержащее все рассматриваемые в данной задаче множества

Мощность (размер) - число элементов множества

Синглятон - одноэлементное множество

Множество-степень 2^S - семейство множеств, содержащее исходное множество S, все его подмножества и пустое множество.

Разбиение множества S - семейство, являющееся подмножеством степени S, причём пустое множество не содержится в этом семействе, сумма семейств есть S, и любые два множества этого семейства не пересекаются.

Декартово произведение двух множеств А и В - множество упорядоченных пар <a, b> таких, что aÎA и bÎB. Мощность декартова произведения равна произведению мощностей исходных множеств.

Декартова степень - декартово произведение нескольких множеств.

 

ОТНОШЕНИЯ

Бинарное отношение (двуместное отношение) множеств А и В - подмножество декартового произведения А на В.

Бинарное отношение на множестве - любое свойство, которым обладают любые два упорядоченных элемента этого множества.

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

Область значений отношения (правая область отношения) - множество всех вторых элементов пар отношения.

Поле отношения - сумма левой и правой областей отношения.

Рефлексивное отношение на множестве А - отношение, которое справедливо для каждого элемента множества А как отношение этого элемента к самому себе. Например =, ³ - рефлексивные, ¹, > - нерефлексивные.

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

Транзитивное отношение на множестве А - такое отношение, из справедливости которого для  первого и второго операнда и справедливости для второго и третьего операнда следует справедливость этого отношения для первого и третьего операндов, при условии, что все операнды являются любыми элементами множества А.

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

Класс эквивалентности R - набор элементов множества, для которых эквивалентное отношение R будет давать одинаковый результат.

Отношение равенства двух операндов по модулю m - указывает, что разность операндов делится на m. Является эквивалентным. Число классов эквивалентности равно m.

Антисимметричное отношение - бинарное отношение, из справедливости которого для двух операндов независимо от порядка их следования, следует равенство этих операндов. Например: ³

Рефлексивное отношение частичного порядка - отношение, являющееся одновременно рефлексивным, антисимметричным и транзитивным.

Частично упорядоченное множество - множество вместе с рефлексивным отношением частичного порядка на нём. Например, отношение "делится на" на множестве натуральных чисел.

Соседние двоичные наборы (пары) - двоичные наборы, отличающиеся значением только одного элемента (либо левого, либо правого).

 

ФУНКЦИИ

Сюръекция (наложение) - функция, область определения которой совпадает с множеством допустимых значений. Например, для натуральных чисел y=(x div 2) - сюръекция, y=2*x - не сюръекция.

Инъекция (вложение, "один в один" функция) - функция, для которой различным значениям аргумента всегда соответствуют различные значения функции.

Биекция - функция, являющаяся одновременно инъекцией и сюръекцией.

Инъективность отображения A->B - отношение, показывающее, что любой элемент множества В является образом не более чем одного элемента множества А.

Сюръективность отображения A->B - отношение, показывающее, что любой элемент множества В является образом хотя бы одного элемента множества А.

Биективность отображения A->B - соответствие каждого элемента А каждому элементу В (взаимооднозначное соответствие).

Композиция функций f:A->B и g: B->C - функция, отображающая A в С. Композиция двух биекций есть биекция.

Равномощные множества - множества, между которыми существуют однозначные соответствия. Равномощность транзитивна.

Счётное множество - множество, равномощное множеству натуральных чисел.

Конечное множество - множество, равномощное множеству {1, 2, …, n} или являющееся пустым.

 

ГРАФЫ

Граф - конечное множество вершин и соединяющих некоторые вершины ребёр.

Петля - вершина, соединяющая некоторую вершину саму с собой.

Кратные рёбра - несколько рёбер, соединяющих одни и те же две вершины.

Псевдограф - граф, содержащий петли и кратные рёбра.

Мультиграф - граф, в котором нет петель, но есть кратные рёбра.

Ориентированное ребро (дуга) - ребро, в котором существенен порядок расположения концов.

Ориентированный граф (орграф) - граф, в котором все ребра ориентированны.

Изображение графа - геометрическая конфигурация, в которой вершины графа изображаются кружками, а рёбра - линиями.

Инцидентность - наличие соединения между вершиной и ребром (дугой).

Смежные рёбра (дуги) - имеющие общую вершину.

Смежные вершины - вершины, соединённые ребром (дугой).

Степень вершины - количество ребёр, инцидентных данной вершине.

Изолированная вершины - вершина, не инцидентная ни одному ребру графа (степень равна 0).

Концевая (висячая) вершина - вершина, степень которой равна 1.

Полустепень захода/исхода вершины - количество рёбер, инцидентных по входу/по выходу.

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

Дополнение графа G - граф, в котором две вершины смежны тогда и только тогда, когда они смежны в графе G. Если два графа изоморфны, то их дополнения тоже изоморфны.

Операция подразбиения ребра - удаление ребра, добавление к инцидентным удалённому ребру вершинам по одному новому ребру и добавление новой вершины, инцидентной этим двум рёбрам.

Граф G называется подразбиением графа H, если он может быть получен с помощью подразбиений рёбер графа H. Если подразбиения двух графов изоморфны, то сами графы гомеоморфны.

Полный граф - граф, две любые вершины которого смежные.

Полный ориентированный граф - орграф, в котором две любые вершины соединены парой дуг.

Пустой граф (нуль граф) - граф, не имеющий рёбер.

Тривиальный граф - граф, состоящий из одной вершины и не имеющий ребер.

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

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

Однородный (регулярный) граф степени d - граф, в котором все вершины имеют одну степень d.

Паросочетаемый граф - регулярный граф степени 1.

Кубический граф - регулярный граф степени 3.

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

Подграф - граф, содержащий некоторые вершины исходного графа и все рёбра, кроме тех, которые инциденты вершинам исходного графа, не вошедшим в подграф.

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

Длина маршрута (пути) - число рёбер (дуг).

Замкнутый маршрут - маршрут, в котором начальная и конечная вершины совпадают.

Простая цепь - незамкнутый маршрут, в котором все рёбра попарно различны.

Цикл - замкнутый маршрут, в котором все рёбра попарно различны.

Контур - цикл в орграфе.

Простой цикл (простой контур) - цикл (контур), в котором все вершины попарно различны.

Вершина A достижима из вершины В - если в орграфе существует путь от А к В.

Сильно связный орграф - орграф, в котором для любой пары вершин (а, b) существует как путь как из а в b, так и из b в а.

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

Разделяющая вершина (точка сочленения) - вершина графа, удаление которой из графа вместе с инцидентными ей рёбрами увеличивает число компонент связности.

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

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

Корень дерева - вершина с нулевой полустепенью захода.

Концевые вершины (листья) - вершины с нулевыми полустепенями исхода.

Двоичное дерево - ориентированное дерево, в котором каждая вершина имеет полустепень исхода либо 2, либо 0.