Операции над множествами

Пересечение:

Объединение:

Разность:

Симметрическая разность:

Декартово или прямое произведение:

Вопрос2

1.Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

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

Билет 19

Вопрос 1

1. Отношение эквивалентности (∼) на множестве X — это бинарное отношение , для которого выполнены следующие условия:

1. Рефлексивность: для любого a в X,
2. Симметричность: если , то ,
3. Транзитивность: если и , то .

2.Совокупность всех классов эквивалентности называется фактор-множеством. Оно обозначается символом X/R.

3. Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств

Вопрос 2

3. Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

4. Необходимое условие:Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x(i) с локальной степенью p(x(i)) < 2.

Билет 20

Вопрос 1

1. Гру́ппа — непустое множество с определённой на нём бинарной операцией, удовлетворяющей указанным ниже аксиомам. Группы являются важными инструментами в изучении симметрии во всех её проявлениях. Примерами групп являются вещественные числа с операцией сложения, множество вращени плоскости вокруг начала координат и т. п.

2. Решётка в теории множеств — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю , так и точную нижнюю грани;

3. Унарная Алгебра - универсальная алгебра с семейством унарных операций

Унарной операцией или одноместной операцией на множестве M называется отображение множества в себя , которое каждому элементу множества M, называемомуоперандом, ставит в соответствие некоторый элемент того же множества, называемый результатом.

Простыми словами: Унарная операция — это операция над одним операндом (побитовое отрицание, унарный минус — меняет знак числа).

Вопрос 2

1. Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу
2. Эйлеров цикл — это эйлеров путь, являющийся циклом.
3. Теоре́ма Э́йлера в теории чисел гласит:

Если a и m взаимно просты, то , где φ(m) — функция Эйлера.