Материал: 1944
Свойства операций над множествами
|
Свойства множеств относительно |
Свойства множеств относительно |
|
операции объединения |
операции пересечения |
1. |
Коммутативность |
|
A B = B A |
A B = B A |
|
2. |
Ассоциативность |
|
(A B) C = A (B C) |
(A B) C = A (B C) |
|
3. |
Дистрибутивность |
|
A (B C) = (A B) (A C) |
A (B C) = (A B) (A C) |
|
4. |
Идемпотентность |
|
А А = А |
А А = А |
|
5. |
Закон де Моргана |
|
A B A B |
A B A B |
||||||||||
6. Операции с множеством |
A = |
||||||||||
A = А |
|||||||||||
7. Операции с множеством U |
A U A |
||||||||||
A U U U |
|
|
|
|
|||||||
|
U |
||||||||||
8. Законы поглощения: |
A (A B) = A |
||||||||||
A (A B) = A |
|||||||||||
A |
|
U |
A |
A |
|
||||||
A |
|||||||||||
9. Свойства операции разности: |
A\ B A |
|
, A \ A = |
||||||||
A \ (B C) = (A \ B) (A \ C) |
B |
||||||||||
(A B) \ C = (A \ C) (B \ C) |
A \ (B C) = (A \ B) (A \ C) |
||||||||||
(A \ B) \ C = A \ (B C) |
(A B) \ C = (A \ C) (B \ C) |
||||||||||
A \ (B \ C) = (A \ B) (A C) |
A \ (A \ B) = A B |
||||||||||
10. Свойства операции |
|
|
|
|
|
||||||
симметричной разности: |
|
|
|
|
|
||||||
A B = B A |
|
|
|
|
|
||||||
A B = (A B) \ (A B) |
|
|
|
|
|
||||||
(A B) C = A (B C) |
|
|
|
|
|
||||||
A (B C) = (A B) (A C) |
|
|
|
|
|
||||||
Бинарные отношения
Понятия |
Определения |
П р и м е р ы |
|
||
Декартово |
A B – множество, элементами |
A 1,2 ; B 2,3,4 |
|||
произведение |
которого являются всевоз- |
|
1,2 , 1,3 , 1,4 , |
|
|
множеств |
|
|
|
|
|
можные упорядоченные пары |
A B |
2,2 , 2,3 , 2,4 |
|
||
|
|
|
|||
А и B |
a,b , где a A,b B |
|
|
|
|
|
2,1 , 2,2 , 3,1 , |
||||
|
|
||||
|
|
|
|
|
|
|
|
B A |
3,2 , 4,1 , 4,2 |
|
|
|
|
|
|
||
|
|
|
|
|
|
104
Окончание таблицы
|
Понятия |
|
|
|
|
|
|
Определения |
|
|
|
|
|
|
|
П р и м е р ы |
|
|
|
|||||||||||||
|
Бинарное |
|
R |
|
– |
всякое |
подмножество |
|
x, y R "x меньше y" |
|||||||||||||||||||||||
|
отношение |
|
декартова |
произведения, |
|
т.е. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
R A B. |
Обозначение: |
x R y , |
|
R 1,2 , 1,3 , 1,4 |
, |
2,3 , |
2,4 |
|||||||||||||||||||||
|
|
|
|
т.е. х находится с y в отношении |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
R или x, y R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
Обратное |
|
|
R 1 |
a,b | |
b,a R |
|
|
R 2,1 , 3,1 , |
4,1 , |
|
3,2 , 4,2 |
||||||||||||||||||||
|
бинарное |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
отношение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Свойства |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Рефлексивность |
|
a A: |
a,a R |
|
|
|
|
(||),(~) |
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Антирефлексив- |
|
|
|
|
|
|
|
|
|
|
|
|
|
( ),( ), ( ) |
|
|
|
|||||||||||||||
|
|
|
|
|
a A: |
a,a |
|
|
R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
ность |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Симметричность |
|
a,b A: |
a,b R |
|
|
|
|
( ),(~),(||),( ) |
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
b,a R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
Транзитивность |
|
a,b,c A: |
a,b R |
|
|
( ),(~),(||),( ),( ),( ) |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
и b,c R a,c R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
Правила и формулы комбинаторики |
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
Правила комбинаторики |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
Правило умножения |
|
|
|
|
|
|
|
Правило сложения |
|
|
|
|||||||||||||||||||
|
Если |
из |
некоторого |
|
конечного |
|
Если |
из |
некоторого конечного |
|
||||||||||||||||||||||
|
множества объект а можно выбрать n1 |
|
множества |
|
объект |
|
а |
|
|
можно |
|
|||||||||||||||||||||
|
способами, а объект b – n2 способами, |
|
выбрать n1 |
способами, |
|
а объект |
|
|||||||||||||||||||||||||
|
то оба объекта (a и b) можно выбрать |
|
b |
– |
n2 |
|
способами, |
|
|
причем |
|
|||||||||||||||||||||
|
n1 n2 |
способами |
|
|
|
|
|
|
|
|
способы |
не |
пересекаются, |
то |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
любой из объектов |
|
(a |
|
|
или b) |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
можно |
|
выбрать |
|
|
|
|
n1 n2 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
способами |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Формулы комбинаторики |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
Схема выбора |
Размещения |
|
|
|
Перестановки |
|
|
|
|
Сочетания |
|
||||||||||||||||||||
|
Без |
|
Anm |
n! |
|
|
|
|
|
|
P |
n! |
|
|
|
Cnm |
|
|
n! |
|
|
|
||||||||||
|
|
(n m)! |
|
|
|
|
|
|
|
m!(n m)! |
|
|||||||||||||||||||||
|
возвращения |
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
С |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n! |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
Anm |
nm |
|
Pn(n1,n2,...,nm ) |
|
|
|
|
Cnm |
Cm |
|
|
|
|||||||||||||||||
|
возвращением |
|
|
n1!n2!...nm! |
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n m 1 |
|
||||||||||
105
Основные понятия теории графов
|
|
Понятие |
|
|
|
|
П р и м е р |
|
|
|||||
Граф |
G(V, X) |
представляет |
собой |
v2 |
x2 |
v3 |
|
|
||||||
непустое |
множество |
|
вершин |
|
x6 |
|
|
|||||||
|
|
|
|
|
|
|||||||||
V v1,v2,...,vn и множество ребер Х, |
x5 |
x3 |
v5 |
|
||||||||||
x1 |
|
|
|
|
||||||||||
оба |
конца |
которых |
принадлежат |
|
|
|
|
|
x7 |
v |
||||
множеству V |
|
|
|
|
|
|
v1 |
x4 |
v4 |
|
6 |
|||
|
|
|
|
|
|
|
|
|||||||
Если |
x (v1,v2 ) |
– |
ребро |
графа, то |
Вершины |
|
|
|
|
v2 и v4 |
||||
вершины v1 и v2 инцидентны ребру х |
инцидентны ребру x5 |
|
|
|||||||||||
Два ребра, инцидентные одной вершине, |
Ребра x1, x2 , x5 смежные, т.к. |
|||||||||||||
– смежные |
|
|
|
|
|
|
инцидентны вершине v2 |
|
||||||
Степень вершины d(v) графа – число |
d(v2 ) 3, |
|
вершина |
v5 |
– |
|||||||||
ребер, которым эта вершина инцидентна. |
|
|||||||||||||
Если |
d(v)=0, |
|
то |
|
вершина |
висячая, |
вершина |
v6 |
– |
|||||
изолированная, если d(v)=1, то висячая |
изолированная |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||
Маршрут (путь) |
для |
графа |
G(V,X) – |
v1x1v2x2v3x3v4x5v2 |
|
|||||||||
последовательность v1x1v2x2v3…xkvk+1. |
|
|||||||||||||
Длина маршрута – количество ребер в |
Если М=v1x1v2x2v3x3v4x5v2, то |
|||||||||||||
нем |
|
|
|
|
|
|
|
|
|
М |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Маршрут |
замкнутый, |
если |
его |
|
|
|
|
|
|
|
||||
начальная и конечная точки совпадают, |
v1x1v2x2v3x3v4x5v2x1v1 |
|
||||||||||||
т.е. v1 vk 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Незамкнутый маршрут (путь) – цепь. |
|
v2x2v3x3v4 |
|
|
||||||||||
Цепь, в которой все вершины попарно |
|
|
|
|||||||||||
различны, называется простой цепью |
|
|
|
|
|
|
|
|||||||
Замкнутый |
маршрут |
(путь) |
– |
цикл |
|
|
|
|
|
|
|
|||
(контур). Цикл, в котором все вершины |
|
v2x2v3x3v4x5v2 |
|
|
||||||||||
попарно различны, называется простым |
|
|
|
|||||||||||
|
|
|
|
|
|
|
||||||||
циклом. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Две вершины графа связные, если |
Вершины v1 и v3 связные, т.к. |
|||||||||||||
существует |
соединяющая |
их простая |
v1x1v2x2v3 |
|
|
|
||||||||
цепь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Два графа изоморфны, если существует взаимно-однозначное соответствие между множествами их вершин и ребер
106
|
|
|
|
|
|
Виды графов |
|
|
|||
|
|
Вид графа |
|
|
|
|
|
П р и м е р ы |
|
||
Граф связный, если каждые две его |
|
|
|
||||||||
вершины связные |
|
|
|
|
|
|
|
|
|||
Граф полный, если каждые две его |
|
|
|
||||||||
вершины соединены одним и только |
G1(X,V)– полный, связный и |
||||||||||
одним ребром |
|
|
|
|
|
||||||
Граф плоский (планарный), если его |
|
планарный |
|
||||||||
можно изобразить на плоскости так, |
|
|
|
||||||||
что все пересечения его ребер |
|
|
|
||||||||
являются вершинами графа |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
G2 (X,V) – плоское изображение |
|||
Граф G называется деревом, если он |
графа G1(X,V) |
||||||||||
|
|
|
|||||||||
является связным и не имеет циклов. |
|
|
|
||||||||
Граф G, все компоненты связности |
|
|
|
||||||||
которого |
|
являются |
деревьями, |
|
|
|
|||||
называется лесом |
|
|
|
|
|
|
G3(X,V) – лес |
||||
|
|
|
|
|
|
|
|
|
|||
Если |
элементы |
множества |
Х |
|
|
|
|||||
упорядоченные |
пары, |
то |
граф |
v2 |
x2 |
v3 |
|||||
называется |
ориентированным, |
или |
|
||||||||
орграфом. Если |
x (v ,v |
2 |
) – |
дуга |
|
x6 |
|
||||
|
|
|
1 |
|
|
|
x1 |
x5 |
x3 |
||
орграфа, то вершина v1 – начало, а |
|||||||||||
вершина |
v2 |
– конец дуги |
х. |
Дуга |
|
|
|
||||
x (v1,v1) |
– петля |
|
|
|
|
v |
x |
v |
|||
Степень входа вершины орграфа – |
1 |
4 |
4 |
||||||||
Вершина |
v2 – источник, вершина |
||||||||||
число входящих в вершину ребер, |
|||||||||||
степень выхода – число выходящих из |
v4 – сток. |
|
|||||||||
вершины ребер |
|
|
|
вершина, |
Путь : v2 v3 v4 |
|
|||||
Источником |
называется |
|
|
|
|
|
|||||
степень входа которой равна нулю, а |
|
|
|
||||||||
степень выхода положительна |
|
|
|
|
|
||||||
Стоком называется вершина, степень |
|
|
|
||||||||
входа которой положительна, а степень |
|
|
|
||||||||
выхода равна нулю |
|
|
|
|
|
|
|
|
|||
Путь в орграфе – последовательность |
|
|
|
||||||||
ориентированных ребер. |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
107 |
|
|
|
|
Цикл – замкнутый путь
Типы графов
Определение |
|
Условия существования |
|
Иллюстрирующие |
|||||||
|
|
|
|
|
|
|
|
|
примеры |
|
|
Путь |
|
(цикл), |
Критерий |
существования |
|
|
|
|
|
||
содержащий |
|
все |
эйлерова цикла: |
степени всех |
|
|
|
|
|
||
ребра |
графа |
и |
графа четные |
|
|
Есть |
эйлеров |
|
и |
||
притом |
по |
одному |
Критерий |
существования |
гамильтонов цикл. |
||||||
разу, |
называется |
|
|
|
|
|
|||||
эйлеровым |
путем |
эейлерова пути: |
граф имеет |
|
|
|
|
|
|||
(циклом). |
|
|
ровно две вершины нечетной |
|
|
|
|
|
|||
Граф, обладающий |
степени |
|
|
|
|
|
|
|
|||
эйлеровым |
циклом |
|
|
|
Есть |
эйлеров |
цикл, |
||||
(путем), называется |
|
|
|
но нет гамильтонова |
|||||||
эйлеровым |
|
|
|
|
|
цикла. |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
108