Основные понятия теории множеств. Способы задания множеств. Отношения бинарные и n-арные, страница 2

f : A®B отобр. функц-но.

5.  Функционалы.

f : F®D

Функция – совокупность всех его значений.

6.  Оператор.

Отношение, преобразующее одни ф-ции в другие.

БИНАРНЫЕ ОТНОШЕНИЯ НА МНОЖЕСТВЕ.

RÍх^2

Формы представления:

1.  формульное (символьное)

x={a,b,c,d}

R={(a,b),(b,c),(a,c)}

aRb – a в отношении b.

Отношения могут быть конечны и бесконечны.

2.  графическое а                  b

 

·

d                   c

3.  матричное

a   b   c

a b c   0	1	1
0	0	1
0	0	0

Строка и столбцы соответствуют элементам множества X

СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ : Х={…x y z …}

1.  Р – рефлексивность. a   b   c

1 1 1

Если х=у, то хRy

a

b

c

2.  И – иррефлексивность.

Если xRy, то х¹у.

a   b   c    

0 0 0

                              a

b

c

3.  С – симметричность.

Если xRy, то yRx.

4.  А – антисимметричность.

Если xRy и yRx, то х=у.

5.  Т – транзистивность.

Если xRy и yRz ,то xRz.

6.  Д – дихотомия.

Если х¹у, то xRy либо yRx.

1

d

c

e

a

b

                                         

6

2

5

4                      3    3

КЛАССЫ ОТНОШЕНИЙ.

1. Отношение эквивалентности : Р+С+Т. 

Наличие св-тв рефлексивности, симметр.,транзистивности.

Пример : группы студентов.

2. Отношение толерантности : Р+С .
3. Отношение совместимости.
4. Отношение порядка : Т+А .

Он делится на :

а)  нестрогий порядок : +Р;

б)  строгий : +И ;

в)  частичный : Т+А (пример – С).

г)  полный порядок : +Д .

5. Отношение лексико-графического порядка задаёт определённый тип n-арного отношения.

XiÎX^n ; (Xi^1, Xi^2, … , Xi^n)

Если Xi>Xj«( Xi^1> Xj^1 ) или (Xi^1= Xj^1) и (Xi^2 >Xi^2), то (Xi^1= Xj^1) и (Xi^2= Xj^2) и (Xi^3> Xj^3)

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

Абстрактный граф – G=(X,U), UÍX². Простой граф, в котором 2 любые вершины можно соединить ребром.

Графы могут быть конечными и бесконечными.

1.  Пустой граф, где X – любое, U=Æ;

2.  Полный граф, где X – любое, U=X²;

3.  Двудольные графы: UÍA´B;   X=AÈB;  AÇB=Æ ;

A={1,2,3};   B={8,9,10};

R={(a,b)/aÎA,bÎB,b-a>6}

1  8    

2  9

3  10

Степенью называется число дуг, инцидентных вершине.

Полу степени захода и исхода.

Мультиграф – граф, в котором две вершины могут быть соединены несколькими рёбрами. Граф ориентирован, если каждое ребро имеет направление (дуга). Пустой граф – не содержащий рёбер.

Полный граф:         С=n*(n-2)/2 .

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

Две вершины смежные, если они соединены ребром (т. е. В двудольном графе две вершины в одном подмножестве не смежные). Матрица смежности n´n. Если i,j вершины соединены ребром, то i-j клетка 1, иначе 0.

Понятие подграфа:

1.  V₁=VÇX₁´X₁    - обычный;

2.  V₁£VÇX₁´X₁    - частичный.

Понятие луча, цепи, маршрута.

Если между городами существует система дорог, то может возникнуть вопрос: можно ли проехать из A в B.

Первое ребро инцидентно А, последнее инцидентно В и любые два соседние ребра имеют общую вершину.