Дискретная математика. Множество

1. Федеральное государственное бюджетное образовательное учреждение высшего образования «КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра прикладной математики
ДИСКРЕТНАЯ МАТЕМАТИКА
Часть 1
курс лекций
Кемерово
2018
© С. Г. Гутова, 2018
© Кемеровский государственный
университет, 2018
ISBN 978-5-8353-1686-1
Об издании – 1, 2, 3
1

2.

ББК В19я73-5
УДК 519.6(075.8)
Г 89
Издается по решению редакционно-издательского совета
Кемеровского государственного университета
Составитель:
Гутова Светлана Геннадьевна – кандидат технических наук, доцент кафедры прикладной
математики
Г 89 Гутова, С. Г. Дискретная математика. Ч. 1: курс лекций [Электронный ресурс]: /
С. Г. Гутова; КемГУ. – Электрон. дан. (1 Мб). – Кемерово: КемГУ, 2018. – 1 электрон. опт.
диск (СD-ROM). – Систем. требования: Intel Pentium (или аналогичный процессор других
производителей), 500 МГц; 512 Мб оперативной памяти; видеокарта SVGA, 1280x1024
High Color (32 bit); 2 Мб свободного дискового пространства; операц. система Windows
ХР/7/8; Adobe Reader. – Загл. с экрана. – Номер гос. ре
ISBN 978-5-8353-1686-1
2

3.

Утверждено на заседании кафедры
прикладной математики
Протокол № 8 от «27 » марта 2018 г.
Заведующий кафедрой,
____________________ Е. С. Каган
Рекомендовано научно-методическим
советом института фундаментальных наук
Рекомендовано
Протокол № 8 от «19» апреля 2018 г.
Председатель совета доцент
_____________С. М. Сирик
© С. Г. Гутова, 2018
© Кемеровский государственный
университет, 2018
3

4.

Текстовое электронное издание
Минимальные системные требования:
Компьютер: Pentium 3 и выше, 500 МГц; ОЗУ 512 Мб; 2 Мб на жестком
диске;
видеокарта
SVGA,
1280x1024
High
Color
(32
bit);
привод
CD-ROM
Операционная система: Windows ХР/7/8
Программное обеспечение: Adobe Reader
© С. Г. Гутова, 2018
© Кемеровский государственный
университет, 2018
4

5.

Введение
Учебное (электронное) издание «Дискретная
математика. Ч.1.: курс лекций» разработано для
направления 01.03.02 «Прикладная математика и
информатика» в соответствии с требованиями ФГОС ВО и
включает теоретический материал, примеры решения задач,
снабжено анимацией.
В результате освоения данной дисциплины
формируются компетенции учебного плана по направлению
01.03.02 «Прикладная математика и информатика»:
ОПК-1 – способность использовать базовые знания
естественных наук, математики и информатики, основные
факты, концепции, принципы теорий, связанных с
прикладной математикой и информатикой;
ПК-2 – способность понимать, совершенствовать и
5
применять современный математический аппарат.

6.

Курс лекций может быть использован для
проведения лекционных занятий по дисциплине
«Дискретная математика» студентами направлений
02.03.02 «Фундаментальная информатика и
информационные технологии» и 02.03.03
«Математическое обеспечение и администрирование
информационных систем» и по дисциплине «Дискретная
математика и математическая логика» студентами
направления 02.03.01 «Математика и компьютерные
науки». Предназначено для студентов 1-2 курсов заочной
формы обучения Института фундаментальных наук.
Курс лекций может быть использован для полезен для
подготовки к занятиям студентами очной формы обучения
по указанным направлениям бакалавриата.
6

7. Оглавление

Введение
Лекция 1
Лекция 2
Лекция 3
Лекция 4
Лекция 5
Лекция 6
Лекция 7
Лекция 8
Лекция 9
Лекция 10
Лекция 11
Лекция 12
Лекция 13
Лекция 14
Лекция 15
Лекция 16
Лекция 17
7

8.

Введение
Курс лекций разработан по дисциплине «Дискретная
математика» для направления 01.03.02 «Прикладная математика и
информатика» в соответствии с требованиями ФГОС ВО и
включает краткий теоретический материал, примеры, снабжен
анимацией.
В результате освоения данной дисциплины формируются
компетенции учебного плана по направлению 01.03.02
«Прикладная математика и информатика»:
ОПК-1 – способность использовать базовые знания естественных
наук, математики и информатики, основные факты, концепции,
принципы теорий, связанных с прикладной математикой и
информатикой;
ПК-2 – способность понимать, совершенствовать и применять
современный математический аппарат.
8

9.

Курс лекций может быть использован для обеспечения лекционных
занятий по дисциплине «Дискретная математика» для студентов
направлений 02.03.02 «Фундаментальная информатика и
информационные технологии» и 02.03.03 «Математическое
обеспечение и администрирование информационных систем» и по
дисциплине «Дискретная математика и математическая логика» для
студентов направления 02.03.01 «Математика и компьютерные
науки». Предназначено для студентов 1-2 курсов заочной формы
обучения института фундаментальных наук
9

10. Лекция 1

Множества

11.

Множество – это совокупность
определенных различаемых объектов
таких, что для любого объекта можно
установить, принадлежит объект
данному множеству или нет.
Множество, которое подчиняется лишь
такому ограничению, может содержать
объекты почти любой природы.
11

12.

Георг Кантор определил множество так:
Множество – это многое,
мыслимое как целое.
12

13.

Например:
• множество всех станций Московского
метро;
• множество левых ботинок;
• множество натуральных чисел: 1, 2, 3, 4 и
т. д.;
• множество символов, доступных
специальному печатающему устройству;
• множество кодов операций конкретного
компьютера.
13

14.

• множество всех натуральных чисел: 1, 2, 3, . .
Обозначим N. Часто 0 считают натуральным
числом. Множество N с добавлением 0
обозначается N 0 .
• множество всех натуральных чисел, не
превосходящих 100.
• множество всех решений уравнения
sin x 1
14

15.

Множество обозначают заглавными
буквами, а его элементы – прописными.
А а1 , а2 , ..., аn
Говоря об определенном множестве, мы
полагаем, что для каждого объекта имеется
две возможности: элемент либо входит в
множество x X , либо нет x X .
Мощность множества – количество его
элементов.
Обозначение мощности: А .
15

16.

Множество, не содержащее элементов,
называется пустым множеством и
обозначается Ø.
Ø 0.
В зависимости от их мощности
множества различают как конечные или
бесконечные. Конечные множества могут
состоять из одного или нескольких
элементов.
16

17. Способы задания множества

Перечисление всех элементов множества
(список), например, множество однозначных
неотрицательных чисел
X 0,1,2,3,...9 .
Множества часто рассматриваются как
«неупорядоченные совокупности элементов»,
хотя иногда полезно подчеркнуть, что,
например
X 0,1,2 2,1,0 2,0,1 .
17

18.

Выяснить, какие из приведенных
определений верные?
В 1,2,3 .
С 5,6,6,7 .
D В , С .
18

19. Порождающая процедура

Описывает способ получения элементов
множества из уже полученных элементов
либо других объектов. Тогда элементы
множества – все объекты, которые могут
быть получены (построены) с помощью такой
процедуры.
19

20.

Множество М
2
n
натуральных степеней
двойки: 2, 4, 8, 16, 32, 64, 128…
Порождающую процедуру зададим
рекуррентно:
1 1 M 2n
2) m М 2 n ; 2m М 2 n
20

21. Пример 2

Какое множество задается рекуррентной
формулой: x1 1, xn xn 1 n
при n 2, x2 x1 2 1 2 2!
при n 3, x3 x2 3 2! 3 = 3!
при n 4, x4 x3 4 3! 4 = 4!
Множество, состоящее
из факториалов :1!, 2!, 3!, 4!,..., n!,...
21

22. Задание множества описанием его элементов (разрешающая процедура)

указание общего свойства, которым
обладают все элементы множества,
например, множество четных
натуральных чисел
или
X {2,4,6,8,10,12...}
X {x : x 2n, n N };
22

23.

Множество А называют подмножеством
множества В (обозначается A B ), если
каждый элемент множества А является также
элементом множества В.
Рис.1. Подмножество
23

24.

Множества А и В называют равными
( A B ), если каждый элемент множества А
является
одновременно
элементом
множества В и наоборот,
т.е. если A B и B A .
24

25.

Множество U называется
универсальным множеством (множество
элементов всех подмножеств) для некоторой
системы множеств, если каждое множество
этой системы является подмножеством U, т.е.
A U , B U ,C U ...
25

26.

Дополнением множества A называется
множество A , состоящее из тех и только тех
элементов универсального множества,
которые не входят в множество А.
Рис.2. Дополнение
множества
26

27.

Объединением двух множеств А и В
называется множество A U B , состоящее из
тех элементов, которые принадлежат или
множеству А, или В, или А и В
одновременно.
Рис.3.
Объединение
множеств
27

28.

Пересечением двух множеств А и В
называется множество A I B , состоящее из
тех и только тех элементов, которые
принадлежат множествам
А
и
В
одновременно.
Рис.4.
Пересечение
множеств
28

29.

Разностью двух множеств А и В
( A B или A \ B ) называется множество тех
элементов множества А, которые не
принадлежат множеству В:
A B AI B
Рис.5.
Разность множеств
29

30.

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

31. Пример 3

Заданы два множества: А = {-2, -1, 0, 1, 2}
и B = {0, 2, 4, 5}. Определить множества A B ;
A B ; A\ B ; B \ A и их мощность.
Решение:
Множество А = {-2, -1, 0, 1, 2} состоит из
пяти элементов, следовательно мощность этого
множества равна 5:
Аналогично, B = {0, 2, 4, 5} содержит 4
элемента:
31

32.

По определению пересечение двух
множеств состоит только из общих для обоих
множеств элементов, следовательно,
A B {0, 2} и
Пояснение:
A I B 0, 2
32

33.

По определению объединение двух
множеств состоит из всех элементов, которые
принадлежат только множеству А, или только
множеству В, или множествам А и В
одновременно, следовательно,
A B = {-2, -1, 0, 1, 2, 4, 5} и
Пояснение:
A U B 0, 2, 2, 1,
1, 4, 5
.
33

34.

Множество A\ B является разностью двух
множеств А и В и состоит из элементов
множества А, которые одновременно не
принадлежат множеству В, следовательно
Пояснение:
A\ B 2, 1, 1 .
34

35.

Аналогично,
Пояснение:
B \ A 4, 5 .
35

36. Пример 4:

A 2, 1, 0,1, 2 , B 0, 2, 4, 5
• Прямое (декартово) произведение:
A B = {(-2, 0); (-2, 2); (-2, 4); (-2, 5);(-1, 0);
(-1, 2); (-1, 4); (-1, 5);(0, 0); (0, 2);(0, 4);(0, 5);
(1, 0); (1, 2); (1, 4); (1, 5); (2, 0); (2, 2); (2, 4);
(2, 5)};
• B A = {(0, -2); (0, -1); (0, 0); (0, 1); (0, 2);
(2, -2); (2, -1); (2, 0); (2, 1); (2, 2); (4, -2); (4, 1); (4, 0); (4, 1); (4, 2); (5, -2); (5, -1); (5, 0).
(5, 1); (5, 2)}
36

37.

Из примера 2 видно, что
A B B A
A B B A A B 5 4 20.
37

38. Пример 5

На диаграмме Вьенна-Эйлера изобразить
результат действия А В С.
Решение:
Решаем по действиям. На каждой копии
диаграммы
необходимо
восстановить
контуры всех множеств, участвующих в
задании. Они должны пересекаться в самом
общем виде. Самый большой контур –
универсальное множество. Оно содержит в
38
себе все множества задачи.

39.

Основа
диаграммы
выполнения каждого действия.
для
Рис.6. Основа
диаграммы
для трех
множеств
39

40.

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

41.

Рис.7. Множества, вступающие в 1 действие
A
B
C
U
41

42.

42

43.

Рис.8. Множества, вступающие во 2 действие
A
B
C
U
43

44.

44

45.

Рис.9. Ответ
A
B
C
U
45

46. Лекция 2

Векторы и прямые
произведения множеств.
Проекция вектора на ось

47.

Векторы
Вектор – это упорядоченный набор
элементов. Его элементы зазываются
координатами или компонентами вектора.
Длина (размерность) вектора – число
координат вектора.
В отличие от элементов множества, его
координаты могут совпадать. Обозначение
вектора: в круглых скобках, координаты –
через запятую (0, 5, 4, 5, 0, 1). Иногда скобки и
даже запятые опускаются.
47

48.

Векторы длины 2 называют
упорядоченными парами; длины 3 –
тройками; и т.д., длины n – n-ками.
Два вектора равны, если они имеют
одинаковую длину, и соответствующие
координаты равны, т. е.
a1 , a2 , ..., am b1 ,b2 , ...,bn
если m n
и
a1 b1 , a2 b2 ,..., am bn .
48

49.

Прямое произведение n множеств
Прямое произведение множеств
A1 , A2 ,..., An
называется множеством всех векторов
(a1 , a2 ,..., an ), длины n таких, что
a1 A1 , a2 A2 ,..., an An .
Иначе говоря
A1 A2 ... An
a1 ,a2 ,...,an : a1 A1 ,a2 A2 ,...,an An .
49

50. Пример 1:

Найти прямое произведение множеств
A1 , A2 и A3 где
A1 0,1 , A2 т, п , A3 1,3 .
Перечисляем тройки элементов в лексикографическом порядке.
A1 A2 A3 0, т,1 , 0, т,3 , 0, п,1 ,
0, п,3 , 1, т,1 , 1, т,3 , 1, п,1 , 1, п,3 .
50

51.

Пусть А – конечное множество,
элементами которого являются символы
(буквы, цифры, знаки препинания, знаки
операций и т. д.). Такие множества обычно
называют алфавитом.
1)
2)
3)
4)
Примеры алфавитов:
33 русских буквы,
26 латинских букв,
10 арабских цифр;
список символов клавиатуры компьютера.
51

52.

Слова длины n в алфавите А – это элементы
множества An . Множество всех слов в
алфавите А – это множество
A U A A U A U ... U A U ...
i
1
2
n
i N
Здесь слово определено как вектор.
При написании слова не принято
пользоваться разделителями: скобками,
запятыми; они могут оказаться символами
самого алфавита. Поэтому слово в алфавите
обозначается как конечная последовательность
символов из алфавита А.
52

53. Пример 2:

1) Десятичное число – слово в алфавите цифр
{0, 1, 2, 3, ... , 9}.
2) Двоичное слово в алфавите {0, 1}.
3) Текст, отпечатанный на машинке – слово в
алфавите, определяемом клавиатурой этой
машинки.
53

54. Теорема (о мощности прямого произведения множеств)

Пусть A1 , A2 ,..., An
конечные множества и
A1 m1 , A2 m2 ,..., An mn .
Тогда мощность множества
A1 A2 ... An
равна произведению мощностей множеств:
A1 A2 ... An m1 m2 ... mn .
54

55. Следствие:

A A .
n
n
Например, множество
B3
двоичных
векторов длины 3, содержит
3
B3 B B 2 .
3
3
55

56. Проекции множества векторов на оси

Проекцией вектора
v a1 , a2 , ...,an
длины n на i-ю ось называется его i-я
координата. Обозначается это так:
прi v ai
Например:
v в , п , л , тогда пр1 v в , пр3 v л.
56

57.

Проекцией вектора v a1 , a2 , ...,an
длины n на оси с номерами i1 , i2 ,...,ik
называется вектор, составленный из
соответствующих координат. Обозначается
это так: прi1 , i2 , ...ik v ai1 , ai2 , ..., aik .
Например:
v в, п, л , тогда пр1,2 v в , п .
57

58. Пусть дано множество V векторов одинаковой длины.

Проекцией множества векторов на
i-ю ось называется множество проекций
на прi V прi v : v V .
i-ю ось всех его векторов. Обозначается
это так:
V a, b, c , d , c, a ,
Например:
пр2 V b, c , пр3 V c, a .
58

59.

Проекцией множества векторов на оси
с номерами
i1 , i2 ,...,ik
называется
множество проекций на оси с номерами
i1 , i2 ,...,ik всех его векторов. Обозначается:
прi1 , i2 , ...ik V прi1 , i2 , ...ik v : v V .
Например:V
a, b, c , d , c, a , тогда
пр1,2 V a ,b d ,c .
59

60. Пример 3:

Дано множество векторов:
V = {(Иванов Александр Николаевич),
(Иванов Михаил Александрович),
(Иванов Сергей Александрович)}.
пр1 V = {Иванов},
пр2 V = {Александр, Михаил, Сергей},
пр23 V = {(Александр Николаевич), (Михаил
Александрович), (Сергей Александрович)}.
60

61. Пример 4

Дано множество векторов
V v1 (a, b, d ); v2 (c, b, d ); v3 (d , b, b) .
Тогда
пр1v1 a – это вектор из одной координаты вектора v1 , а именно, первой
координаты;
пр3v2 d – это вектор из одной координаты вектора v2 , а именно, третьей;
пр 2 v 3 b – это вектор из одной координаты вектора v3 , а именно, второй;
61

62. Пример 4

V v1 (a, b, d ); v2 (c, b, d ); v3 (d , b, b)
пр1,2v2 c , b – это вектор из двух координат вектора v2 , а именно первой и
второй;
пр2,3v3 b, b – это вектор из двух координат вектора v3 , а именно второй и
третьей;
пр1,3v1 a , d – это вектор из двух координат вектора v1 , а именно первой и
третьей;
62

63. Пример 4

V v1 (a, b, d ); v2 (c, b, d ); v3 (d , b, b)
пр1V a , c , d
– это множество векторов,
составленных из первых координат элементов
V. Они все различны, поэтому пр1V 3 ;
пр2V b
– это множество векторов,
составленных из вторых координат элементов
V. Они все одинаковы, поэтому пр2V 1 ;
пр3V d , b –
это множество векторов,
составленных из третьих координат элементов
V. Две из трех одинаковы, поэтому пр3V 2 ;
63

64. Пример 4

V v1 (a, b, d ); v2 (c, b, d ); v3 (d , b, b)
пр1,2V a , b , c , b , d , b – это множество
векторов, составленных из 1-х и 2-х координат
векторов множества V.
пр2,3V b, d , b, b
– это множество
векторов, составленных из 2-х и 3-х координат
векторов множества V.
пр1,3V a , d , c, d , d , b – это множество
векторов, составленных из 1-х и 2-х координат
векторов множества V.
64

65. Лекция 3

Комбинаторика

66. Правило суммы

Классическая формулировка
Если элемент α можно выбрать k
способами, а элемент β можно
выбрать m способами.
Тогда α или β можно выбрать k + m
способами.
66

67.

Теорема о мощности объединения
множеств
(современная формулировка)
Количество элементов объединения
двух множеств равно сумме количества
элементов в первом и во втором множестве,
за вычетом количества элементов их
пересечения:
А В А B A B
67

68.

Причем, если множества не
пересекаются, то теорема приобретает
вид, аналогичный классической
формулировке:
А В А В
68

69.

Для трех множеств теорема имеет вид:
А В С А В С
А В А С В С А В С
69

70.

Пример 1
Из 35 учащихся класс по итогам года имели
“5” по математике – 14 человек; по физике – 15
человек; по химии – 18 человек; по математике
и физике – 7 человек; по математике и химии –
9 человек; по физике и химии – 6 человек; по
всем трем предметам – 4 человек.
Сколько человек имеют “5” по указанным
предметам? Сколько человек не имеет “5” по
указанным предметам? Имеет “5” только по
математике? Имеет “5” только по двум
предметам?
70

71.

Пример 1
Введем обозначения. Обозначим буквой U
множество всех учеников класса, буквой М
множество учеников, имеющих «5» по
математике, буквой Ф – имеющих «5» по
физике, Х – имеющих «5» по химии. Тогда,
согласно условию,
71

72.

Пример 1
На рисунке 1 приведено множество,
состоящее из учеников, имеющих «5» хотя бы
по одному из указанных предметов.
• Рис.1. Множество
учеников,
• имеющих «5» хотя
бы по одному
предмету
72

73.

Пример 1
Очевидно, что это объединение множеств
М, Ф и Х. Для нахождения количества
элементов объединения воспользуемся
правилом суммы.
73

74.

Пример 1
На рисунке 2 приведено множество,
состоящее из учеников, не имеющих «5» ни по
одному из указанных предметов. Обозначим его
буквой Н.
Рис. 2. Множество
учеников, не
имеющих «5» по
указанным
предметам
74

75.

Пример 1
Очевидно, что это разность между
универсальным множеством U и объединением
множеств М, Ф и Х.
75

76.

Пример 1
На рисунке 3 приведено множество,
состоящее из учеников, имеющих «5» только по
математике. Обозначим его буквами ТМ.
• Рис. 3. Множество
учеников, имеющих
«5» только по
математике
76

77.

Пример 1
Очевидно, что это разность между
множеством М и множествами ТМФ – имеющих
«5» только по математике и физике, ТМХ –
имеющих «5» только по математике и химии, и
77

78.

Пример 1
На рисунке 4 приведено множество,
состоящее из учеников, имеющих «5» только по
двум предметам. Обозначим его Т2. Очевидно,
что Т2 является суммой трех непересекающихся
множеств ТМФ,
ТМХ, ТФХ.
Рис. 4. Множество
учеников, имеющих
«5» только по двум
предметам
78

79. Найдем мощность каждой части искомого множества:

ТМФ М Ф М Ф Х ;
ТМХ М Х М Ф Х ;
ТФХ М Ф М Ф Х .
Тогда искомая мощность примет
вид:
Т 2 ТМФ ТМХ ТФХ
М Ф М Х Ф Х 3М Ф Х .
79

80. Правило произведения

Классическая формулировка
Если элемент α можно выбрать k
способами, а элемент β можно
выбрать m способами.
Тогда пару α и β можно выбрать km
способами.
80

81.

Теорема о мощности прямого
произведения множеств
(современная формулировка)
А В А В
81

82. Пример 2:

Из 3 экземпляров учебника алгебры,
7 экземпляров учебника геометрии и 6
экземпляров учебника физики, надо
выбрать комплект, содержащий все
учебники по одному разу. Сколькими
способами это можно сделать?
Ответ: 3 ⨉ 7 ⨉ 6 = 126.
82

83. Пример 2:

Из 10 арабских цифр составляют 5значный код. Сколькими способами это
можно сделать так, чтобы: а) все цифры
были разными; б) на последнем месте
четная цифра.
а) 10 ⨉ 9 ⨉ 8 ⨉ 7 ⨉ 6;
б) 10 ⨉ 10 ⨉ 10 ⨉ 10 ⨉ 5.
83

84. Число размещений без повторений

Число размещений без повторений из n
по k – это число способов, сколькими можно
из n различных элементов построить векторов
с k различными координатами.
Число размещений без повторений находится
по формуле:
k
Аn
n!
n k !
84

85. Число размещений без повторений

Пример 3:
Сколькими способами можно построить
3-значное число с различными цифрами, не
содержащее цифры 0?
9!
9! 1 2 ... 6 7 8 9
А
7 8 9.
9 3 ! 6!
1 2 ... 6
3
9
85

86. Число размещений с повторениями

Число размещений с повторениями из n
по k – это число способов, сколькими можно
из n различных элементов построить
векторов с k координатами, среди которых
могут быть одинаковые.
Число размещений с повторениями
находится по формуле:
k
n
В n
k
86

87. Число размещений с повторениями

Пример 4:
Сколько слов длины 6 можно составить
из 26 букв латинского алфавита?
6
26
В 26
6
87

88. Число перестановок без повторений

Число перестановок без повторений из
n элементов – это число способов, сколькими
можно расположить на n различных местах n
различных элементов.
Число перестановок без повторений
находится по формуле:
Рn n!
88

89. Задача на рассадки и расстановки

В задачах на рассадки и расстановки
используется тот факт, что
n различных элементов на
n различных местах
можно расставить n!
различными способами
89

90. Пример 5:

Сколькими способами можно расставить
на книжной полке 5 различных книг? В
скольких случаях две определенные книги А
и В окажутся рядом?
Всего вариантов расстановки 5 книг на 5
местах :
5!=120
90

91. Замечание:

В задаче на рассадки и расстановки число
элементов множества А ищут по формуле:
А х1 х2 х3 ,
где х1 – число способов выбрать нужные
места;
х2
– число способов расположить на них
нужные элементы;
х3
– число способов расположить
остальные элементы на оставшихся местах.
91

92. Рис. 5. Схема расстановки

1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
х1 4;
х2 2!; х3 3!;
A 4 2! 3!
92

93. Число сочетаний без повторений

Число сочетаний без повторений из n
по k – это число способов, сколькими можно
из n различных элементов выбрать k штук
без учета порядка.
Число сочетаний без повторений
находится по формуле:
n!
С
.
k! n k !
k
n
93

94. Свойства числа сочетаний

1) C 1;
2) C 1;
0
n
n
n
3) C n;
1
n
4) C
5) C C
k
n
6)
2
Cn
n k
n
n(n 1)
;
2
7)
n 1
n
3
Cn
n;
;
n n 1 n 2
.
3!
94

95. Урновая задача

Урновая задача – это задача, в которой
производится выбор сразу нескольких
элементов из заданной совокупности.
Пример 6:
В урне 7 шаров. Из них 3 белых, 4
черных. Наугад выбирают 3 шара.
Сколькими способами это можно сделать? В
скольких случаях среди них будет: 1) один
белый; 2) два белых; 3) все белые.
95

96. Схема урновой задачи

96

97. Общее число исходов эксперимента найдем по общей формуле

n!
С
.
k! n k !
k
n
7! 5 6 7
U С
5 7 35
3! 4! 1 2 3
3
7
97

98. Количество элементов множества А1 найдем по формуле:

А1
1
2
С3 С4
4 3
3
3 6 18.
2
98

99. Количество элементов множества А2 найдем по формуле:

А2
2
1
С3 С4
3 4 12.
99

100. Количество элементов множества А3 найдем по формуле:

А3
3
0
С3 С4
1 1 1.
100

101. Лекция 4

Соответствия

102.

Соответствия и функции
Соответствием множеств А и В
называется подмножество G такое, что
G A B.
Если (a, b) G, то говорят, что
«b соответствует a при соответствии G».
Область определения соответствия G
– множество пр1G A.
Область значений соответствия G –
множество пр2 G B.
102

103.

Соответствие G называется всюду
(полностью) определенным – если пр1 G = А
(в противном случае – частично
определенное соответствие).
Соответствие G называется
сюрьективным, если пр2 G = B.
103

104.

Образ элемента a пр1G в множестве B
при соответствии G – это множество всех
элементов b пр2G которые соответствуют a.
Прообраз элемента b пр2G в
множестве А при соответствии G – это
множество всех a пр1G которым
соответствует b.
104

105.

Образом множества C пр1G
называется объединение образов всех
элементов С.
Прообразом множества D пр2G
называется объединение прообразов всех
элементов D.
105

106.

Соответствие G называется
функциональным (однозначным)
соответствием, если образом любого
элемента из пр1 G является единственный
элемент из пр2 G.
106

107.

Соответствие G называется
инъективным соответствием, если
прообразом любого элемента из пр2 G
является единственный элемент из пр1 G.
107

108.

Соответствие F является функцией типа
F : A B, если оно функционально
(однозначно)
F (a ) b.
108

109.

Соответствие G является отображением
множества А в множество В, если оно
функционально и полностью определено.
Соответствие G является отображением
множества А на множество В, если оно
сюрьективно.
109

110.

Соответствие G является взаимно
однозначным, если оно:
1) всюду определено;
2) сюрьективно;
3) функционально;
4) инъективно.
110

111. Пример 1:

Определить свойства соответствия G
между множествами A и B.
A = {a, b, c}, B = {1, 2, 3}.
G = {(a, 2), (b, 2), (c,3)}.
111

112.

Область определения:
D(G) = пр1G = {a, b, c} = A, значит
полностью определено.
Область значения:
Е(G) = пр2G = {2, 3} ≠ B, значит не
сюрьективно.
112

113.

Образы элементов области определения:
G (a) = {2}; G (b) = {2}; G (c) = {3}.
Видим, что есть единственность образа,
значит соответствие функционально.
113

114.

Прообразы элементов области значений:
G
1
2 a,b ; G 3 c .
1
Нет единственности прообраза, значит не
инъективно.
114

115. Выводы:

1.Соответствие является функцией, так как
функционально.
2. Соответствие является отображением, так
как полностью определено и функционально.
3. Соответствие является отображением А в В,
так как не сюрьективно.
4. Соответствие не является взаимно
однозначным, так как не сюьективно и не
инъективно.
115

116. Пример 2:

Определить свойства соответствия G
между множествами A и B.
A = {a, b, c}, B = {1, 2, 3}.
G = {(b, 1), (b, 2), (c,3)}.
116

117.

Область определения:
D(G) = пр1G = {a, b} ≠ A, значит не
полностью определено
Область значения:
Е(G) = пр2G = {1, 2, 3} = B, значит
сюрьективно
117

118.

Образы элементов области определения:
G (b) = {1, 2}; G (c) = {3}.
Видим, что нет единственности образа,
значит соответствие не функционально.
118

119.

Прообразы элементов области значений:
G-1 (1) = {b}, G-1 (2) = {b}, G-1 (3) = {c}
Есть единственность прообраза, значит
инъективно.
119

120. Выводы:

1.Соответствие не является функцией, так как
не функционально.
2. Соответствие является отображением, так
как не полностью определено и не
функционально.
3. Соответствие не является взаимно
однозначным, так как не функционально и не
полностью определено.
120

121.

Преобразованием множества А
называется отображение типа A A.
Функция типа A1 A2 ... An B
называется n-местной функцией
f (a1 , a2 ,..., an ) b.
121

122.

Соответствие H B A называется
обратным к G A B, если Н таково, что
(b, a) H (a, b) G.
122

123.

Если соответствие, обратное к функции
f : A B является функциональным, то оно
называется функцией, обратной к f,
f
1
: B A.
123

124.

Пусть дана функция
Соответствие f
1
f : A B.
: B A.
является функцией тогда и только тогда, когда
1
f
f инъективна, и
является отображением
тогда и только тогда, когда f инъективна и
сюрьективна, то есть биективна.
124

125.

Утверждение:
Для функции f : A B
существует
1
обратная функция f
тогда и только тогда,
когда f является взаимно однозначным
соответствием между своей областью
определения и областью значений.
125

126.

Пусть даны функции
f : A B и g : B C.
Функция h : A C называется композицией
функций f и g, если
f g h( x) g ( f ( x)), x ∈ A.
Часто говорят, что h получена
подстановкой f в g.
126

127.

Для многоместных функций
f : A B и g : B n C возможны
m
различные варианты подстановки f в g,
задающие функции различных типов.
Например, при m = 3 и n = 4 функция
имеет 6 аргументов и тип B A B C ,
3
2
h g (b1 , f (a1 , a2 , a3 ), b3 , b4 ).
127

128.

Для множества многоместных
f1 : A A, ...
m1
fn : A
mn
A
функций типа возможны любые
подстановки функций друг в друга, а также
любые переименования аргументов.
Например, переименование x3 в x2 из
функции четырёх аргументов порождает
функцию трёх аргументов:
f ( x1 , x2 , x2 , x4 ) f ( x1 , x2 , x4 ).
128

129.

Функция, полученная из функций
f1 , ..., f n
некоторой подстановкой их друг в друга и
переименованием аргументов, называется
суперпозицией.
Выражение, задающее эту суперпозицию
и содержащее функциональные знаки, скобки
и символы аргументов, называется
формулой.
129

130. Взаимно однозначные соответствия и мощность множеств

Утверждение (о взаимно
однозначном соответствии равномощных
множеств):
Если между конечными множествами А
и В существует взаимно однозначное
соответствие, то А В .
130

131. Взаимно однозначные соответствия и мощность множеств

Доказательство:
1. Пусть мощность А больше, чем
мощность В.
131

132. Взаимно однозначные соответствия и мощность множеств

Тогда если выполняется свойство полной
определенности, то не выполняется свойство
инъективности.
132

133. Взаимно однозначные соответствия и мощность множеств

Доказательство:
2. Пусть мощность А меньше, чем
мощность В.
133

134. Взаимно однозначные соответствия и мощность множеств

Тогда если выполняется свойство
функциональности, то не выполняется
свойство сюрьективности, и наоборот.
134

135. Взаимно однозначные соответствия и мощность множеств

Таким образом, получили противоречие, что
доказывает истинность сформулированного
утверждения.
135

136.

Этот факт:
1) позволяет установить равенство
мощностей двух множеств, не вычисляя
мощностей этих множеств;
2) дает возможность вычислить мощность
множества, установив его взаимно
однозначное соответствие с множеством,
мощность которого известна или легко
вычисляется.
136

137.

На понятии взаимно однозначного
соответствия строится доказательство многих
важных теорем в теории множеств.
Теорема о числе подмножеств
конечного множества
Если мощность конечного
множества U равна n, то число
его подмножеств равно 2n .
137

138.

Доказательство:
Пусть элементы множества U
перенумерованы:
U = {a1 , a2 , a3 ,…, an }.
Установим взаимно однозначное
соответствие между множеством всех
подмножеств U –
булеаном ℬ (U) и множеством двоичных
векторов длины n – Вn.
138

139.

Доказательство:
Двоичный вектор
v = (v1 , v2 , v3 ,…, vn ), соответствующий
подмножеству М множества U: имеет
координату
vi = 0, если ai не принадлежит U;
vi = 1, если ai принадлежит U.
139

140.

Например:
Элементу булеана Ø соответсвует
двоичный вектор (0,
0, …, 0);
подмножеству
{a1} – (1, 0,…,0);
подмножеству
{a2} – (0, 1,…,0);
подмножеству
{a1 , a2 } – (1, 1,…,0);
подмножеству
U – (1, 1,…,1).
140

141. Теорема о числе подмножеств конечного множества

Таким образом, между множествами
ℬ (U) и Вn установлено взаимно
однозначное соответствие.
Согласно утверждению, их мощности
равны:
│ℬ (U)│= │Вn │= 2n .
141

142. Лекция 5

Отношения

143. Определение:

Подмножество R M
n
называется n -
местным отношением на множестве М.
Говорят, что a1 , a 2 , , a n находится в
отношении R, если (a1 , a 2 , , a n ) ∈ R .
143

144.

Одноместное отношение – это просто
подмножество М. Такие отношения называют
признаками: элемент а – обладает признаком
R, если R⊆ M и a ∈ R.
Свойства одноместных отношений это
свойства подмножеств М, поэтому для случая
n = 1 термин «отношение» употребляется
редко.
144

145.

Примером трехместного (тернарного)
отношения является множество троек
нападающих в хоккейной команде. Любой из
нападающих находится в этом отношении со
всеми теми игроками, с которыми он играет в
одной тройке (один нападающий может,
вообще говоря, участвовать более, чем в
одной тройке).
145

146.

При n = 2 – отношения называются
двуместными или «бинарными».
Если a и b находятся в отношении R,
это записывается aRb.
Таким образом, бинарное отношение,
заданное на множестве М, это любое
2
подмножество R ⊆ M .
146

147. Способы задания

Бинарные отношения задаются:
1) Списком;
2) Матрицей бинарного отношения;
3) Графом.
147

148. Задание списком

Списком задаются отношения, где М –
конечное множество, а R содержит небольшое
количество пар.
Пример 1:
M а , b , c – алфавит из трех букв, отношение
R – предшествования букв в алфавите. Тогда R
содержит пары:
R а, b , a, c , b, c .
148

149.

Матрица бинарного отношения,
заданного на множестве
M = {a1 , a 2 , , a n } это квадратная
матрица С порядка n, в которой cij
(где i – номер строки, j - номер столбца)
определяется так:
1, если ai Ra j ;
cij
0, в противном случае.
149

150. Пример 2:

M 1, 2, 3, 4
Отношение R – «быть больше или равно»
1 2 3 4
1 1 0 0 0
2 1 1 0 0
3 1 1 1 0
4 1 1 1 1
150

151. Задание графом

При задании графом, элементы М
сопоставляются одноименным точкам. Точки a
и b соединяются стрелками, если aRb.
Пример 3:
M 1, 2, 3 .
Отношение –
быть меньше.
Рис. 1. Задание
отношения
графом
151

152. Свойства бинарных отношений

Отношение R на М называется
рефлексивным, если для любого a ∈ M
выполняется a Ra.
Главная диагональ матрицы такого
отношения содержит только единицы, граф –
петлю в каждой вершине.
Пример 4: Отношение «быть делителем»,
заданной на множестве N. 1 делитель 1; 2
делитель 2; 3 делитель 3; и т. д.
152

153. Свойства бинарных отношений

Отношение R на М называется
антирефлексивным, если для любого
выполняется aRa.
a∈ M
Главная диагональ матрицы такого
отношения содержит только нули, граф – не
имеет петель.
Пример 5: Отношение «быть больше»,
заданной на множестве N. 1 не больше 1; 2 не
больше 2; 3 не больше 3; и т.д.
153

154. Свойства бинарных отношений

Отношение R на М называется
симметричным, если для любой пары
a ,b ∈ M из aRb следует bRa (то есть, для
любой пары отношение R выполняется в обе
стороны или не выполняется вообще).
Матрица симметричного отношения –
симметрична относительно главной диагонали,
у графа все стрелки парные, симметричные.
154

155. Пример 6:

• Отношение «жить в одной комнате в
общежитии».
• Если А живет в одной комнате с В, то и
В живет в одной комнате с А.
• Если С живет в одной комнате с D, то и
D живет в одной комнате с C.
• И так далее.
155

156. Свойства бинарных отношений

Отношение R на М называется
антисимметричным, если для любой пары
a ,b ∈ M из того, что одновременно выполняется:
aRb и bRa следует что a = b .
Матрица антисимметричного отношения не
имеет ни одной симметричной 1, у графа все
стрелки непарные, направлены лишь в одну
строну.
156

157. Пример 7:

• Отношение «быть начальником».
• Если А начальник В, то В не является
начальником А.
• Если C начальник D, то D не является
начальником C.
• И так далее.
157

158. Свойства бинарных отношений

Отношение R на М называется
транзитивным, если для любых трех
a ,b ,c ∈ M из того, что выполняется aRb и
одновременно bRc следует, что aRc.
Пример 8: Отношение «быть больше»,
заданной на множестве N.
если 3 больше 2 и 2 больше 1, то 3 больше 1;
если 5 больше 3 и 3 больше 1, то 5 больше 1;
и т.д.
158

159. Отношение эквивалентности

Отношение R на М называется отношением
эквивалентности,
если оно
Рефлексивно,
Симметрично,
Транзитивно.
159

160. Пример 9:

На множестве натуральных чисел
задано отношение R – иметь одинаковый
остаток от деления на 3.
R – рефлексивно, так как каждое
число само с собой имеет одинаковый
остаток от деления на 3,
например 1 и 1, 2 и 2, 3 и 3, и т.д.
160

161. Отношение: иметь одинаковый остаток от деления на 3

R – симметрично, так как каждое если число
а имеет с числом b одинаковый остаток от
деления на 3, то и число b с числом а тоже имеет
одинаковый остаток от деления на 3. Например,
1 и 4 имеют одинаковый остаток от деления на 3,
то и 4 и 1 тоже имеют одинаковый остаток;
2 и 5 имеют одинаковый остаток от деления на 3,
то и 5 и 2 тоже имеют одинаковый остаток;
3 и 12 имеют одинаковый остаток от деления на
3, то и 12 и 3 тоже имеют одинаковый остаток, и
161
т.д.

162. Отношение: иметь одинаковый остаток от деления на 3

R – транзитивно, так для каждых чисел
а , b и с если а с b имеют одинаковый остаток
от деления на 3, и b с с имеют одинаковый
остаток от деления на 3, то и а с с тоже
имеют одинаковый остаток от деления на 3,
например 1 и 4 имеют одинаковый остаток от
деления на 3, и 4 и 13 тоже имеют одинаковый
остаток от деления на 3, тогда 1 и 13 тоже
имеют одинаковый остаток.
162

163. Отношение: иметь одинаковый остаток от деления на 3

Таким образом, отношение R –
рефлексивно, симметрично и
транзитивно, то есть является
отношением эквивалентности.
163

164. Разбиение на классы эквивалентности

Если отношение R – отношение
эквивалентности, то оно разбивает
множество, на котором задано, на
классы эквивалентности.
164

165. Разбиение на классы эквивалентности

Для разбиения на классы надо:
1) Выбрать из М произвольный элемент a1 и
поместить его в класс C1 , затем поместить в этот
класс все элементы, эквивалентные ему;
2) Затем из оставшихся элементов М выбрать
элемент a2 и поместить его в класс C 2 , затем
поместить в этот класс все элементы,
эквивалентные ему;
3) Делать, пока останутся нераспределенные по
классам элементы.
Число классов разбиения – индекс разбиения I.
165

166. Отношение: иметь одинаковый остаток от деления на 3

Для разбиения на классы надо:
1) Выбрать произвольный элемент 1 и поместить его
в класс C1 , затем поместить в этот класс все
элементы, эквивалентные ему: 4, 7, 10, 13, ... ;
2) Затем из оставшихся элементов М выбрать элемент
2 и поместить его в класс C 2 , затем поместить в
этот класс все элементы, эквивалентные ему: 5, 8,
11, 14, 17, … ;
3) Затем из оставшихся элементов М выбрать элемент
3 и поместить его в класс C3 , затем поместить в
этот класс все элементы, эквивалентные ему: 6, 9,
12, 15, … Индекс разбиения равен 3.
166

167. Отношение порядка

Отношение R – отношение
порядка, если оно
антисимметрично и
транзитивно.
167

168. Отношение порядка

Отношение порядка R –
отношение строгого порядка,
если оно антирефлексивно,
антисимметрично и
транзитивно.
168

169. Отношение порядка

Отношение порядка R –
отношение нестрогого
порядка, если оно
рефлексивно,
антисимметрично и
транзитивно.
169

170. Отношение порядка

Если элементы a и b связаны отношением
порядка, то есть aRb или bRa, то a и b
сравнимы по отношению порядка R.
170

171. Отношение порядка

Если любые два элемента a и b сравнимы
по отношению порядка R, то R отношение
полного или линейного порядка, а М
называется полностью упорядоченным.
171

172. Пример 10: отношение «быть делителем», задано на N

R – рефлексивно, так как каждое число
является делителем самого себя:
1 делитель 1;
2 делитель 2;
3 делитель 3, и т.д.
172

173. Отношение «быть делителем», задано на N

R – антисимметрично, так как если числа
разные и a делитель b,то b не является делителем
a:
если 1 делитель 2 и 2 не делитель 1;
если 4 делитель 8, то 8 не делитель 4;
если 3 делитель 9, то 9 не делитель 3,
и т. д.
173

174. Отношение «быть делителем», задано на N

R – транзитивно, так как если числа разные и
a делитель b и b делитель с, то а тоже является
делителем с:
если 1 делитель 2 и 2 делитель 4, то 1 –
делитель 4;
если 4 делитель 8 и 8 делитель 24, то 4 –
делитель 24, и т. д.
174

175. Отношение «быть делителем», задано на N

R – рефлексивно, антисимметрично
и транзитивно, значит
R – отношение нестрогого порядка.
175

176. Отношение «быть делителем», задано на N

R – задает неполный порядок,
так как можно найти хотя бы одну пару
несравнимых элементов,
например: 2 и 3; 7 и 11; 4 и 9, и т.д.
176

177. Лекция 6

Операции и алгебры

178. Определение операции

N-арная операция на множестве М –
это функция типа
n
: М M,
где n – арность операции. Операция
замкнута относительно множества М по
определению, то есть операция над
элементами множества М, и результат
тоже элемент М.
178

179. Определение алгебры

Алгеброй называется множество М,
вместе с заданной на нем
совокупностью операций
1 , 2 , ... , n ,
то есть система
А M ; 1 , 2 , ... , n
179

180.

М – основное (несущее)
множество (носитель алгебры)
алгебры А.
Тип алгебры – вектор арностей
операций.
Сигнатура – совокупность
операций Σ.
180

181.

Множество M М
называется
замкнутым относительно n-арной
операции на М, если
М M ,
n
т. е. если значения на аргументе
из М' принадлежат М' .
181

182.

Если М' замкнуто относительно
всех операций 1 , 2 , ... , n ,
алгебры А с носителем М, то система
А M ; 1 , 2 , ... , n
называется подалгеброй алгебры А.
182

183. Пример 1:

Алгебра R, , – называется полем
действительных чисел.
Обе операции бинарные, поэтому
тип этой алгебры (2,2).
Сигнатура Σ , .
Подалгеброй этой алгебры является,
например, поле рациональных чисел.
183

184. Примеры 2:

Пусть N p 0, 1, 2, ... , p 1 .
Определим на N p операции:
– «сложение по модулю р»,
– «умножение по модулю р»,
следующим образом:
a b c и a b d,
где с и d – остатки от деления на р чисел
а + b и а b соответственно.
184

185. Пример 2:

Пусть, например, р = 7, тогда
N p = { 0,1, 2, 3, 4, 5, 6 }
и
3 4 0, 3 4 5, 4 6 3.
Часто обозначают:
a + b = с (mod p) и a b = d (mod p).
185

186.

Конечным полем характеристики р
называется алгебра
N p , , ,
если р – простое число.
186

187. Пример 3:

Булеаном U называется множество всех
подмножеств множества U
(обозначается ℬ(U)).
Булева алгебра множеств над U или
алгебра Кантора – алгебра (ℬ(U), , , )
Ее тип (2,2,1), сигнатура
, , .
187

188. Пример 3:

Для любого U ′ ⊂ U
B' = (ℬ(U'), U, ∩, ¬ )
– является подалгеброй В.
188

189. Пример 3:

Множество U={a, b, c, d}
тогда основное множество алгебры В
содержит 16 элементов.
B՛=(ℬ({a, b}),U, ∩, ¬ ).
является подалгеброй В.
189

190. Свойства бинарных алгебраических операций

Операция φ называется
ассоциативной, если для любых
элементов а, b, с .
a b c a b c a b c.
190

191. Пример 4:

1. Сложение и умножение чисел
ассоциативны, что позволяет не ставить
скобки в выражениях a b c a b c,
a b c a b c.
2. Возведение в степень
b
a a b
– не ассоциативна,
a b c a a
не равно
bc
a b c a .
так как
b c
bc
191

192. Пример 4:

3. Прямое произведение множеств не
ассоциативно: A 1, 2 , B a, b , C z .
A B C
1, a , z , 1, b , z , 2, a , z , 2, b , z ;
A B C
1, a, z , 1, b, z , 2, a, z , 2, b, z .
192

193. Свойства бинарных алгебраических операций

Операция φ называется
коммутативной, если для любых
элементов a, b
a b b a.
193

194. Пример 5:

1. Сложение чисел коммутативно
(«от перемены мест слагаемых сумма не
меняется»):
a b b a
2. Умножение чисел коммутативно («от
перемены мест множителей произведение
не меняется»):
a b b a
194

195. Пример 5:

3. Вычитание и деление – некоммутативные
операции: a b b a ; a / b b / a .
4. Умножение матриц – некоммутативная
операция, например:
1 2 2 2 2 3
;
0 1 0 1 0 1
2 2 1 1 2 4
.
0 1 0 1 0 1
195

196. Свойства бинарных алгебраических операций

Операция φ называется
дистрибутивной слева относительно
операции ψ, если для любых a, b, с
a b c a b a c .
196

197. Свойства бинарных алгебраических операций

Операция φ называется
дистрибутивной справа относительно
операции ψ, если для любых a, b, с
a b c a с b c .
197

198. Пример 6:

1. Умножение дистрибутивно относительно
сложения слева и справа
a b c a b a c ;
a b c a c b c .
198

199. Пример 6:

2. Возведение в степень дистрибутивно
относительно умножения справа.
a b c a b
c
a b a с b c .
c
c
199

200. Пример 6:

но не слева, так как
a b c a
b c
a b a c a a a
b
c
b c
.
200

201. Пример 6:

3. Сложение не дистрибутивно
относительно умножения
a b c a b a c ;
a b c a c b c .
201

202. Лекция 7

Гомоморфизм алгебр

203.

Алгебры разного типа, очевидно, имеют
существенно различное строение. Если же алгебры
имеют одинаковый тип, то наличие у них сходства
характеризуется с помощью вводимых ниже
понятий гомоморфизма и изоморфизма.
Пусть даны две алгебры
А K ; 1 , 2 , ... , n и В M ; 1 , 2 , ... , n
одинакового типа, т. е. арности 1 и ψ1 ; 2 и
ψ 2 , ...; п и ψ п
– одинаковы.
203

204.

Гомоморфизмом алгебры А в алгебру В
называется отображение
Γ : K М ,
удовлетворяющее условию:
i k1 , k 2 , ... , kl i i k1 , k 2 , ... , kl i
для всех i 1, 2, ..., n, ,
i m1 , m2 , ... , ml i
где l i – арность операций i и ψ i ).
204

205.

Смысл условия гомоморфизма:
a , b, c ∈ K ; Γ (a), Γ (b), Γ (c) ∈ M
независимо от того, выполнена ли сначала операция i в
множестве K и затем произведено отображение Г, либо
сначала произведено отображение Г, а затем в
множестве M выполнена соответствующая операция i ,
результат будет одинаков.
205

206.

Изоморфизмом алгебры А на алгебру В
называется взаимно однозначный гомоморфизм.
В этом случае существует обратное отображение
1: K M , так же взаимно однозначное.
1
m j .
k
Пусть k j m j , m j M . Тогда j
Поменяем в условии гомоморфизма левые части
1
к
этих равенств на правые и применим
обеим частям получившегося равенства. Так как
1 k k , то получим:
1 i k1, k2 , ..., kl (i ) 1 i m1, m2 , ..., ml (i ) ,
1
, получим
учитывая, что
i
m1 , 1 m2 , ..., 1 ml (i ) 1 i m1, m2 , ..., ml (i ) .
1
206

207.

Это тоже равенство с заменой Г на
1
, элементов множества K на
элементы множества М и переменой
1
ψ
местами i и i . Иначе говоря, – это
изоморфизм В на А.
Утверждение 1.
Если существует изоморфизм А на В,
то существует изоморфизм В на А; при
этом алгебры А и В называются
изоморфными.
207

208.

Утверждение 2.
Мощности несущих множеств
изоморфных алгебр равны (при
гомоморфизме это равенство может не
выполняться).
Автоморфизм на себя или
автоморфизм – это гомоморфизм при
условии, что А = В.
Изоморфизм
в
себя
–
изоморфизм В ⊂ А .
208

209.

Пример 1.
Пусть QN – множество всех целых чисел;
Q2 N – множество всех четных чисел.
(QN ;+)
(Q2 N ;+)
Алгебры
и
изоморфны.
Изоморфизмом является отображение : n 2n , причем,
условие гомоморфизма здесь имеет вид:
Г(a + b) = Г(a) + Г(b).
Поскольку
nо условие
равенства:
Г(a + b) = 2 (a + b),
Г(a) = 2a, Г(b) = 2b,
гомоморфизма примет
вид
истинного
2 (a + b) = 2a + 2b.
Поскольку Q2 N QN , то Г – изоморфизм алгебры
(QN ;+) в себя.
209

210.

Пример 2.
Пусть QZ – множество всех целых чисел;
Отображение:
: n 2n ,
является для алгебры QZ ; автоморфизмом.
Условие гомоморфизма здесь имеет вид:
Г(a + b) = Г(a) + Г(b).
Поскольку
Г(a + b) = – (a + b),
Г(a) = – a, Г(b) = – b,
то условие гомоморфизма примет вид истинного
равенства:
– (a + b) = (– a) + (– b).
210

211.

Пример 3.
Отображение:
: n ( n)
для алгебры (QN ;+) не является автоморфизмом, так как
условие гомоморфизма имеет вид:
a b a b .
Поскольку
a b a b ,
a a, b b,
то условие
равенства:
гомоморфизма
принимает
вид
ложного
a b a b .
211

212.

Пример 4.
Изоморфизмом между алгебрами R ; и R; , где
R+ – положительное подмножество R, является отображение:
а log a.
Условие гомоморфизма имеет вид:
a b a b .
и поскольку
a b log a b ,
то условие
равенства:
a log a, b logb,
гомоморфизма принимает
вид
истинного
log a b log a log b.
212

213.

Булевы алгебры Кантора
B = ( B(U), , , ), и B′ = ( B(U ′ ), , , ),
образованные двумя различными
множествами U и U΄ одинаковой мощности,
изоморфны. Операции у них просто
одинаковы, а отображением Г может служить
любое взаимно однозначное соответствие
между U и U΄ .

214.

Утверждение 3.
Отношение
изоморфизма
является
отношением эквивалентности на множестве
алгебр:
– рефлексивность отношения изоморфизма
очевидна;
– симметричность следует из существования
обратного изоморфизма;
– транзитивность устанавливается следующим
образом: если Γ1 – изоморфизм А на В, Γ2 –
изоморфизм В на С, то изоморфизмом А на С будет
композиция Γ1 и Γ2 .
214

215.

Классами эквивалентности в разбиении
по отношению изоморфизма являются классы
изоморфных между собой алгебр. Понятие
изоморфизма – одно из важнейших в
математике. Его сущность, как видно из
примеров можно выразить так: если алгебры А
и В изоморфны, то элементы и операции в В
можно переименовать так, что В совпадет с А.
215

216.

• Это позволяет получить такие соотношения в
алгебре А и автоматически распространить
их на все алгебры, изоморфные А.
Распространенное в математике выражение
«рассматривать
с
точностью
до
изоморфизма»
означает,
что
рассматриваются
только
те
свойства
объектов,
которые
сохраняются
при
изоморфизме, т. е. являются общими для всех
изоморфных объектов.
• В
частности,
изоморфизм
сохраняет
ассоциативность,
коммутативность,
дистрибутивность.
216

217. Лекция 8

Графы. Определения,
способы задания.
Виды графов.

218. Определение графа

Пусть V – множество вершин,
а Е – множество ребер.
Графом G называется пара объектов
(V, E) между которыми задано отношение
инцидентности:
Г : е → (v, w),
где вершина v и ребро e инцидентны друг
другу, если вершина является для этого ребра
концевой точкой.
218

219. Определение графа

Вершины v' и v" называются смежными,
если существует ребро, соединяющее их, т.е.
они инцидентны одному и тому же ребру.
Ребра e' и e" называются смежными,
если они имеют, по крайней мере, одну
общую вершину (инцидентны одной
вершине).
219

220. Определение графа

Граф, содержащий направленные ребра
(дуги) с началом v' и концом v" , называется
ориентированным графом (ор-графом). Для
ор-графа
v , v v , v .
Граф, содержащий ненаправленные ребра
с конами v' и v" , называется
неориентированным графом (н-графом).
Для н-графа
v , v v , v .
220

221. Определение графа

Рис.1 Неориентированное ребро (a,b)
Рис.2 Ориентированное ребро (a,b)
221

222. Определение графа

Ребро, концевые вершины которого
совпадают, называется петлей.
Рис.3.
Неориентированная
петля
Рис.4. Ориентированная
петля
222

223. Определение графа

Ребра (дуги), имеющие одинаковые
начало и конец, называются
параллельными или кратными.
Рис.5. Кратные неориентированные ребра
223

224. Определение графа

Рис. 6. Кратные ориентированные ребра
224

225. Определение графа

Ребра ор-графа, соединяющие одну и
туже пару вершин в разных направлениях
называются симметричными или
противоположно-направленными.
Рис. 7. Симметричные ребра
225

226. Определение графа

Граф называется конечным, если
множество его элементов (вершин и ребер)
конечно.
Рис. 8. Конечный граф
226

227. Определение графа

Граф называется бесконечным, если
бесконечно множество вершин или
множество его ребер.
Рис. 9. Граф с бесконечным числом вершин
227

228. Определение графа

Рис. 10. Граф с бесконечным числом ребер
228

229. Определение графа

Рис. 11. Бесконечный граф
229

230. Каноническое соответствие

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

231. Каноническое соответствие

Рис 12. Канонически соответствующие графы
231

232. Способы задания

Задать граф – значит описать множества
его вершин и ребер, а также отношение
инцидентности.
Пусть вершины графа v1 , v2 , , vn ;
e1 , e2 , , em ребра графа G.
Граф задают:
1) Матрицей инцидентности.
2) Матрицу смежности.
3) Списком ребер.
4) Рисунком.
232

233. Матрица инцидентности

матрица инцидентности
ij
размера m n (строкам соответствуют
ребра, столбцам – вершины графа), в которой
для н-графа
1, ребро ei инциндентно вершине v j ;
ij
0 , в противном случае.
233

234. Матрица инцидентности

для ор-графа
1, если вершина v j начало ребра ei ;
1, если вершина v j конец ребра ei ;
ij
, если ei петля вокруг вершины v j ;
0 в остальных случаях.
234

235. Пример 1: Рис.13 Матрица инцидентности н-графа

b c d
1 1 0 0 0
2 1 0 1 0
a
3 1 0
1 0
4 1
1 0 0
5 0 1 1 0
235

236. Пример 2: Рис. 14. Матрица инцидентности ор-графа

a b c
1 α 0 0
2 1 0 -1
3 1 0 -1
4 -1 1 0
5 0 -1 1
6 0 1 -1
d
0
0
0
0
0
0
236

237. Матрица смежности

Матрица смежности
ij
размера n n , столбцам и строкам которой
соответствуют вершины графа.
Для н-графа ij равно количеству ребер,
связывающих i-ю и j-ю вершины,
для ор-графа ij равно количеству ребер
выходящих из i-й и входящих в j-ю вершину.
237

238. Матрица смежности

• Матрица смежности н-графа всегда
симметрична.
• Матрица смежности ор-графа в общем
случае не симметрична.
• Она симметрична, если данному орграфу
есть канонически соответствующий н-граф.
238

239. Пример 3: Рис. 15. Матрица смежности н-графа

a
b c d
a
1
1 2 0
b
1 0
c
2
1 0 0
d
0
0
1 0
0 0
239

240. Пример 4: Рис. 16. Матрица смежности ор-графа

a
b c d
a
1
1 0 0
b
0
0
c
2
1 0 0
d
0
0 0 0
1 0
240

241. Список ребер

• Списком ребер можно задать граф без
кратных ребер.
• Ребро представляется парой вершин,
инцидентных ему, например е = (v, w).
• Для н-графа порядок вершин в строке
произволен, для ор-графа первым
стоит номер вершины–начала ребра.
241

242. Рисунок

• Рисунок или геометрическая
интерпретация появляется, если
сопоставить вершинам точки плоскости,
ребрам – линии на плоскости, причем,
линия соединяет только те точки, которые
соответствуют вершинам, инцидентным
данной линии-ребру.
• Граф для которого возможна
геометрическая интерпретация на
плоскости, называется планарным.
242

243. Пример 5: Рис. 17. Список ребер н-графа

E = {(a,a), (a,b), (a,c), (b,c)}.
243

244. Пример 6: Рис. 18. Список ребер ор-графа

E={(a,a), (a,b), (a,c), (с,a), (b,c)}.
244

245. Планарные графы

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

246. Планарные графы

• На рисунке приведен пример не
планарного графа
Рис. 19. Граф «три дома - три колодца»
246

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

Графы, отличающиеся только
нумерацией вершин, называются
изоморфными.
247

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

Рис.20. Изоморфные графы
248

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

• Графы, отличающиеся только
нумерацией вершин, называются
изоморфными.
249

250. Пустой и полный граф

Граф называется пустым, если
множество ребер пусто:
E Ø.
Рис. 21. Пустой граф
250

251. Пустой и полный граф

Н-граф называется полным, если
любые две вершины связаны ребром:
E V .
2
Рис. 22. Полный
н-граф
251

252. Пустой и полный граф

Ор-граф называется полным, если
любые две вершины связаны парой
симметричных
ребер:
Рис. 23. Полный
ор-граф
252

253. Двудольный граф

Граф называется двудольным если
множество его ребер разбито на два
подмножества,
V V1 V2 , V1 V2 Ø
и ребрами связаны только вершины из
разных подмножеств.
253

254. Двудольный граф

V1 a, b
V2 c, d , g
Рис. 6. Двудольный
граф
254

255. Двудольный граф

Граф называется полным
двудольным,
если каждая
вершина V1
Связана ребром
с каждой V2 .
вершиной
Рис. 24. Полный
двудольный граф
255

256. Двудольный граф

Если V1 n1 , а V2 n2 ,
то
полный двудольный граф обозначается:
K n1 ,n2
256

257. Двудольный граф

Рис. 25. Полный
двудольный граф
K1, 2 .
257

258. Двудольный граф

Рис. 26. Полный двудольный граф K 2 , 2 .
На рис. 24 приведен
пример
K 2,3 .
На рис. 19 приведен
пример
K 3,3 .
258

259. Лекция 9

Локальные степени вершин

260. Локальные степени вершин н-графа

Пусть G = (V, E) – н-граф.
Локальной степенью вершины v V
называется число ρ v равное числу
ребер, инцидентных вершине v.
При этом вклад петли в степень
вершины равен 2.
260

261. Локальные степени вершин н-графа

Вектор степеней н-графа
G = (V, E) – вектор размерности n,
составленный из степеней вершин графа,
расположенных по убыванию.
261

262. Локальные степени вершин н-графа

ρ(a)=5
ρ(b)=2
ρ(c)=3
ρ(d)=0
Вектор
степеней
ρ = (5, 3, 2, 0)
Рис.1 Степени
вершин н-графа
262

263. Локальные степени вершин н-графа

Замечание 1: векторы степеней
изоморфных графов одинаковы:
ρ = (5,3,2,0)
Рис. 2. Граф, изоморфный графу на рис.1
263

264. Локальные степени вершин н-графа

Замечание 2: Сумма всех локальных
степеней вершин
н-графа равна удвоенному количеству
ребер.
n
vi 2 e
i 1
число
ребер
н-графа.
e
264

265. Локальные степени вершин н-графа

Теорема
(о числе вершин нечетной степени)
Число вершин нечетной степени –
четно.
265

266. Локальные степени вершин н-графа

Доказательство:
vi 2 e .
Сумма в левой части равенства –
четна.
Если убрать все четные слагаемые,
сумма останется четной.
Сумма нечетных слагаемых четна,
если их четное число.
266

267. Локальные степени вершин н-графа

Однородным степени k
называется н-граф, локальные степени
которого одинаковы и равны k.
Для однородного графа степени k:
vi k v 2 e ,
k
e v , v число вершин.
2
267

268. Локальные степени вершин н-графа

Локально-конечным называется
н-граф, все локальные степени которого
конечны.
Рис. 3.
Локальноконечный,
бесконечный
однородный
граф степени 4.
268

269. Локальные степени вершин ор-графа

Пусть G = (V, E) – ор-граф.
Локальной степенью исхода
вершины v V называется число ρ
равное числу ребер, выходящих из
вершины v.
- v ,
269

270. Локальные степени вершин ор-графа

Локальной степенью захода
вершины v V называется число
ρ v равное числу ребер, входящих
в вершину v.
270

271. Локальные степени вершин ор-графа

Вектор степеней исхода
ор-графа G = (V, E) – вектор
размерности n, составленный из
степеней исхода вершин графа,
расположенных по убыванию.
271

272. Локальные степени вершин ор-графа

Вектор степеней захода
ор-графа – вектор размерности n,
составленный из степеней захода
вершин графа, расположенных по
убыванию.
272

273. Локальные степени вершин ор-графа

ρ a 3; ρ a 2;
ρ b 1; ρ b 1;
ρ c 1; ρ c 2;
ρ d 0; ρ d 0.
ρ 3,1,1, 0 ,
ρ 2, 2,1, 0 .
273

274. Локальные степени вершин ор-графа

Замечание 3:
Векторы степеней исхода и степеней
захода изоморфных графов одинаковы.
274

275.

ρ 3,1,1, 0 ; ρ 2, 2,1, 0 .
275

276. Локальные степени вершин н-графа

Замечание 4:
Сумма всех локальных степеней
исхода вершин и сумма всех
локальных степеней захода ор-графа
равна количеству ребер.
vi vi e .
n
i 1
n
i 1
276

277. Локальные степени вершин ор-графа

Однородным степени k
называется ор-граф, локальные
степени исхода и степени захода
которого одинаковы и равны k.
Для однородного графа степени k:
vi vi k v e ,
e k v .
277

278. Локальные степени вершин ор-графа

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

279. Лекция 10

Части графа.
Операции над частями графа

280. Часть графа

Пусть G = (V, E) – н-граф.
Частью (подграфом) графа G
называется граф Н =(V', E' ),
где V' V, E' E ,
причем все ребра множества E' входят в
граф Н вместе со своими концами.
280

281. Суграф

Подграф Н = (V', E' ), называется
суграфом, если V' = V.
Суграф называется
покрывающим, если каждая вершина
инцидентна хотя бы одному ребру
графа G.
281

282. Подграф, порожденным множеством вершин

Подграф Н = (V', E' ), называется
подграфом, порожденным
множеством вершин А V,
если V' = А, E' состоит из ребер
множества Е, соединяющих вершины
множества А.
282

283. Звездный граф

Подграф Н = (V', E' ), называется
звездным графом вершины
v V
если V' составляют вершина v и все
смежные ей вершины,
E' состоит из ребер множества Е,
инцидентных вершине v.
283

284. Пример покрывающего суграфа

G(V,E)
Н1 = (V', E' )
Рис.1. Покрывающий суграф
284

285. Пример непокрывающего суграфа

G(V,E)
Н2 = (V', E' )
Рис.2. Непокрывающий суграф
285

286. Пример подграфа, порожденного множеством А

G(V,E)
Н3 = (А, E' ), А={3,4,5,6}
Рис.3. Подграф, порожденный множеством А286

287. Пример звездного графа

G(V,E)
Н4 = (V', E' ) = Z(4)
Рис. 4. Звездный граф
287

288. Операции над частями графа

Суммой подграфов
Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется
граф Н = (V, E ),
такой что
V V1 V2 ,
Обозначается:
Е Е1 Е2 .
H H1 H 2 .
288

289. Операции над частями графа

Пересечением подграфов
Н1 = (V1, E1 ) и Н2 = (V2, E2 )
называется граф D = (V, E ),
такой что
V V1 V2 , Е Е1 Е2 .
Обозначается:
D H1 H 2 .
289

290. Операции над частями графа

Сумма подграфов
Н1 = (V1, E1 ) и Н2 = (V2, E2 )
называется прямой по ребрам, если у
них нет общих ребер:
E1 E2 Ø.
290

291. Операции над частями графа

Сумма подграфов
Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется
прямой по вершинам, если у них нет
общих вершин:
V1 V2 Ø.
291

292. Операции над частями графа

Дополнением подграфа
Н = (V1, E1 ) до графа G = (V, E )
называется подграф H V2 , E2 ,
где множество его ребер:
E2 E E1 ,
292

293. Операции над частями графа

а множество вершин V2 состоит из всех
вершин множества V, инцидентных
ребрам из Е2 и всех
изолированных вершин, не попавших
в множество V1.
293

294. Пример суммы подграфов

Н1 = (V1, E1 )
Н2 = (V2, E2 )
H H1 H 2
Рис. 5. Сумма подграфов
294

295. Пример пересечения подграфов

Н1 = (V1, E1 )
Н2 = (V2, E2 )
H H1 H 2
Рис. 6. Пересечение
подграфов
295

296. Пример суммы, прямой по ребрам

Н1 = (V1, E1 )
Н2 = (V2, E2 )
H H1 H 2
Рис. 7. Прямая по ребрам
сумма подграфов
296

297. Пример суммы, прямой по вершинам

Н1 = (V1, E1 )
Н2 = (V2, E2 )
H H1 H 2
Рис. 8. Прямая сумма
подграфов
297

298. Пример дополнения

Н = (V1, E1 )
G(V,E)
Рис. 9. Дополнение
H V2 , E2
298

299. Замечание:

Подграф и его дополнение являются
прямой суммой по ребрам:
Н H G.
299

300. Лекция 11

Маршруты.
Расстояние в графе

301. Маршруты

Пусть G = (V, E) – н-граф.
Маршрутом в графе G называется
чередующаяся последовательность
вершин и ребер
M v0 , e1 , v1 , e2 , ..., en , vn
где ребро
ei
инцидентно вершинам
vi -1 , vi .
301

302. Маршруты

Вершина v0 - начальная вершина
маршрута М,
vn – конечная,
vi – внутренняя вершина,
M v0 , vn маршрут
соединяющийv0 и vn .
Дина маршрута – число его ребер.
302

303. Маршруты

Маршрут М называется
маршрутом общего вида, если
вершины и ребра повторяются,
цепью – если его ребра не повторяются,
простой цепью – если его вершины не
повторяются.
303

304. Маршруты

Маршрут М называется
циклическим, если начальная и
конечная вершина совпадают.
Замечание: совпадают,
не значит повторяются.
304

305. Маршруты

Циклический маршрут М называется
маршрутом общего вида, если
вершины и ребра повторяются,
циклом – если его ребра не
повторяются,
простым циклом – если его вершины
не повторяются (кроме начала и конца).
.
305

306. Пример 1

М1 = (1, 2, 3, 4, 1, 3, 4, 5) – общего вида.
М2 = (1, 2, 3, 4, 1, 5) – цепь
М3 = (5, 6, 3, 4, 1) –
простая цепь.
Рис.1. Маршруты
306

307. Маршруты

М1 =(1, 2, 3, 1, 2, 3, 1) – циклический
маршрут общего вида.
М1 =(1, 3, 4, 5, 6, 4, 1) – цикл
(не простой)
М1 =(1, 2, 3, 4, 1) –
простой цикл.
Рис.2. Циклические
маршруты
307

308. Расстояния в графе

Расстоянием между вершинами a
и b называется длина минимальной
простой цепи, связывающей их.
Расстояние обозначается d(a, b).
Аксиомы метрики:
1) d(a, b) = d(b, a);
2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;
3) d(a, b) ≤ d(a, c) + d(c, b)
308

309. Расстояния в графе

Пример 2
1 2 3 4 5
Рис.3. Расстояния в
графе
1
2
3
4
5
0
1
1
2
1
1
0
2
1
1
1
2
0
1
1
2
1
1
0
1
1
1
1
1
0
309

310. Расстояния в графе

ri – эксцентриситет
i-ой вершины
– расстояние от этой вершины до
наиболее удаленной от нее вершины.
ri = max d(vi,vj)
по всем j от 1 до n.
310

311. Расстояния в графе

Диаметр графа G – максимальное
расстояние между вершинами графа
d(G)= max d(vi,vj)
по всем i и j от 1 до n, или
d(G)=max ri по всем i от 1 до n.
311

312. Расстояния в графе

Центр графа G – это вершина,
расстояние от которой до наиболее
удаленной вершины – минимальное.
Что бы найти центр, надо сначала
найти радиус графа.
312

313. Расстояния в графе

Радиус графа G –расстояние от
центра графа до наиболее удаленной
вершины.
r (G) = min ri
по всем i от 1 до n.
313

314. Расстояния в графе

Центр графа G –такая вершина vi,
для которой
ri = r(G).
Замечание:
Центр в графе может быть не
единственный.
314

315. Расстояния в графе

В нашем
примере
центром
является
вершина 5.
Радиус – 1,
диаметр – 2.
1 2 3 4 5 ri
1
2
3
4
5
0 1 1 2 1 2
1 0 2 1 1 2
1 2 0 1 1 2
2 1 1 0 1 2
1 1 1 1 0 1
315

316. Расстояния в графе

Диаметральные цепи графа G –
простые цепи, длина которых равна
d(G), соединяющие наиболее
удаленные вершины графа.
316

317. Расстояния в графе

Радиальные цепи графа G –
простые цепи, длина которых равна
r(G), соединяющие центр и наиболее
удаленные от него вершины графа.
317

318. Расстояния в графе

D1=(1,5,4), D2=(1,3,4),
D3=(1,2,4), D4=(2,5,3),
D5=(2,1,3), D6=(2,4,3),
R1=(5,1), R2=(5,2),
R3=(5,3), R4=(5,4).
Рис.4. Расстояния
318

319. Лекция 12

Связные компоненты графа

320. Связность

Пусть G = (V, E) – н-граф.
связными называются вершины a и b
если существуют маршрут,
связывающий их.
Н-граф G называется связным,
если все его вершины связны.
320

321. Связность

Утверждение: отношение
связности является отношением
эквивалентности.
Доказательство:
1.Каждая вершина связана сама с собой
маршрутом нулевой длины, значит
отношение связности рефлексивно.
321

322. Связность

2. Если вершина a связна с b, то и b
связна с a. Если a с b связаны
маршрутом М(a,b), то b с a связаны
маршрутом М(b,a), где ребра и
вершины идут в обратном порядке.
Значит отношение связности
симметрично.
322

323. Связность

3. Если вершина a связана маршрутом
с b, b связана с с, то и a связана
маршрутом с с.
Это маршрут, начало которого
М(a,b), окончание – M(b,c), вершина b
– общая.
Значит отношение связности
транзитивно.
323

324. Связность

Отношение рефлексивно,
симметрично и транзитивно,
значит является отношением
эквивалентности.
Множество вершин V
разбивается отношением связности
на классы эквивалентности –
подмножества связных вершин.
324

325. Связность

Связными компонентами графа
G называются подграфы,
порожденные классами
эквивалентности по отношению
связности.
Замечание: В связном графе
одна связная компонента.
325

326. Связные компоненты

V={a,b,c,d,g},
класс
V1 = { a,c,d
},
класс
V2 = {b,g}.
Рис. 1. Связные
компоненты 326

327. Разделяющие множества

Разделяющим множеством
н-графа G = (V, E) называется
множество ребер, при удалении
которых число компонент связности
графа увеличивается.
327

328. Разделяющие множества

Разрезом в н-графе G =(V, E)
называется разделяющее множество
в котором нет лишних ребер, то есть
минимальное разделяющее
множество.
328

329. Разделяющие множества

Мостом или перешейком
в н-графе G = (V, E) называется
разрез, состоящий из одного ребра.
329

330. Рис.2. Разделяющее множество

Разделяющее множество:
{(1,4), (2,3), (7,8)};
разрез:{(1,4), (2,3)}, (7,8) – лишнее;
мост :{(4,5) }.
330

331. Шарнир

Вершина v0 н-графа G = (V, E)
называется шарниром, если
удаление этой вершины и всех
инцидентных ей ребер приводит к
увеличению числа компонент
связности графа.
331

332. Шарнир

Рис.3. Шарнир в графе
Шарниром является вершина 4.
332

333. Лекция 13

Задачи об обходах

334. Задача о мостах Кёнигсберга

Рис.1. Карта мостов Кенигсберга
во времена Эйлера
334

335. Граф – схема мостов

Части города – вершины, мосты – ребра.
Из рисунка видно,
что задача,
поставленная
Эйлером,
не выполнима.
Рис.2. Граф,
соответствующий схеме мостов
335

336. Известные головоломки

Рис.3. Сабли Магомеда
Рис.4. Пентаграмма
336

337. Эйлеров граф

Эйлеровым циклом в н-графе
называется цикл, обходящий все ребра
графа (ровно по одному разу).
Эйлеров граф – граф, в котором
есть эйлеров цикл.
337

338. Полуэйлеров граф

Эйлеровой цепью в н-графе
называется цепь, обходящая все ребра
графа (ровно по одному разу).
Полуэйлеров граф – граф, в котором
есть эйлерова цепь.
338

339. Теорема Эйлера (условие эйлеровости графа)

Для того, чтобы произвольный
н-граф был эйлеровым, необходимо и
достаточно, чтобы
1) он был связен;
2) локальные степени всех его вершин
были четными.
339

340. Теорема (условие полуэйлеровости графа)

Для того, чтобы произвольный
н-граф был полуэйлеровым, необходимо и
достаточно, чтобы:
1) он был связен;
2) локальные степени всех его вершин,
кроме двух, были четными.
Вершины с нечетными степенями являются
началом и концом эйлеровой цепи.
340

341. Эйлеров, полуэйлеров, не эйлеров графы

Рис.5. Эйлеров граф
Рис.6. Полуэйлеров граф
Рис.7. Не эйлеров граф
341

342. Алгоритм Флери

При построении эйлерова цикла
начинаем с произвольной вершины и
двигаемся в произвольном направлении
выполняя два условия:
1) стираем пройденные ребра и
изолированные вершины, которые при этом
появляются;
2) идем по мосту, только если нет другой
342
возможности.

343. Рис. 8. Пример построения эйлерова цикла

343

344. Гамильтонов граф

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

345. Полугамильтонов граф

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

346. Гамильтонов, полугамильтонов графы

Рис.9. Гамильтонов граф
Рис.10. Полугамильтонов граф
346

347. Задача о кратчайшем пути

Пусть G = (V, E) – н-граф.
Пусть каждому ребру e графа
приписано положительное число –
длина ребра L(e).
Задача заключается в нахождении
маршрута от вершины a к вершине b,
наименьшей длины.
347

348. Алгоритм

Присвоим всем вершинам метки
s(v) = +∞, причем метка s(а) = 0.
Проверим каждое ребро (vi , vj) на
выполнение условия пересчета:
s(vj) - s(vi) > L(vi,vj).
Если это так, пересчитаем метку конца
ребра:
s(vj) = s(vi) + L(vi,vj).
348

349. Алгоритм

Совершаем пересчет меток до тех
пор, пока не перестанет выполнятся
указанное условие. Метка, которую
получила вершина b является длиной
искомого маршрута.
349

350. Пример 1

Рис. 11. Задача о кратчайшем пути
350

351. Задача о кратчайшем пути

1. 2,1 : s 1 s 2 L 2,1
s 1 s 2 L 2,1 0 1 1;
2. 2,3 : s 3 s 2 L 2,3
s 3 s 2 L 2,3 0 3 3;
3. 1,3 : s 3 s 1 2 L 1,3
s 3 3;
4. 1,5 : s 5 s 1 L 1,5
1
1
1
1
1
1
2
0
0
0
0
0
0
3
3
3
3
3
4
4
5
6
7
3
3
s 5 s 1 L 1,5 1 2 3;
5. 1,4 : s 4 s 1 L 1,4
s 4 s 1 L 1,4 1 3 4;
351

352. Задача о кратчайшем пути

6. 3,4 : s 4 s 3 1 L 3,4
s 4 4;
7. 3,7 : s 7 s 3 L 3,7
s 7 s 3 L 3,7 3 2 5;
8. 4,7 : s 7 s 4 L 4,7
s 7 5;
9. 5,7 : s 7 s 5 2 L 5,7
s 7 s 5 L 5,7 3 1 4;
10. 5,6 : s 6 s 5 L 5,6
s 6 s 5 L 5,6 3 4 7;
11. 7,6 : s 6 s 7 3 L 7,6
s 6 s 7 L 7,6 4 1 5.
1
1
1
1
1
1
1
1
1
1
1
2
0
0
0
0
0
0
0
0
0
0
0
1 0
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
6
7
3
3
3
3 5
3 5
3 4
3 7 4
3 5 3524

353. Задача о кратчайшем пути

Таким образом, длина кратчайшего
пути равна 5.
Возвращаясь от вершины 6
переходя к вершинам, инцидентным
ребрам, ведущим в вершину 6, доходим
о вершины 2.
μ = ( 2, 1, 5, 7, 6)
353

354. Лекция 14

Деревья

355. Определения дерева

Пусть G =(V, E) – н-граф.
Деревом называется связный
ациклический граф.
Рис. 1. Дерево
355

356. Определение леса

Лесом называется несвязный
ациклический граф.
Рис. 2. Лес
356

357. Теорема 1 (о деревьях)

Граф будет дерево тогда и только
тогда, когда любые две его вершины
связаны единственной простой цепью.
Связность дает наличие
такой цепи, ацикличность
– ее единственность.
Рис. 3. Теорема 1
357

358. Терема 2 (о деревьях)

Граф с n вершинами будет деревом
тогда и только тогда, в нем ровно n-1
ребро.
Если ориентировать
дерево о выбранной
вершины,
то в каждую вершину
будет входить 1 ребро,
а в а0 – 0.
Рис. 4. Теорема 2 358

359. Вершины максимального типа

Дано неориентированное дерево Т.
Концевые вершины дерева – вершины,
локальная степень которых равна 1.
Назовем их вершинами первого типа
дерева Т.
Рис. 5. Вершины
1 типа
359

360. Вершины максимального типа

Удалим из дерева Т ребра,
инцидентные концевым вершинам –
концевые ребра. Получим дерево Т1.
Концевые вершины
дерева Т1 – Вершины
типа 2.
Рис. 6. Вершины
2 типа
360

361. Вершины максимального типа

Удалим из дерева Т1 концевые ребра.
Получим дерево Т2.
Концевые вершины
дерева Т2 –
вершины
типа 3.
Рис. 7. Вершины максимального типа
361

362. Вершины максимального типа

Утверждение 1:
В конечном дереве есть вершины
только конечного числа типов.
Утверждение 2:
Вершин максимального типа k одна
или две.
362

363. Вершины максимального типа

Утверждение 3:
Центрами деревьев являются
вершины максимального типа k и
только они. Все диаметральные цепи
проходят через центры.
Длина диаметральной цепи равна
2k-1, если центра два и 2k-2, если центр
один.
363

364. Вершины максимального типа

k = 3 , центров два, длина диаметральной
цепи 2k-1=5.
Рис. 8. Диаметральная цепь
364

365. Корень дерева

Если дерево не ориентировано,
то его можно ориентировать от
корня.
Корень – это один из центров
дерева.
365

366. Корень дерева

У всех вершин дерева локальные
степени захода равны 1, а у корня 0.
Вершины, степени исхода которых
равны 0 называются листьями.
Высотой дерева называется
наибольшее расстояние от корня до
листа.
366

367. Рис. 9 Листья

Рис. 9 Листья367

368. Бинарное дерево

Бинарным деревом называется
ориентированное дерево с корнем,
где каждая вершина имеет локальную
степень исхода, равную 2.
368

369. Ветвь дерева

Ветвью вершины а в дереве Т
с корнем а0 называется подграф,
порожденный множеством
вершин В(а) состоящим из
вершин, связанных с корнем цепь,
проходящей через а.
369

370. Ветвь

t
Рис.10. Ветвь дерева
370

371. Лекция 15

Характеристические
числа графа

372. Цикломатическое число

Цикломатическим числом
графа G называется число ребер,
которые надо убрать, что бы граф
стал ацикличным.
372

373. Цикломатическое число

1.1
1.2
Рис.1. Цикломатическое число
373

374. Цикломатическое число

Цикломатическое число графа G
находится по формуле:
γ G e v с
e число ребер,
v число вершин,
с число компонент связности.
374

375. Цикломатическое число

Замечание 1: Цикломатическое
число дерева равно 0.
Замечание 2: Цикломатическое
число леса равно 0.
Замечание 3: Если
цикломатическое число графа равно 1,
то в графе ровно 1 цикл.
375

376. Цикломатическое число

Пример 1:
Рис. 3. Нахождение цикломатического числа
γ G e v с
7 5 1 3.
376

377. Цикломатическое число

Пример 2:
γ G e v с
10 7 2 5.
Рис.4. Цикломатическое число несвязного графа
377

378. Число внутренней устойчивости

Внутренне устойчивым
множеством графа G называется
множество вершин S, все вершины
которого попарно несмежны.
Число внутренней устойчивости:
α G max S .
S V
378

379. Число внутренней устойчивости

Пример 3:
Рис.5. Нахождение α(G)
S1 a , S 2 a, c , S3 g , c , S 4 a, d .
G max Si 2.
379

380. Число внешней устойчивости

Внешне устойчивым множеством
графа G называется множество
вершин Q, таких, что из всех вершин
множества Q ведут ребра в вершины
множества Q.
Число внутренней устойчивости:
G min Q .
Q V
380

381. Число внешней устойчивости

Пример 4:
Рис.6. Нахождение β(G)
Q1 a, b, c , Q2 g , d , Q2 b
G min Qi 1.
381

382. Хроматическое число

Граф G называется hхроматическим, если его вершины
можно раскрасить h различными
красками так, чтобы никакие две
смежные (различные) вершины не были
окрашены в один цвет. Хроматическое
число графа – это наименьшее число
красок.
G min h.
382

383. Хроматическое число

Пример 5:
Рис.7. Нахождение χ(G)
H1 a, d , H 2 g , c , H 3 b .
G min h 3.
383

384. Хроматическое индекс

Граф G называется kраскрашиваемым, если его ребра
можно раскрасить k различными
красками так, чтобы никакие два
смежные ребра не были окрашены в
один цвет. Хроматический индекс
графа – это наименьшее число красок.
G min k.
384

385. Хроматическое индекс

Согласно теореме Визинга, если
максимальная локальная степень
вершины графа равна k, то
хроматический индекс подчиняется
условию:
k G k 1.
385

386. Хроматическое число

Пример 6:
Рис.8. Нахождение χ'(G)
k max v b 4;
4 G 5;
G 4.
386

387. Пример 7:

В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут
быть источники излучения. Если
источники расположены в пунктах Xi и
Xj влияют друг на друга (поражают друг
друга), то на графе они соединены
ребром (Xi, Xj).
Можно ли расположить в каких-либо
из данных пунктов 4 или 3 источника, не
поражающих друг друга?
387

388.

Рис.9. Нахождение
максимального
внутренне
устойчивого
множества.
S1={X2, X5},
S2={X1, X4},
S3={X3, X6},
S4={X2, X4, X6}.
388

389. Пример 8:

Объекты Х1, Х2, … , Х9
расположены так, как показано на
графе. Объекты, которые
просматриваются друг из друга
соединены ребрами. Определить в
каких объектах достаточно поставить
камеры наблюдения, чтобы они в
совокупности просматривали все
объекты.
389

390.

Рис.10. Нахождение минимального
внешне устойчивого множества
390

391.

Пример 9: Дана политическая карта
континента. Найти минимальное число
цветов, чтобы раскрасить карту.
Рис.11. Раскраска
географической карты
391

392.

Рис.12. Замена
стран на
вершины, а
границ между
ними на ребра.
Найдем
хроматическое
число графа.
χ(G) = 3.
392

393.

Рис.13. Раскраска карты в три цвета
393

394. Лекция 16

Сети,
потоки в сетях

395. Введение

Сети – это графы, которые
моделируют реальные
транспортные и
коммуникационные сети.
395

396. Введение

Задача о максимальном потоке в сети
заключается в том, чтобы подсчитать
максимальное количество некоторых
объектов, которые могут двигаться от
одного конца сети к другому. При этом
пропускная способность узлов сети
ограничена.
396

397. Введение

Под объектами могут пониматься пакеты данных, путешествующих по
интернету;
- коробки с товарами, которые везут
по автомагистрали; и т. д.
397

398. Введение

Эта задача может использоваться
при составлении расписания авиарейсов,
распределения задач в
суперкомпьютерах, обработке цифровых
изображений и расположении
последовательности ДНК.
398

399. Введение

Перемещение объектов могут
ограничено пропускной способностью
соединений сети или скоростью
транспорта на загруженных дорогах.
399

400. Введение

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

401. Сети

Сетью называется частично
ориентированный граф G(V, E)
Истоком и стоком (входным и
выходным полюсом) называются
некоторые отмеченные вершины.
401

402. Сети

Исток – вершина, локальная
степень захода которой равна 0.
Сток – вершина, локальная
степень исхода которой равна 0.
402

403. Сети

Если в сети k истоков и
m стоков – сеть называется
(k,m)- полюсником.
Если в сети 1 исток и 1 сток, сеть
называется двухполюсной.
Далее будем рассматривать только
двухполюсные сети.
403

404. Сети

Пусть s – исток, t – сток, так что
любая другая вершина лежит на пути
из вершины s в t. Вершины, не
являющиеся истоком и стоком
называются внутренними вершинами
сети.
404

405. Сети

Разобьем множество вершин V на
два подмножества Х и Х таких, что
s Х , а t Х.
Множество ребер, реализующих
это разбиение назовем разрезом в
сети
R X, Х .
405

406. Сети

Ориентированные ребра с
Х
началом в Х и концом в
называются прямыми.
Множество прямых ребер
обозначим
E R .
-
406

407. Сети

Ориентированные ребра с
началом в Х и концом в Х
называются обратными.
Множество обратных ребер
обозначим
E R .
407

408. Сети

Все неориентированные
ребра являются прямыми.
Их ориентация произвольна,
и определяется при задании
потока в сети.
408

409. Сети

Замечание 1:
Прямым или обратным ребро
будет в зависимости от вида
разреза в сети.
409

410. Пример 1

Дана частично ориентированная
двухполюсная сеть.
410

411.

X s,1, 3 ; X t , 2, 4 .
R X , X 1,2 , 3,4 , 4,1 .
E R 1,2 , 3,4 ; E R 4,1 .
411

412.

X s, 3, 4 ; X t ,1, 2 .
R X , X s,1 , 1,3 , 4,1 , 2,4 , 4, t .
E R s,1 , 1,3 , 4,1 , 2,4 , 4, t ;
E R пусто .
412

413.

X s,1, 2 ; X t, 3, 4 .
R X, X s,3 , 1,3 , 4,1 , 2,4 , 2, t .
E R s,3 , 1,3 , 2,4 , 2, t ;
E
R 4,1 .
413

414.

X s,1, 3, 4 ; X t, 2 .
R X, X 1,2 , 2,4 , 4, t .
E R 1,2 , 2,4 , 4, t ;
E R пусто
414

415. Поток в сети

Пусть S произвольная частично
ориентированная сеть.
Пусть каждому ребру сети e E
приписано число
с(e) 0,
– пропускная способность ребра е.
415

416. Поток в сети

Потоком в сети S называется пара,
составленная из числовой и
нечисловой функций ( f ,w):
w – ориентация всех
неориентированных ребер сети,
f =f(e) – функция значений потока
на ребрах.
416

417. Поток в сети

Функция f удовлетворяет
условиям:
1) 0 f (e) c(e), e E;
2) выполняется закон Киргофа:
дивергенция любой внутренней
вершины сети равна 0.
417

418. Поток в сети

Дивергенция вершины сети – число
находимое по формуле:
R(a) f e f e .
e a
e a
a ребра, выходящие из а;
a ребра, входящие в а.
418

419. Поток в сети

Величина потока в сети S –
равна дивергенции потока в вершине
s (дивергенция истока).
R R(s).
419

420. Поток в сети

Замечание 2:
R ( s ) R t .
420

421. Поток в сети

Замечание 3:
Величина потока в сети есть
величина переменная, зависящая
от значений функции f(e).
421

422. Пример 2

Дана частично ориентированная
двухполюсная сеть. Найти величину
потока в сети.
422

423.

с(a)=2; c(b)=3; c(h)=1; c(d)=2; c(q)=1;
c(w)=1; c(x)=3; c(y)=2; c(z)=2.
423

424.

424

425.

425

426. Поток в сети

Каждому ребру разреза R
ставится в соответствие пропускная
способность разреза с(R), равная
сумме пропускных способностей
всех прямых ребер разреза.
426

427.

с(a) = 2; c(b) = 3; c(h) = 1; c(d) = 2;
c(q) = 1; c(w) = 1; c(x) = 3; c(y) = 2;
c(z) = 2. C = c(w) + c(d) = 3 + 1 = 4.
427

428.

C = c(b) + c(h) + c(x) + c(y) =
= 3 + 1 + 3 + 2 = 9.
428

429. Поток в сети

Теорема Форда-Фалкерсона
Максимальная величина потока
в сети S равна минимальной
пропускной способности среди
всех ее разрезов.
429

430. Лекция 17

Основы
теории кодирования

431. Основы теории кодирования

Кодом называется система условных знаков (символов),
для передачи, обработки и хранения информации.
Пусть А – произвольный алфавит. Элементы алфавита А
называются буквами, а конечные вектора, составленные из
букв – словами.
Длина слова – число букв в слове , обозначается .
Соединение слов 1 и 2 обозначим через 1 2 , а
соединение n одинаковых слов α – через n . Слово 1
называется началом слова α, если существует слово 2 ,
такое что 1 2 .
431

432. Основы теории кодирования

Пример 1:
Алфавит А={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Слова: натуральные числа, составленные их
цифр.
n1=23421, n2= 5600976, и так далее.
Двоичный код натуральных: разложение по
неотрицательным степеням 2.
код числа m1 = 3 – v1 =11;
код числа m2 = 4 – v2 =100;
код числа m3 = 6 – v3 =110;
код числа m4 = 12 – v4 =1100; и так далее.
432

433.

Рассмотрим алфавит Bk 0, 1, 2, ... , k 1 .
Произвольное
отображение
произвольного
множества М в множество слов в алфавите Bk
называется k-ичным кодированием множества М.
При k = 2, B2 B 0,1 – двоичное множество.
433

434.

Кодирование (отображение) Е – двоичная запись
натуральных чисел с помощью минимального количества
букв.
Числу n N 0 ставится в соответствие слово
b( n ) b1b2 ...bl( n ) ,
наименьшей длины, удовлетворяющее условию:
l( n )
n bi 2l( n ) i .
i 1
При этом b1 1, а длина слова l( n ) log2 n . Последнее
условие означает, что n удовлетворяет неравенству
2l( n ) 1 n 2l( n ) .
434

435.

Пример 2:
Пусть n = 12.
log2 12 3,59 , т. е. это дробное число между 3 и 4.
Инкремент этого логарифма равен l( 12 ) log2 12 4 , так
как это следующее целое, идущее за ним.
4
4 i
12
b
2
i
Аналогично 2 12 2 . Значит,
.
3
4
i 1
12 b1 2 b2 2 b3 2 b4 2
3
2
1
0
1 8 b2 4 b3 2 b4 1
1 8 1 4 0 2 0 1.
Таким образом, двоичный код числа 12 имеет вид:
b(12) = 1100 .
435

436.

Кодирование E m – двоичная запись натуральных чисел
с помощью m букв.
Числу n N 0 , удовлетворяющему условию
0 n 2m
ставится в соответствие слово
bm ( n ) 0m l( n ) b( n ) .
Пусть n = 12, m = 3.
3
Так как неверно то, что 0 12 2 , то это означает, что
код b3( 12 ) построить невозможно.
436

437.

Пример 3:
Пусть n = 12, m = 6.
6
0
12
2
Так как верно то, что
, то это означает,
что код b3( 12 ) построить можно, его вид:
b6 ( 12 ) 0
6 4
b( 12 ) 001100.
437

438. Побуквенное кодирование

Кодирование является
побуквенным, если каждой букве
алфавита ставиться в
соответствие двоичный код.
Код слова получается из
последовательной записи кодов букв.
438

439. Побуквенное кодирование

Пример 4: Алфавит А={a, b, c, d}
Двоичные код букв:
код буквы a – v1 =0;
код буквы b – v2 =11;
код буквы c – v3 =01;
код буквы d – v4 =011.
Тогда слово bc имеет код 1101. Его можно
однозначно разделит на коды букв.
Тогда слово ab имеет код 011. Его можно
декодировать как ab или как d.
439

440. Побуквенное кодирование

Побуквенный код называется
равномерным, если коды букв имеют
одинаковую длину.
Пример 5: Алфавит А={a, b, c, d}
Двоичные код букв:
код буквы a – v1 =000;
код буквы b – v2 =110;
код буквы c – v3 =010;
код буквы d – v4 =011.
440

441. Побуквенное кодирование

Побуквенный код называется
префиксным, если ни одно кодовое слово не
является началом другого кодового слова.
Пример 6: Алфавит А={a, b, c, d}
Двоичные код букв:
код буквы a – v1 =00;
код буквы b – v2 =10;
код буквы c – v3 =010;
код буквы d – v4 =011.
441

442. Побуквенное кодирование

Побуквенный код называется
разделимым,
если код слова можно однозначно
разделить на коды букв.
442

443. Побуквенное кодирование

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

444.

Оптимальное кодирование
Пусть источник случайным образом генерирует
буквы алфавита А а1 , а2 , ... , аm , причем вероятность
появления каждой буквы известна. Таким образом
задано распределение вероятностей Р вида:
… a
a
a
a
i
1
2
pi
p1
p2
m
…
pm
Так как алфавит фиксирован, то это распределение
можно записать в виде:
m
P p1 , p2 , ... , pm , p i 0, pi 1 444
.
i 1

445.

Оптимальное кодирование
Стоимостью
кода
распределении P назовем число
V
при
m
LV P vi pi .
i 1
Оно характеризует среднее количество
букв кодирующих слов, приходящихся на
одну букву алфавита А при кодировании V.
Очевидно, что при различных кодированиях
одного и того же алфавита, стоимость кодов
будет различной.
445

446.

Префиксный код V v1 , v2 , ..., vm
называется оптимальным при распределении
Р р1 , р2 , ..., рm , если его стоимость
минимальна по сравнению с другими кодами
алфавита А при распределении Р.
446

447.

Код Фано
Код Р. Фано, близкий к оптимальному,
заключается в следующем. Упорядоченный (в порядке
не возрастания вероятностей) список букв алфавита
делится на две последовательные части так, чтобы
суммы вероятностей входящих в них букв отличались
как можно меньше. Буквам из 1-ой части
присваивается символ 0, из 2-ой – 1. С каждой частью
поступают аналогично. Так делается пока, в каждой из
частей не окажется по одной букве. Полученные
последовательности нулей и единиц является кодом
Фано данного алфавита.
447

448. Пример 6:

Дано распределение частот для букв
алфавита. Построить код Фано. Найти
стоимость кода.
A
B
C
D
E
F
0,17 0,13 0,04 0,29 0,15 0,07
G
H
0,1
0,05
448

449. Код Фано

1. Упорядочить буквы по не
возрастанию частот.
A
B
C
D
E
F
0,17 0,13 0,04 0,29 0,15 0,07
G
H
0,1
0,05
449

450.

А
B
C
D
E
F
G H
0,17 0,13 0, 04 0, 29 0,15 0, 07 0,1 0, 05
450

451. Код Фано

1. Упорядочить буквы по не
возрастанию частот.
2.Разделить список на две
последовательные части так, чтобы
разница между суммами частот этих
частей была минимальна.
451

452.

D
А
E
B
G
F
H
C
0, 29
0,17
0,15
0,13
0,1
0, 07
0, 05
0, 04
0, 29 0,71 0, 42;
0, 46 0,54 0,08;
0, 46
0,54
0,61 0,39 0, 22.
452

453. Код Фано

1. Упорядочить буквы по не
возрастанию частот.
2.Разделить список на две
последовательные части так, чтобы
разница между суммами частот этих
частей была минимальна.
3. Сопоставить частотам первой части
символ 0, второй части сопоставить 1.
453

454.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
C
0,04
0,46
0,54
454

455. Код Фано

1. Упорядочить буквы по не возрастанию
частот.
2.Разделить список на две
последовательные части так, чтобы разница
между суммами частот этих частей была
минимальна.
3. Сопоставить частотам первой части
символ 0, второй части сопоставить 1.
4.С каждой из полученных частей
произвести аналогичное деление.
455

456.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
C
0,04
0,46
0,28
0,54
0,26
456

457.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
C
0,04
0,46
0,28
0,54
0,26
457

458.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
C
0,04
0,46
0,28
0,54
0,26
458

459.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
C
0,04
0,46
0,28
0,54
0,26
459

460.

D
0,29
A
0,17
E
0,15
B
0,13
G
0,1
F
0,07
H
0,05
00
01
100
101
110
1110
11110
C
0,04
11111
460

461. Стоимость кода

Стоимость кода V при распределении Р
находится по формуле:
Здесь
vi длина кодирующего слова vi ;
pi частота появления слова vi .
461

462.

D
A
E
B
G
F
H
C
L
2
2
3
3
3
4
5
0, 29
0,17
0,15
0,13
0,1
0, 07
0, 05
0, 04
00
01
100
101
110
1110
11110
11111
5
2, 79
462

463.

Код Хаффмена
Теорема Хаффмена
Если V v1 , v2 , ..., vm – оптимальный двоичный код
при распределении P p1 , p2 , ... , pm ,
и некоторая вероятность p j = q1 + q2 , причем
р1 р2 ... p j 1 p j p j 1 рm q1 q2 ,
то код V v1, v2 , ..., v j 1, v j 1, ..., vm , v j 0, v j1
так же является оптимальным при распределении
P p1 , p2 , ... , p j 1 , p j 1 , ... , pm , q1 , q2 .
Код V является расширением кода V .
463

464.

Код Хаффмена
Построение оптимального кода Хаффмена заключаются
в следующем. Пусть в упорядоченном по невозрастанию
вероятностей списке две последние вероятности pm 1 и pm .
Эти вероятности из списка исключаются, а их сумма
вставляется в список таким образом, чтобы вероятности попрежнему не убывали. Делаем так, пока в списке не
останется две вероятности. Первой из них присваивается
символ 0, второй – символ 1. Получаем оптимальный код,
состоящий из 2 кодовых слов. Далее, используя теорему
расширяем его до кода из 3 слов, и т. д. Пока не получим
список исходных вероятностей.
464

465.

ai
a
b
c
d
pi
xi
0,5
0
,5 0,5
00,2
,2 0,3
0,2
0,1
0,5 0
1
1
00
0
1
01
0 000
1 001
465

466. Стоимость кода

Найдем стоимость полученного кода.
4
LV P vi pi
i 1
0,5 2 0,2 3 0,2 0,1 1,8.
.
466

467.

Рассмотрим
равномерный
код
с обнаружением и исправлением ошибок.
Однозначной ошибкой типа замещения
называют результат замены одного из символов
0 на 1 или 1 на 0.
Кратностью ошибки s называется число
ошибок
одного
типа.
Например,
если
передаваемое слово x = 1011, а на приемной
станции получено у = 0011, то в слове
произошла ошибка типа замещения.
467

468.

Функция Хемминга H(x), задается на двоичных
n
B
∈
x
. Это вектор минимальной длины l,
векторах
полученный в результате покоординатного сложения по
модулю 2 двоичных кодов номеров тех координат
вектора х, которые равны 1.
Здесь l – та длина двоичного кода, которой
достаточно, чтобы закодировать номера всех координат
слова х.
l log 2 n 1 .
Таким образом,
H x x1 bl 1 x 2 bl 2 ... x n bl n .
468

469.

Пример 8:
Найти функцию Хемминга для двоичного слова
x = 1011. Так как n = 4 , то
l log 2 4 1 log 2 5 3 . Найдем двоичные
коды длины 3 для всех номеров координат слова х .
1
2
3
4
n
b3 (n)
001
010
011
100
Тогда
H x 1 001 ⊕0 010 ⊕1 011 ⊕1 100 =
= (001) ⊕(011) ⊕(100) =
= (0 ⊕0 ⊕1, 0 ⊕1⊕0, 1⊕1⊕0)= (110) .
469

470.

Кодом
Хемминга
называется
подмножество
n
H
∈
B
двоичных слов
, для каждого из которых
n
функция Хемминга равна нулевому вектору. Таким
образом x 1011 H 3 .
Утверждение 4:
n
x
∈
B
Количество двоичных слов
, принадлежащих
n l
H
2
коду Хемминга равно
.
n
Теорема Хемминга
Код Хемминга является кодом с исправлением одного
замещения.
470

471.

Пример 9:
Пусть при передаче по каналу связи в двоичном слове
x = 010101∈ H 6 произошло замещение 5-ого символа, в
результате чего получилось слово y = 010111. Найдем
функцию Хемминга H ( y) . l log 2 6 1 log 2 7 3 .
Сложим по модулю 2 двоичные коды номеров только тех
координат вектора у, которые равны 1.
H у 010 ⊕ 100 ⊕ 101 ⊕ 110 101 b3 5 .
Полученный результат является двоичным кодом номера
того места, на котором произошло замещение.
471

472.

Литература
1. Теория вероятностей и математическая статистика [Текст]:
практикум / Кемеровский гос. ун-т; [сост. С. Г. Гутова]. - Кемерово:
КемГУ, 2017. - 185 с.: рис., табл.
2. Дискретная математика: учеб.-метод. Пособие [Текст] /
ФГБОУ ВПО «Кемеровский государственный университет»; сост.
С. Г. Гутова, Т. А. Невзорова. – Кемерово, 2011. – 128 с.
3. Кузнецов, О. П. Дискретная математика для инженера [Текст]
/ О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат,
1986. – 480 с.
4. Чуешева, О. А. Математическая логика: учеб.-метод. пособие
[Текст] / сост. О. А. Чуешева. – Кемерово, 2006. – 48 с.
5. Щекочихина, С. Г. Дискретная математика: вопросы для
самостоятельного изучения для студентов 1 курса МФ спец. 01.02. /
[Текст] / С. Г. Щекочихина. – Кемерово: Кузбассвузиздат, 2003. –
64 с.
472

473.

ГУТОВА
Светлана Геннадьевна
ДИСКРЕТНОЙ МАТЕМАТИКЕ
Часть 1
курс лекций
473