Список литературы

1. Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.

2. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1979.

3. Глускин Л.М., Шварц В.Я., Л.А. Шор. Задачи и алгоритмы комбинаторики и теории графов. — Донецк: Выща школа, 1982.

4. Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

5. Оре О. Теория графов. — М.: Наука, 1980.

Список дополнительной литературы

1. К главе 1

6. Александров П.С. Введение в теорию множеств и общую топологию. — М.: Наука, 1987

7. Кановей В.Г. Аксиома выбора и аксиома детерминированности. — М.: Наука, 1984.

8. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. — М.: Наука, 1976.

9. Френкель А.А., Бар — Хиллел И. Основания теории множеств. — М.: Наука, 1966.

10. Хаусдорф Ф. Теория множеств. M.-Л.: — ОНТИ, 1937.

1. К главе 2

11. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. — М.: Наука, 1974.

12. Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука,1979.

13. Клини С. Математическая логика. — М.: Наука, 1973.

14. Новиков П.С. Элементы математической логики. — М.: Наука, 1979.

15. Шенфилд Д.Р. Математическая логика. — М.: Мир, 1975.

1. К главе 3

16. Виленкин Н.Я. Комбинаторика. — М.: Наука, 1987.

17. Постников М.М. Магические квадраты. — М.: Наука, 1964.

18. Райзер Дж. Комбинаторная математика. — М.: Мир, 1966.

19. Риордан Дж. Введение в комбинаторный анализ. — Мир: 1963.

20. Сачков В.Н. Комбинаторные методы дискретной математики. — М.: Наука,1977.

21. Холл М. Комбинаторика, — М.: Мир, 1966.

1. К главе 4

22. Берж К. Теория графов. — М.: Наука,1973.

23. Зыков А.А. Теория конечных графов. — Новосибирск: Наука, 1969.

24. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

25. Харри Ф. Теория графов. — М.: Наука, 1973.

Предметный указатель

K

kраскрашиваемый граф 155

N

NPполные задачи 149

R

rподмножества nX множества 100

а

абсциссами 23

А

Аксиома

объемности 9

Аксиома бесконечности (Z6) 39

Аксиома выбора (Z7) 53

Аксиома выделения (Z5) 37

Аксиома пары (Z2) 14

Аксиома степени (Z4) 38

Аксиома суммы (Z3 15

а

алгебры множеств 22

алгоритм с возвратами — «backtracing» 149

аргумент и значение функции 35

б

бесконечный граф 126

биеция 35

бинарное отношение 127

бинарные функции 37

булевы функции 61

в

вершины графа 124

вполне упорядоченное множество 50

временную сложность алгоритма 148

выбор 93

выводимаяформула 77

г

гамильтонов контур 146

гамильтонов цикл 146

граф 124

группа 98

д

двойственнная функция 70

декартовым квадратом 23

декартовым произведением множест 23

дерево 152

диагональной процедуре Кантора 45

диаграммы Феррерса 118

дизъюнкция 66

дополнение 19

дополнение графа 127

достаточные условия равенства множеств 11

достижимая вершина 142

дуги графа 125

е

единица кольца множеств 22

з

задача выбора 83

задача выбора с возвращением 89

задача расположения. 83

задача укладки графов 131

З

Замыкание множества булевых функций 73

з

запись 140

и

изолированные вершины графа 126

изоморфизм графов 130

импликация 67

инверсия 96

инцидентное ребро 126

инъекция 35

К

Кардинальным числом 41

к

кванторы 77

классами эквивалентности 28

комбинаторной конфигурации 83

конечное множество 38

конечный граф 126

континуум 45

контур на графе 143

концевая вешина, концевое ребро 152

конъюнкция 65

кратные ребра 126

Л

Левой областью Dl отношения 25

Левой областью Dl отношения R 25

л

лес 152

линейно упорядоченное множество 49

локальная степень вершины неориентированного графа 133

локальная степень вершины ориентированного графа 134

М

Маршрут на графе 142

Матрица инциденций 136

м

матрицей смежности 135

мера на графе 154

методы теории доказательств 76

минимальный и минимальный элементы множества 49

М

Множество 7

Мощностью конечного множества 40

н

необходимое условие равенства множеств 29

неориентированное ребро 125

неориентированные ребра 125

нуль кольца множеств 22

нульграф 126

Н

Нульмаршрут 142

о

областью определения и областью значений функции f. 34

образом множества 33

объединением 15

однородный граф степени r 134

операция математической логики 64

ординал 50

ординатам 23

ориентированные ребра 125

ориентированный граф, орграф 125

отношение эквивалентности 26

О

Отношения 24

о

отношения порядка на множествах 15

О

Отношениями 24

о

отображением 34

п

парадокс Рассела 8

пересечением 18

перестановки и сочетания с повторениями 107

перестановкой 94

плоский граф 126

П

Подграф 127

п

подстановка 94

покрытие графа цепями 146

полем отношения R 25

полнота системы булевых функций 73

полнота системы функций 73

полный граф 126

порядковые числа (трансфиниты) 51

правильная раскраска графа 159

правой областью Dr 25

предикат 74

принцип двойственности 71

произведением 18

производящая функция 104

прообразом множества 33

простой цикл 143

пространственная характеристика сложности алгоритма 138

путь на графе 143

р

разбиением множества 26

размещения с повторениями 106

размещениями без повторений 92

разности множеств 18

ребра графа 124

С

С.Д.Н.Ф 70

С.К.Н.Ф. 72

с

связный граф 143

симметрическое отношение 129

симметрической разностью множеств 19

система Цермело (Zсистема) 9

сложение по модулю два 66

смешанный граф 125

собственным подмножеством 19

совершенная конъюнктивная нормальная форма. 72

соотнесенный граф 143

сопряженное разбиение 118

сочетания 100

сочетания с повторениями 108

списки инцидентности 139

список 140

стрелка Пирса 66

счетно 43

сюръекцией 34

т

таблица начала списка инцидентности 140

тавтологией 77

точная верхняя и нижняя грани множества 50

транспозиция 96

треугольник Стирлинга. 111

у

указатель 140

универсальное множество 19

упорядоченного множества 15

упорядоченной парой 15

ф

фактормножеством 28

функцией 33

функция отрицания 64

х

хроматический класс 159

хроматическое число графа 155

ц

цепь 143

цикл 143

циклы 95

ч

частичная упорядоченность множества 48

частичный граф 127

Ч

Числа Белла 112

ч

числа Стирлинга первого рода 93

числами Стирлинга второго рода 111

ш

штрих Шеффера 67

э

эйлеров граф 144

эйлеров контур 146

Э

Эйлерова цепь 145

э

эквивалентность 66