1.Тождества алгебры множеств

Мн-совокупность объектов обладающих одним и тем же определенным свойством.( мн стульев в комнате, то что можно посчитать)

Из этого следует, что во мн не должно быть неразличимых элементов. Элементами мн называются отдельные объекты из которых состоит мн. (3-эл мн нат чисел)

Элементы мн в свою очередь могут являться мн; { } – обозначение мн; А={ a,b,c}; {a,b,c}={b,c,a}; А,В- мн; а,в- элементы

Кортеж- это такое мн, в котором каждый его элемент занимает строго определенную позицию. (а1=а2)

2.Взаимосвязь лог терм и яз теории множ

Лог терминология	Язык теорий мн
«А или В»	А+В
«А и В»	АВ
«Не А»	A`
«Ни А, ни В»	(А+В)` или A`B`
« Не сразу А и В»	(АВ)` или А`+B`
«Всякое А есть В» или «Если А, то В» или « из А следует В»	АсВ
«Какое-то А есть В»	АВ ≠ нет значений
«Никакое А не есть В»	АВ=нет значений
«Какое-то А не есть В»	АВ`≠ нет значений
«Нет никакого А»	А= нет значений

4.Теорема о принципе вкл и исключений

Пусть даны подмн А1,…,Аn ( не обязательно различные) некоторого конечного мн и пусть требуется найти мощность их объединения А1 U…U An

В первой приближении этой мощности можно принять IA1I +…+IAnI это число будет слишком велико, поскольку имеет место пересечение, то принадлежащин пересечения будут подсчианы дважды

5. Следствие теоремы вкл и искл

Пусть Х-конечное мн; А1,…,Аn-его подмн; тогда:

IXIA1U…UAnI=IXI-(IA1I+…+I An-1 ∩AnI-…+(-1)^n I A1∩…∩AnI

Запишется в виде:

IAUBUCI=IAI+IBI+ICI-IA∩BI-IB∩CI-IA∩CI+IA∩В∩СI

A1≡A ; А2≡В; А3≡С

7.Теория графов

Достоинство-наглядность

Граф- это пара мн точек мн Ч называемых вершинами и направленным отрезком U, соединяющее вершины называющиеся дугами.

G(X;Y); Х- мн вершин; Y- мн дуг

Графы-матем аппарат при исследовании различных систем: эк, биолог, техн

Эк аппарат- совокупность матем методов, подходов, приемов для решения различных научно-практ задач на матем основе

Вся теория графов начаась с задачи о Кененсбергских мостах

9. Типы графов, ориентированный и неорентированный

Типы: Граф G = (X, A) называют полным, если для любой пары вершин хi и хj в X существует ребро (хi, хj) в неориентированном графе G=(X,A)т. е. для каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их

Граф G =(X, A) называется симметрическим, если в множестве дуг A для любой дуги (хi, хj) существует также противоположно ориентированная дуга (хj, хi)

Связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью, называется деревом

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

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

10. Элементы графов

Вершина=Узел

Ребро-отрезки, соед вершины в неориент графе

Дуга- отрезки соедин вершины ориент графа

11. Валентность и инцидентность

Валентность- Степень вершины — количество рёбер графа G, инцидентных вершине x. Обозначается d(x).

Инцидентность — понятие, используемое только в отношении ребра и вершины: если v_1, v_2 — вершины, а e=(v_1,v_2) — соединяющее их ребро, тогда вершина v_1 и ребро e инцидентны, вершина v_2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

12. Маршруты и циклы в графах Маршрутом в графе называют чередующаяся последовательность вершин и ребер, любые два соседних элемента являются инцидентными. Примечание если v₀=v_k, то маршрут замкнутый, иначе открытый. Длиной маршрута называется количество ребер в нем присутствующее( с допустимыми повторениями) Циклом называется конечная цепь, у которой начальная и конечная вершина совпадает.Циклы могут быть простыми и сложными. Простые циклы не содержат повторяющихся вершин, сложные могут содержать. Число циклов в графе обычно обозначается Z(G) Ацикличным называется граф, не содержащий циклов.

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

14.Понятие связности

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

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

15. задача о мостах; уникурсальный граф

Можно ли прогуливаясь по городу пройти каждый мост по 1 разу ( нечетное кол-во мостов)

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

16 Реш зад о мостах

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

17. Т Эйлера о сумме степеней + док

Сравниваем полустепени заходи и исхода ǀɣ(v1)ǀ=ǀ(v1)ǀ= 1

Поскольку полустепень исхода и захода всех вершин орграфа=, то по теореме 2 этот граф явл Эйлеровым

Эйлеров граф-граф, который содержит эйлеров цикл, включающий все ребра, каждая из которых проходится 1 раз.

18. Эйлеровы и гамильтоновы циклы

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

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

Гамильтонов граф-это граф, содержащий гамильтонову цепь или гамильтонов цикл.

19. планарный граф. Т Понтягина-Куратовского

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

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

Таким образом если граф имеет плоское изображение, то он планарный. Не всякий неограф является планарным .

Т Куратовскго: Неограф планарный тогда и только тогда, когда он не содержит подграф стягиваемых к К5 и К3,3

20. Теоремы планарности графов

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

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

21. Непланарные графы. Примеры

Признаки непланарных графов: достаточное условие: если граф содержит