Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 94

Комбинаторные алгоритмы. Теория и практика.— Мл Мир, 1980. 29. Свами М., Тгуласираман К. Графы, сети и алгоритмы.— Мл Мир, 1984. 30. Справочная книга по математической логике. ьЬ1-1Ч / Под ред. Дж. Барвайса.— Мл Наука, 1982, 1983. 31. Харири Ф. Теория графов.— Мл Мир, 1973. 32.

Юэвиитин И.И. Информациология.— М.: Радио и связь, 1996. ЗЗ. Арре1 К., Найеп Ит. Ечегу р1апаг шар тв Фоиг со1отаЫе//Вий. оГ Ащег. МаФЬ. Бос.— 1976.— Ч. 82, № 5. 34. Веще С. Ьаг Четдпаг М. Бит ип ФЬеотеше дц Фуре Кошб рош ЫретбгарЪев ~~Апп. Ч.Ч. Асат1. Бст.— 1975. 36, Хт 1. 35. ВтгЛЛоЯ' С., Ьеютг П. СЬгощаИс ро1упопца!в//Ттапв. Ашет.

МаФЬ. Бос.— 1946.— Хь 60.— Р. 355-451. 36. СЛпгФоДдеэ Н. ТгарЬ ФЬеоту. Ап а18огИЬппс арртоасЬ.— Неъг Уог1с— Ьопдоп — Бап Ртапс1всо. Асадепис Ргевв, 1975. [Ру с. перл Крисньотвидес Н. Теория графов. Алгоритмический подход.— Мл Мир, 1978.) 37. ПеэсагФег В.

Бо1иИоп Фо вт1тапсед ргоЫеш № 4526//Атлет. МаФЬ. МопФЫу.— 1954.— № 61.— Р. 352. 38. Ейгас С.А. Оп ФЬе вФптстше о1 К-сЬготпаИс бгарЬв//Ргос. СашЪпс18е РЫ1ов. Бос.— 1967.— № 63.— Р. 683-691. 39. Ютптс С.А. ТЬе вФтисФше оу К-сЬтотпаИс бгарЬв//Риис1. МаФЬ.— 1953.— № 40.— Р. 42-55. 40. СоЫЬегд П.Е. СепеИс А18опФЬтпв.— А<Ы1воп-%ев1еу, 1989. 41.

Нагйитдег Н. ОЪет еше К1ввв11еЬаФтоп дег БФтесЬеп Котпр1ехе// ЧФегте11всЪг. НаФигуогвсЬ. Сев. ЕйпсЪ.— 1943.— № 88.— Р. 133- 142. 42. Кейу л.В., Кейу Ь.М. РаФЪ апд снсшФв тп спИса1 бгарЬв,/Ашег. 3. МаФЬ.— 1954.— Х' Тб.— Р. 786-792. 43. МасЛа1евтсэ Л. СепеИс А18опФЬптв + ВаСа БФгисьигев = Ечо1иИоп Ртобгашв.— Брппбет-Чет1аб, 1992. 44. Мрете!гЛт' л'. Бит 1е со1опабе дев бгарЬв//Со11отФ. МаФЬ.— 1955.— № 3.— Р.

161-162. 45. Баасу Т.Ь. ТЫтФееп сото!уи1 тш1аФ1оп оп Си1Ьпе'в уоиг-со1ог сопуесФФге у'Атпег. МаФЬ. МопФЫи.— 1972.— № 72.— Р. 2-43. 46. ФУЛттпеу Н. СопбтиепФ ргарЪв аид ФЬе соппесФФхФФу оЕбгарЬв//Атпет. Л. МаФЬ.— 1932.— № 54.— Р. 150-168. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Автомат асинхронный 266 — конечный 264 — магазинный 263 — Майхилла 262 — микропрограммный 282, 283 — операционный 267 — синхронный 266 — управляющий 267 Алгебра 18 — булеза 33 — Вебба 132 — множеств (алгебра Кантора) 21 — отношений — Поста 132 — реляционная 42 — Россера — 'Гьюкегта 132 — схемная 367 Алгоритм 55 Антисиндром 344 Базис булев 108 — дизъюнктивный 113 — конъюнктивный 113 — Вебба 113 — Жегалкина 113 — импликативный 113 — коимпликатнвный 113 — несвязный 347 — связный 347 — циклов 171 — Шеффера 113 Буква 216, 259 — крайняя второго рода 327 — — первого рода 327 — обобщенная второго рода 322 — — первого рода 321 Булеан 15 Вершина граничная 379 Вершина покрывающая 331 — разделяющая 312 Вершины соцветные 208 Вес производной ат булевой функции 119 Вид 359 Высказывание 94 Гамак 312 Гиперграф 38 Гиперкуб (и-мерный куб) 50 Грамматика бесмонтекстная 263 — контекстная 262 — контекстно свободная 263 — — связаная 262 — линейная 263 — металинейная 263 — односторонне линейная 263 — с конечным числом состояний 258 — языка 258 Грань нижняя 27 — — наибольшая 27 — верхняя 27 — — наименьшая 27 Граф взвешенный 158 —, вложимый в булеза пространство 198 — гомеоморфный 194, 229 — двудольный 39 — затирания 291 — зацепления 287 — звездный 208 — изоморфный 160 — квазиполный 21Т вЂ” — невмлючаемый 242 — кубируемый 198 — линейный 339 — незацепленный 286 Предметный ркаэотель 537 Граф переходов 272 — пленарный 194 — полный 37 —, приводимый к цунгу 283 — предквазиполный 440 — противоречивости столбцевой 456 — — строчный 456 — п-раскрашиваемый 208 — и-хроматический 208 — связный 163 — — сильно 168 — — несильно 168 — типа ка — частичный 24 Группа 19 — подстановом (группа Галуа) 19 Группоид адднтивный 18 — ассоциативный 19 — идемпотентный 19 — коммутативный (абелев) 19 — мультипликативный 18 Декомпозиция автоматов абстрактная 282 — — параллельная 282 — структурная 342 — функции булевой 100 — — А-анечкой 467 Дерево 171 — дастижимости 379 Диаграмма гомеоморфная 36 — Хассе 26 — Эйлера 15 Дифференцирование булевой функции 117 — графа 1Т6 Задача достижимости 379 Запуск переходов 374, 375 Изоморфизм алгебр 33 — упорядоченных множеств 27 Имплнканта простая 52 — — многовыходная 419 — я-связный 166 Интервал булевой функции максимальный 103 — — многовыходной 419 — — — максимальный 419 — множества 51 Исчисление высказываний 127 — предиматов 142 — — расширенное 144 — — узкое 144 Канал информационный 267 — управляющий 267 Квазиплотность квазилолного графа 217 — модели 217 — — квазиполной 217 Квантор всеобщности 142 — существования 142 Класс булевых функций линейных 109 — — — монотонных 110 — — — самодвойственных 110 — — —, сохраняющих константу 0(1) 109 — хроматический 209 — эквивалентности Коалгебра графов 343 Код дополнительный 64 — обратный 64 — прямой 61 Кодирование Аймена — Эмери 72 — "в остатках" 73 — внутренних состояний 292 — — соседнее 297 — — частотно-матричное 293 — Штибитца ТО Кольцо 21 Комплект 373 — пустой 373 Кооперация 343 Констнтуента 47 Контур 168 Конфигурация комбинаторная 14 Мажорантв подмножества 26 538 Предметвыа указатель Матрица базисная разрезов (коци- ' кломатическая) 173 — — — цикломатическая 170 — инпиденций 158 — — вторая 172 — — первая 172 — 5-клеточная 165 — смежности 159 — — модифицированная 190 — — базисная 325 — частотная отношений 176 — — и-мерная 180 Машина Тьюринга 260 Микролуч 283 Микрооперация 273 Микропрограмма 273 Миноранта подмножества 26 Мограф 58 Модель 39 — гомеоморфиая 229 — изоморфная 229 — квазиполиая 217 Окрестность единичного радиуса элемента (сечение) 23 — вершины 184 Операция дизъюнкции 94 — дополнения 17 — инверсии 343 — конъюнкции 94 — обратная 343 — объединения 17, 40, 373 — — пересечения 17, 40 — произведения декартова расширенного 40 — разложения 343 — разности 17, 40 — — симметрической 46 — расщепления второго типа 332 — — первого типа 331 Остов 171 Отношение п-арное 36 — — симметричное (Я-отноше.

ние) 37 Отношение бинарное 22 — — упорядоченности 25 — — — строгой 25 — достижимости 375 — — непосредственной 375 — обратное 28 — предпорядка 25 — рефлексивное 23 — симметричное 24 — трапзитивное 24 — эквивалентности 28 Паросочетание 184 — наибольшее 184 — совершенное 184 Перестановка 14 — модели 217 Подмножество 13 — нечеткое 75 — собственное 14 Лодмодель 216 Подстановка 19 Покрытие 53 Лоле 21 Полугруппа 19 Лолусистема Туэ 258 Порядок модели 217 Пасет 75 Лредикат 142 Проблема алгоритмически неразрешимая 262 — хаРактеризационная 395 Проекция бинарного отношения 42 Произведение декартово 15 — — частичное 282 — подстановок 20 Производная временная 495 — графа 176 — — первого порядка 117 — Й-го порядка 118, 178 — — смешанная 117, 178 — модели 333 Пространство булево 198 — метрическое 83 У?редметныб указатель Путь простой 168 — сложный 168 — составной 168 Разбиение 29 Размещение 14 Разложение столбцевое 100 — строчиое 100 — Шеннона 98 — — в точке 00...0 124 — — в заданной точке 127 — — двойственное 99 — — предельное 98 Разрез 167 Раскраска вершин 208 — ребер 209 Расстояние Евклидова (квадратное) 84 — — относительное 84 — Хемминга (линейное) 83, 84 — — относительное 84 Реберность 210 Решетка 29 — векторная 80 — дедекипдова (модулярная) 32 — дистрибутивная 32 — полная 32 — с дополнениями 33 Риск 496 Род графа 194 — поверхности 194 Связность реберная 166 Семантика дескриптивная 393 — проективная 393 — рефлексивная 393 Сеть Петри 374 — — маркированная 374 — — — безопасная 377 Сечение 328 Символ 258 — иетерминальиый 260 — терминальный 260 Система алгебраическая 40 Система счисления 56 — — аддитивная 58 539 — — асимметрическая 58 — — весомозначная 58 — — естественная 58 — — мультипликативная 58 — — непозиционная 58 — — позиционная 58 — — с основанием Я 58 — — симметрическая 58 Состояния незацеплепные 284 — неустойчивые 297 — псевдоэквивалептные 289 — совместимые 283 — эквивалентные 279 Суперпозиция 108 Таблица истинности 95 — Квайна (импликантная) 53 Тело 21 Терм первичный 96 Тип 359 Трасса 146 Уровень типа А 331 — — В 331 — — С 332 — — 1У 334 Фактормножество 23 Фигура запрещенная 198 Форма Кантора 51 — — нормальная (НФК) 51 — — — минимальная 52 — — — совершенная 51 — — — сокращенная 52 — — — тупиковая 52 — — скобочпая 54 Форма (булевой функции) нормальная дизъюнктивная (ДНФ) 96 — — — совершенная 96 — — — сокращенная 103 — — — тупиковая 107 — — — — минимальная 107 — — — — — решетчатая 317 Функция 16 Предметиыв указатель 540 18Н)ь) 5-02-015238-2 795020 152389 > Хорда 171 Учебное издание Функция булева — — остаточная 100 — — слабоопределенная 105 — )г-значной логики 132 — полностью определенная 16 — часткчно определенная (недо- определенная) 16 Цепь 26 — простая 163 — — составная 163 — — сложная 163 Цикл гамильтонов 163 — эйлеров 166 Цунг 283 Число графа внешней устойчивости 183 — — — — вершинное 183 — — — — — отрицательное 191 Число графа внешней устойчивости вершинное положительное 191 — — — — реберное 183 — цикломатнческое 171 — — мографа 325 Элемент дополнительный 31 — единичный 27 — максимальный 27 — минимальный 27 — наибольший 27 — наименьший 27 — нейтральный 19 — — двусторонний 19 — — левый 19 — — правый 19 — сравнимый 27 Язык конечноавтоматный 264 — с конечным числом состояний 259 — эквивалентный 258 Горбатов Вячеслав А()занасъевич ФУНДАМЕНТАЛЬНЫЕ ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ.

ИНФОРМАЦИОННАЯ МАТЕМАТИКА Редактор Е.Ю, Ходом Компьютерный набор н верстка А.П. Носова, А.С. Фурсово Компьютерная графика М.В. Неаиоесиоао Подписано в печать с готовых диапоаитивов 15.12.99. Формат ВОХ90~/1«Бумага офсетная. Печать об)сотная. Уел. печ. л. 34,0. Уч.-изд. л, 40,8. Тираж 2000 зкз. Заказ 4130. С-002.

Издательская фирма «Физико-математическая литература» РАН ЛР )4) 020297 от 23.06.1997. 117071, Москва В-71, Ленинские проспект, 15. При участии ООО «Харе«от». Лицензия ЛВ )Чз 32 от 27.08.97. 220013, Минск, ул. Я. Коласа, 35-305. Ордена Трудового Красного Знамени полиграфкомбинат ППП им. Я. Коласа. 220005, Минск, ул. Красная, 23, .