22. Формула де-Моргана:

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

Граф – это конечное множество Х, состоящее из n элементов называемых вершинами графа, и подмножество V декартова произведенияназываемое множеством дуг.

Граф, или неориентированный граф  — это упорядоченная пара , где  — это непустое множество вершин или узлов, а  — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе  — порядком, число рёбер  — размером графа.

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Графы делятся на два типа,обычные и сложные

Ориентированный граф

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

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

Смешанный граф

Смешанный граф  — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой , где , и определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы

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

24. Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Степенью графа называется величина 

Теорема . Сумма степеней всех вершин графа равна удвоенному количеству всех ребер

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

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

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