Дискретная математика

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 (или аналогичный процессор других
производителей), 12 ГГц; 512 Мб оперативной памяти; видеокарта SVGA,
1280x1024 High Color (32 bit); 2 Мб свободного дискового пространства; операц.
система Windows ХР/7/8; Power Point. – Загл. с экрана.
ISBN 978-5-8353-1686-1
2

3.

Конспект лекций разработан по дисциплине «Дискретная математика»
для направления подготовки 01.03.02 Прикладная математика и информатика
в соответствии с требованиями ФГОС ВО и включает теоретический
материал, примеры, снабженные анимацией. Может быть использован для
обеспечения лекционных занятий по дисциплине «Дискретная математика»
студентами направлений 02.03.02 Фундаментальная информатика
и
информационные технологии и 02.03.03 Математическое обеспечение и
администрирование информационных систем и по дисциплине «Дискретная
математика и математическая логика» студентами направления 02.03.01
Математика и компьютерные науки.
Утверждено на заседании
кафедры прикладной математики
Рекомендовано научно-методическим
советом института фундаментальных наук
Протокол № 7 от «26 » февраля
2018 г.
Заведующий кафедрой,
__________________ Е. С. Каган
Рекомендовано
Протокол № 7 от «19» марта 2018 г.
Председатель совета доцент
_____________С. М. Сирик
3

4.

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

5.

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

6.

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

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

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

8. Лекция 1

Множества

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

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

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

16.

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

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

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

18.

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

19. Пример 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!,...
19

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

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

21.

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

22.

Множества А и В называют равными
(А = В), если каждый элемент множества А
является одновременно элементом
множества В и наоборот,
то есть если A B и B A .
Другими словами, два множества равны,
если они состоят из одних и тех же
элементов.
22

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29. Пример 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
элемента:
29

30.

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

31.

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

32.

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

33.

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

34. Пример 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)}
34

35.

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

36. Пример 5

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

37.

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

38.

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

39.

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

40.

2) На 2 копии диаграммы надо
заштриховать множества, вступающие
во второе действие: это результат
первого действия и С. У каждого из
этих множеств на рисунке одинарная
штриховка своего вида (цвета).
40

41.

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

42.

3) На 3 копии диаграммы надо
заштриховать множество, которое
будет являться ответом.
Штриховка – одинарная.
Заметим, что на каждой копии
диаграммы, кроме последней, должно
быть ровно два вида штриховки, а на
последней копии – один вид.
42

43.

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

44. Лекция 2

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

45.

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

46.

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

47.

Прямое произведение 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 .
47

48. Пример 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 .
48

49.

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

50.

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

51. Пример 2:

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

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

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

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

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

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

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

55.

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

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

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

57.

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

58. Пример 3:

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

59. Пример 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 , а именно, второй;
59

60. Пример 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 , а именно первой и
60
третьей;

61. Пример 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 ;
61

62. Пример 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.
62

63. Лекция 3

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

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

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

65.

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

66.

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

67.

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

68.

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

69.

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

70.

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

71.

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

72.

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

73.

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

74.

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

75.

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

76.

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

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

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

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

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

79.

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

80. Пример 2:

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

81. Пример 3:

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

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

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

83. Пример 4:

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

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

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

85. Пример 5:

Сколько слов длины 6 можно составить из
26 букв латинского алфавита?
6
6
В26 26
85

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

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

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

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

88. Пример 6:

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

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

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

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

1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Рис. 5. Схема расстановки
х1 4;
х2 2!; х3 3!;
A 4 2! 3!
90

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

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

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

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

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

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

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

94

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

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

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

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

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

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

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

3
0
А3 С3 С4 1 1 1.
98

99. Лекция 4

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

100.

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

101.

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

102.

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

103.

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

104.

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

105.

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

106.

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

107.

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

108. Пример 1:

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

109.

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

110.

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

111.

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

112. Выводы:

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

113. Пример 2:

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

114.

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

115.

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

116.

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

117. Выводы:

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

118.

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

119.

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

120.

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

121.

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

122.

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

123.

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

124.

Для многоместных функций
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 ).
124

125.

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

126.

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

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

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

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

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

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

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

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

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

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

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

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

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

133.

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

134.

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

135.

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

136.

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

137.

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

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

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

139. Лекция 5

Отношения

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

n
Подмножество R M называется
n – местным отношением
на множестве М [2, 3].
Говорят, что a1 , a 2 , , a n находится
в отношении R, если a1 , a2 , , an R .
140

141.

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

142.

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

143.

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

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

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

145. Список

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

146.

Матрица бинарного отношения,
заданного на множестве M {a1 , a2 , , an }
– это квадратная матрица С порядка n,
элементами:
1, если ai Ra j ;
cij
0, в противном случае.
Здесь i – номер строки, j - номер столбца.
146

147. Пример 2:

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

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

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

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

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

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

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

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

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

152. Пример 6:

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

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

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

154. Пример 7:

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

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

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

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

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

157. Пример 9:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

174. Лекция 6

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

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

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

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

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

177.

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

178.

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

179.

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

180. Пример 1:

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

181. Примеры 2:

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

182. Пример 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).
182

183.

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

184. Пример 3:

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

185. Пример 3:

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

186. Пример 3:

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

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

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

188. Пример 4:

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

189. Пример 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 .
189

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

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

191. Пример 5:

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

192. Пример 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
192

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

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

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

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

195. Пример 6:

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

196. Пример 6:

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

197. Пример 6:

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

198. Пример 6:

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

199. Лекция 7

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

200.

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

201.

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

202.

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

203.

Изоморфизмом алгебры А на алгебру В
называется взаимно однозначный гомоморфизм.
В этом случае существует обратное отображение
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 1 m1 , 1 m2 , ..., 1 ml (i ) 1 i m1, m2 , ..., ml (i ) .
203

204.

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

205.

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

206.

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

207.

Пример 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 ;+) в себя.
207

208.

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

209.

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

210.

Пример 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.
210

211.

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

212.

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

213.

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

214.

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

215. Лекция 8

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

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

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

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

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

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

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

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

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

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

Вершина, у которой нет инцидентных
ребер, называется изолированной.
220

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

234. Пример 1:

a
b c d
1 1
0 0 0
2 1 0 1 0
3 1 0 1 0
4 1
1 0 0
5 0
1 1 0
Рис.13. Матрица инцидентности н-графа
234

235. Пример 2:

a b c d
1 α 0 0 0
2 1 0 -1 0
3 1 0 -1 0
4 -1 1 0 0
5 0 -1 1 0
6 0 1 -1 0
Рис. 14. Матрица инцидентности ор-графа
235

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

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

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

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

238. Пример 3:

a b
a 1
b
c d
1 2 0
1 0 1 0
c 2
1 0 0
d 0
0 0
Рис. 15. Матрица смежности н-графа
0
238

239. Пример 4:

a b c d
a
1
1 0 0
b 0 0 1 0
c
2
1 0 0
d 0 0 0 0
Рис. 16. Матрица смежности ор-графа
239

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

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

241. Рисунок

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

242. Пример 5:

E = {(a,a), (a,b), (a,c), (b,c)}.
Рис. 17. Список ребер н-графа
242

243. Пример 6:

E={(a,a), (a,b), (a,c), (с,a), (b,c)}.
Рис. 18. Список ребер ор-графа
243

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

257. Лекция 9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

273.

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

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

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

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

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

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

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

277. Лекция 10

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

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

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

279. Суграф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

298. Лекция 11

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

299. Маршруты

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

300. Маршруты

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

301. Маршруты

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

302. Маршруты

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

303. Маршруты

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

304. Пример 1

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

305. Маршруты

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

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

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

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

Пример 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
307

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Диаметральные
и радиальные цепи
316

317. Лекция 12

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

318. Связность

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

319. Связность

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

320. Связность

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

321. Связность

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

322. Связность

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

323. Связность

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

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

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

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

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

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

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

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

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

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

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

329. Шарнир

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

330. Шарнир

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

331. Лекция 13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

346. Алгоритм

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

347. Алгоритм

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

348. Пример 1

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

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

1. 2,1 : s 1 s 2 L 2,1
s 1 s 2 L 2,1 0 1 1;
1
2
3
4
5
6
7
0
1 0
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;
1
2
3
4
5
6
7
0
1 0
1 0 3
351

352. Пример 1

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

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

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;
1
2
3
4
5
6
7
0
1 0
1 0 3
1 0 3
353

354. Пример 1

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

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

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
2
3
4
5
6
7
0
1 0
1 0 3
1 0 3
1 0 3 3
s 5 s 1 L 1,5 1 2 3;
355

356. Пример 1

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

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

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
2
3
4
5
6
7
1 0 3 4
3
0
1 0
1 0 3
1 0 3
1 0 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;
357

358. Пример 1

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

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

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
s 5 s 1 L 1,5 1 2 3;
1
2
3
4
5
6
7
0
1 0
1 0 3
1 0 3
1 0 3 3
1 0 3 4
1 0 3 4
3
3
5. 1,4 : s 4 s 1 L 1,4
s 4 s 1 L 1,4 1 3 4;
6. 4,5 : s 5 s 4 1 L 4,5
s 5 3;
359

360. Пример 1

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

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

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

362. Пример 1

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

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

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

364. Пример 1

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

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

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

366. Пример 1

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

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

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

368. Пример 1

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

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

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

370. Пример 1

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

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

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

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

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

373. Лекция 14

Деревья

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

386

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

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

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

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

389. Ветвь

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

390. Лекция 15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

406. Пример 7:

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

407.

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

408. Пример 8:

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

409.

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

410.

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

411.

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

412.

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

413. Лекция 16

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

414. Введение

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

415. Введение

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

416. Введение

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

417. Введение

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

418. Введение

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

419. Введение

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

420. Сети

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

421. Сети

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

422. Сети

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

423. Сети

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

424. Сети

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

425. Сети

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

426. Сети

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

427. Сети

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

428. Сети

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

429. Пример 1

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

430.

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 .
430

431.

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 пусто .
431

432.

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 .
432

433.

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 пусто
433

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

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

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

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

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

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

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

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

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

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

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

Замечание 2:
R s R t .
439

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

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

441. Пример 2

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

442.

с(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.
442

443.

443

444.

444

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

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

446.

с(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.
446

447.

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

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

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

449. Лекция 17

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

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

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

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

Пример 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; и так далее.
451

452.

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

453.

Кодирование (отображение) Е – двоичная запись
натуральных чисел с помощью минимального количества
букв.
Числу 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 ) .
453

454.

Пример 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 .
454

455.

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

456.

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

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

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

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

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

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

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

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

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

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

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

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

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

463.

Оптимальное кодирование
Пусть источник случайным образом генерирует
буквы алфавита А а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 463
.
i 1

464.

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

465.

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

466.

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

467. Пример 6:

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

468. Код Фано

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

469.

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

470. Код Фано

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

471.

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.
471

472. Код Фано

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

473.

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
473

474. Код Фано

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

475.

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
475

476.

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
476

477.

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
477

478.

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
478

479.

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
479

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

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

481.

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

482.

Код Хаффмена
Теорема Хаффмена
Если 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 .
482

483.

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

484.

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

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

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

486.

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

487.

Функция Хемминга 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 .
487

488.

Пример 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) .
488

489.

489

490.

Пример 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 .
Полученный результат является двоичным кодом
номера того места, на котором произошло
замещение.
490

491.

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

492.

Учебное издание
ГУТОВА
Светлана Геннадьевна
ДИСКРЕТНАЯ МАТЕМАТИКА
Часть 1
конспект лекций
492