Между множествами А и В оставляет и объединяет в одно множество только те эллемнеты которые не пересекаются в двух этих множествах.

Графы

 

21Планарные

22Орграфы

23Смежность

24Связность

25матрица Инцидентности

26Виды графов. (циулические, планарные ориентированные их ребра не пересекаются,не ориентированные)
Диаметр графа

Кр.путь по графу..........................................9 алгоритм дейкстра

Укладка графа на сфере

Форм. Эйлера

Маршруты цепи циклы

Постр кр.пути

Алгоритм раскрашивания (теория раскраски графов 5 цв)

Эйлерова хар-ка
Гамильтонов цикл

Задача Комивояжера

тоерия раскрски графов

 

Деревья

Основные свойства деревьев

40корень ветки листья.

 

Множества
Множество – любая определенная совокупность объектов. Объекты – элементы множества.

Способы задания множества:

· Перечислением элементов

M={a, b, c, d,…}

· Характеристическим предикатом

M={x|x(P)}

· Порождающей процедурой

M={x|x=f(x)}

Мощность множества: |M|

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

Конечные множества – множества, состоящие из конечного числа элементов.

Бесконечные множества – множества, состоящие из бесконечного числа элементов. Например, множество натуральных чисел или универсум. Их нельзя задать перечислением.

Булеан – множество всех подмножеств множества. Число подмножеств конечного множества, состоящего из n элементов = 2ⁿ.

Операции над множествами: пересечение, объединение, разность, симметричная разность, декартово произведение

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

1. Пересечение множеств.

Определение: Пересечением множеств Х и У называется множество, состоящее из всех тех, и только тех элементов, которые принадлежат и множеству Х и множеству У.

Например: Х={1,2,3,4} У={2,4,6} пересечением {2,4}

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

Например: непересекающимися множествами являются множества отличников группы и неуспевающих.

Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих одновременно всем множествам.

Свойства пересечения:

1. X∩Y = Y∩X - коммутативности

2. (X∩Y) ∩Z =X∩ (Y∩Z)=X∩Y∩Z - ассоциативности

3. (UX)∩Y = U(X∩Y) - объединения

4. X∩Y=X (Х – нейтр.множество или эллемент)
5. Х∩Х=Х – идемпотентность

6. Х∩ᴓ=ᴓ - пустота

Объединение множеств

Определение: Объединением двух множеств называется множество, состоящее из всех и только тех элементов, которые принадлежат хотя бы одному из множеств Х или У.

Например: Х={1,2,3,4} У={2,4,6} объединением {1,2,3,4,6}

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

Свойства объединения:

1. XUY= ХUY- коммутативности

2. (X UY)UZ =XU (YUZ)=XUYUZ - ассоциативности

3. ∩АUB=∩(AUB) - дистрибутивность

4. ХUᴓ=X

5. XUX=X

Из свойств операций пересечения и объединения видно, что пустое множество аналогично нулю в алгебре чисел.

 

Разность множеств

Определение: Данная операция, в отличие от операций пересечения и объединения определена только для двух множеств. Разностью множеств Х и У называется множество, состоящее их всех тех и только тех элементов, которые принадлежат Х и не принадлежат У.

Например: Х={1,2,3,4} У={2,4,6} разность {1,3}

Как мы уже видели, роль нуля в алгебре множеств играет пустое множество. Определим множество, которое будет играть роль единицы в алгебре множеств

Свойства:
Вычитание множества из самого себя даёт в результате пустое множество:

Свойства пустого множества относительно разности:

Разность двух множеств содержится в уменьшаемом:

. Из этой формулы следует, что операция разности не является обратной операции суммы (то есть объединению).

Разность не пересекается с вычитаемым:

Разность множеств равна пустому множеству тогда, и только тогда, когда уменьшаемое содержится в вычитаемом:

между множествами А и В оставляет и объединяет в одно множество только те эллемнеты которые не пересекаются в двух этих множествах.

 

5. Декартово произведение

 

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

Ряд на ряд гл.диогональ граф.

 

Диагр. Венна придуманы для того,чтобы было проще работать над множествами.

Бинарные отношения

Бинарным отношением из множества в множество называется подмножество прямого произведения и и обозначается: . Часто используют инфиксную форму записи: .

Если отношение определено на множестве , то возможно следующее определение:

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

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

Область определения отношения R на A и B есть множество всех x ⋲ A таких,что для нектоорых y ⋲ В имеем (х,у) ⋲ R. Другими словами,область определения R есть множество всхе первых координат упорядоченных пар из R. Множество значений отношения R на А и В есть множество всех у ⋲ В таких,что (х,у) ⋲ R для некторого х ⋲ А. Другими словами, множество значений R есть множество всех вторых координат упорядоченных пар из R.

Пусть - отношение на А х В, а - отношение на В х С. Композицией отношений S и R называется отношение определенное таким образом:

Свойства:

Симметричность — это если для (x, y) выполняется отношение, то оно выполняется и для (y, x). Антисимметричность — это значит, что ни для какого (x, y), для которого выполняется отношение, не выполняется (y, x)
Рефлексивность значит, что если отношение P построено на множестве A (т.е. P ⊂ A2), то вся диагональ A2 (т.е. все возможные пары (x, x), x ∈ A) принадлежит отношению. Иррефлексивность — ни один элемент из диагонали отношению не принадлежит.
Транзитивность — если пара (x, y) принадлежит отношению, и пара (y, z) принадлежит этому же отношению, то пара (x, z) всегда принадлежит отношению.

ᴓᴉϵ϶Σ

Отношения эквивалентности

это бинарное отношение

R ⊆ A × A есть отношение эквивалентности, если оно

• рефлексивно

• симметрично

• транзитивно

Класс эквивалентности элемента а относительно

отношения эквивалентности R есть множество

{ x | x R a }

Фактор–множество множества A относительно

отношения эквивалентности R есть множество A / R

всех классов эквивалентности.