1.6.2. Элементы теории множеств

Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку. Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается . Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным.

Задать множество можно перечислением его элементов. Например, множество образованное из n элементов a1,a2,…,an , обозначается A={ a1,a2,…,an }; пишется aA (говорится «элемент a принадлежит множеству A»), если a является элементом множества А, в противном случае aA.

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

Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт A=B.

Множество А₁ называется подмножеством А (записывается А₁А), если все элементы множества А₁ являются элементами А.

Для множеств определены следующие операции: объединения, пересечения, дополнения.

Объединением множеств А и В (записывается AB) называется множество состоящее из элементов как одного так и второго множества. Например, A и B – множества точек принадлежащих некоторым двум кругам, имеющим общие точки, тогда объединением AB будет фигура, состоящая из общих точек.

Пересечением множеств А и В (записывается AB) называется множество, состоящее из элементов, принадлежащих как одному так и второму множеству одновременно.

Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается Ā=В-А.

1.6.3. Элементы теории графов Основные понятия

Г

.

раф задается парой множеств: множества E называемого множеством вершин и множества U, называемого множеством ребер. Ребро uU есть пара (e_i,e_j), где e_i,e_jE , указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро uU инцидентно вершинам e_i,e_j. Если порядок ребер не имеет значения, т.е.

u= (e_i,e_j)= (e_j,e_i), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро u= (e_i,e_j) называется ориентированным ребром или дугой. Вершина e_i - называется началом дуги, e_j – конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом.

Граф G(E,U) называется конечным, если множество E вершин конечно.

Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины e_i,e_jE называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине e_i, называется локальной степенью этой вершины (e_i). Число ребер r графа G(E,U) определяется выражением

, где n – количество вершин в графе.

Рассмотрим граф, изображенный на рисунке 1.8.

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

Множество вершин графа состоит из пяти элементов E={1,2,3,4,5}, а множество ребер U={(1,2),(1,4),(1,5),(2,3),(3,4),(5,3)}. Ребро (5,3) – является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины:

(1)=3; (2)=2; (3)=3; (4)=2; (5)=2; r=(3+2+3+2+2)/2=6

Важным в теории графов является понятие части графа G(E,U), который обозначается G(E,U)G(E,U)

Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа

EE UU

Многие задачи на графах состоят в определении частей графа с заданными свойствами.

Часть графа G(E,U)G(E,U) называется подграфом графа G(E,U), если EE , а подмножество UU образовано только ребрами инцидентными вершинам множества E.

Часть графа G(E,U)G(E,U) называется суграфом графа G(E,U), если EE , а подмножество UU образовано ребрами инцидентными вершинам множества E. В графе, изображенном выше, можно выделить подграф G(E,U), где E={1,2,3}, множество ребер U={(1,2),(2,3)} и суграф G(E,U), у которого E={1,2}, U={(1,2),(1,4),(1,5),(2,3)}.

Полным графом называется граф G(E,U), у которого каждая вершина e_iE соединена ребрами с остальными вершинами. Например,

Рис. 1.9. Полный граф