Универсальное множество. Дополнение множества до универсального множества.

Универсальное множество. Дополнение множества до универсального множества.

В конкретных математических областях бывает полезно ввести в рассмотрение столь обширное множество I, что все рассматриваемые множества окажутся его подмножествами. Такое множество I принято называть универсальным множеством или универсумом.Если выбрано некоторое универсальное множество I, то возникает новая теоретико-множественная операция — дополнение. Для всякого множества М (при этом подразумевается, что М — подмножество универсального множества I его дополнение, обозначаемое через М, — это множество всех элементов универсума, которые не принадлежат множеству М:

М = {х | х I и x M}

Таким образом, дополнение — это частный случай разности:

M = I \ M,
все отличие здесь состоит в том, что разность берется относительно фиксированного множества, содержащего все множества, которые в данной связи рассматриваются.

4. Объединение, пересечение и вычитание множеств.

а) Пересечением множеств М и N называют множество тех объектов, которые принадлежат множествам М и N одновременно.

Обозначение: М N = {х|х М и х N}.

б) Объединением множеств М и N называют множество тех элементов, которые содержатся по крайней мере в одном из множеств М или N. Обозначение: M N = {х | х М или х N}.

в) Разностью множеств М и N называют множество тех элементов, которые принадлежат множеству М и не принадлежат множеству N. Обозначение: М \ N. = {х | х М и х N}.

Свойства операций над множествами.

1. A U B = B U A - коммутативность. A n B = B n A

2. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C - ассоциативность.

3. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) - дистрибутивность.

4. Поглощение A U A = A, A n A = A.

5. Существование универсальных границ. А U 0 = A A n 0 = 0 A u U = U A n U = A

6. Двойное дополнение A = A

7. A U A = U A n A = 0

8. Законы двойственности или закон Де - Моргана
~~(AUB)~~ = A n B
~~(AnB)~~ = A U B

Отношения эквивалентности и порядка.

Отношение эквивалентности (отношение тождестваотношение типа равенства) — двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): 1. аксиоме рефлексивности (см. выше): xRx (предмет находится в отношении R к самому себе); 2. аксиоме симметричности (см. выше): xRy yRx (если предмет х находится в отношении R к предмету у, то и у находится в отношении R к х); 3. аксиоме транзитивности (см. выше): xRy& yRz xRz (если предмет х находится в отношении R к предмету у и у находится в отношении R к z, то х находится в отношении R к г).Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке^{[источник не указан 668 дней]}, подобие, одновременность. Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше». Отношения порядка — отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — «строгий» порядок.

Решение рекуррентных соотношений. Примеры.

некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой по следовательности соотношение тождественно выполняется. Решение рекуррентного соотношения k -го порядка называется общим, если оно зависит от k произвольных постоянных C1, K, C k и путем подбора этих постоянных можно получить любое решение данного соот ношения. математик Фибоначчи среди многих других задач привел следующую: пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов? Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через F( n ) количество пар кроликов по истечении n месяцев с начала года. Мы видим, что через n + 1 месяцев будет F( n ) и еще столько новорожденных пар кроликов, сколько было в конце месяца n - 1, то есть еще F( n - 1) пар кроликов. Иными словами, имеет место рекуррентное соотношение F( n + 1) = F( n ) + F( n - 1). Так как по условию F( 0) = 1 и F( 1) = 2, то последовательно находим F( 2 ) = 3, F( 3) = 5, F( 4 ) = 8 и т.д.

Производящие функции.

Пусть — произвольная (бесконечная) последовательность чисел (целых, рациональных, вещественных или комплексных). Производящей функцией (производящим рядом) называется запись вида Замечание. Не следует думать, что мы можем сказать, чему равно значение производящей функции в точке . Переменная является формальной, и ряд смысла не имеет. Единственное, что мы можем сказать про функцию , это что ее значение в нуле равно . Если, однако, производящий ряд является полиномом (т.е. все его коэффициенты кроме конечного числа равны нулю), то значение этого ряда в любой точке выражается конечной суммой и поэтому имеет смысл.

Маршруты, пути.

Маршрутом в графе называется чередующаяся последовательность вершин и рёбер vo, e1, v1, e2, v2,..., efc, Vfc, в которой любые два соседних элемента инцидентны. Если vo = Vk, то маршрут замкнут, иначе открыт. Если все рёбра различны, то маршрут называется цепью. Если все вершины

(а значит, и рёбра) различны, то маршрут называется простой цепью. В цепи vo, ei,..., еk-1, Vk вершины vq и Vk называются концами цепи. Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается (u, v). Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

32.Матричное задание графов.

Предположим, что все вершины и все ребра неориентиронеориентированного графа или все вершины и все дуги (включая петли) ориентированного графа пронумерованы начиная с единицы.

Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа nхm, где n — число вершин, a m — число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом: .

Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин, или булева матрица графа. Это квадратная матрица В порядка n, элементы которой определяют следующим образом:

для неориентированного графа Заметим, что в k-й строке матрицы ориентированного граграфа количество единиц равно полустепени исхода dg+ v_k вершины v_k, а количество единиц в k-м столбце dg- v_k — полустепени захода Для неориентированного графа матрица смежности вершин симметрическая.

Поиск маршрутов в графах.

Алгоритм (Тэрри ) поиска пути в связном графе, из вершины v i в вершину v j, где v i v j.

Исходя из вершины v i осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, по следующим правилам:

1. идя по произвольной дуге, всякий раз отмечать направление, в котором оно было пройдено;

2. исходя из некоторой вершины vk, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;

3. для всякой вершины vk, отличной от v i, отмечать первую заходящую в vk дугу, если вершина vk встречается в первый раз;

4. исходя из некоторой вершины, vk, отличной от вершины v i, по первой заходящей в vk дуге идти лишь тогда, когда нет других возможностей.

Путь в орграфе из вершины v i в вершину v j, где v i ` v j , называется минимальным , если он имеет минимальную длину среди всех путей орграфа из v i в v j.

Эйлеровы графы и циклы.

Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Связный граф называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым. Если граф обладает эйлеровым циклом, то он является связным, а все его вершины — четными.

39. Гамильтоновы графы и циклы.

Маршрутом (или путем ) в графе G называется чередующаяся последовательность вершин и ребер v₀, e₁, v₁, …, v_t_{− 1}, e_t, v_t₊₁, в которой e_i = v_i_{− 1}v_i (1 ≤ i ≤ t). Такой маршрут кратко называют ( v ₀, v_t )-маршрутом и говорят, что он соединяет v₀ c v_t; в свою очередь вершины v₀, v_t — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v₀, v₁, …, v_t своих вершин. Если v₀=v_t, то (v₀, v_t)-маршрут называется замкнутым. Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром ). Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.

Планарные графы.

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

Принцип Дирихле.

Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод дает неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путем явного построения или указания требуемого объекта, может привести к гораздо большим трудностям. Некоторые задачи решаются также методами, в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения (все они легко доказываются методом от противного).

а) Если на отрезке длиной 1 расположено несколько отрезков. сумма длин которых больше 1, то по крайней мере два из них имеют общую точку.

б) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2, то по крайней мере две из них имеют общую точку.

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

44.Сущность теории Рамсея. Теорема Рамсея. Числа Рамсея.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение: Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет. Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено. Можно заметить три очевидных факта, касающихся чисел Рамсея:
1. R(k, m) = R(m, k)
2. R(1, m) = 1
3. R(2, m) = m
Остальные числа вычисляются индивидуально.

Приложение теоремы Рамсея. Теорема Ван дер Вардена.

Головоломка о вечеринке представляет собой задачу, типичную для приложений теории Рамсея. Какое количество людей достаточно для того, чтобы образовать группу, в которой всегда окажется либо четверо людей знакомых друг с другом, либо четверо, друг с другом незнакомых? На этом рисунке гости представлены точками. Каждое красное ребро на этом графе соединяет гостей, знакомых друг с другом, а каждое синее — незнакомых. В группе из 17 точек, изображённых на рисунке, невозможно найти четыре точки для которых сеть соединяющих их рёбер была бы целиком красной или целиком синей Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось либо четверо знакомых, либо четверо незнакомых друг с другом. На самом деле во всякой группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо незнакомых друг с другом. Если множество всех натуральных чисел любым способом разбито на конечное число классов, то хотя бы один из этих классов содержит сколь угодно длинную арифметическую прогрессии.

Этот удивительный по простоте формулировки и очень нетривиальный по доказательству результат выдающийся российский математик и педагог Александр Яковлевич Хинчин (19.07.1894-18.11.1959) назвал одной из жемчужин теории чисел. Знаменитая теорема Ван дер Вардена утверждает, что для любых натуральных чисел n> 2, r> 1 найдется такое минимальное натуральное число W(n, r), что в любой раскраске множества натуральных чисел {1,..., W(n, r)} в r цветов найдется одноцветная арифметическая прогрессия длины n. Величину W(n, r) из теоремы Ван дер Вардена принято называть функцией Ван дер Вардена.