Введение в прикладную комбинаторику, Кофман А.

А. КОФМАН Введение в прикладную комбинаторику Перевод с французского В. П. МЯКН!йЕВА и В. Е. ТАРАКАНОВА Под редакцией Б. А. СЕВАСТЬЯНОВА ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКИИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТ Москва 1975 ОГЛАВЛ ЕН И Е Предисловие редактора перевода Список основных обозначений Гл а за 1. Пересчет. Применение производящих функций $9 $ !О Глава П. Развитие методов пересчета 60 60 70 73 78 87 97 ячейкам 114 . 125 , 127 по ячей- .

133 . 145 . 151 $22 9 23 $1 $2 $3 $4 $5 6 $7 $8 $1! $12 $13 $ !4 й 15 $16 $ !7 9 18 9 19 % 20 $21 Введение Теоретико-множественное произведение. Понятие г-выборки Размещения. Сочетания Пересчет. Перечисление. Классификация. Оптимизация Производящие функции Сведения о коиечноразностных операторах з-преобразование Применение производящей функции, Энумераторы и денумера- торы сочетаний Денумераторы размещений Основные последовательности и формулы для пересчета Введение Формула включения и исключения Использование общего метода решета в теории чисел Задача о встречах Беспорядки и совпадения Перманент матрицы Группы подстановок. Перестановки. Транспозицин Денумерагоры цинловых классов Классифицирование. Схема размещения элементов по Урновые схемы Задача о супружеских парах, или задача Люка Перестановки с запретными положениями.

Размещение кам Противоречивые перестановки Латинские прямоугольники 9 9 10 16 18 20 24 37 44 47 !64 Г л а в а П1. Свойства графов Введение ....,...,....,...,... 154 Граф, Определение.......,...,,,... 155 Понятие пути .....,....,,...,... 161 Сильно связный граф. Разложение на ыаксимальные сильно связные подграфы. Транзитивное замыкание н пересчет путей 164 Порядковая функция графа без контуров...,....

172 Функция Гранди,.....,,...,...,,, 177 Внутренняя устойчивость. Внешняя устойчивость . . . , . . 180 Ядра графа ...,...,....,...,,, !86 Основные понятия для неориентированных графов,.... 191 Хроматическое число. Хроматический класс....,... 195 Клика. Максимальная клика . . . . , . . . , . . . . . 201 р-цветный граф Граф с р отображениями Неориентированный мулыиграф, или неориентированный р-граф , . . . . . . , 204 Плоские р-графы,,...,,...,,..., ., 205 Подмножество сочленения ...,,...,...,, 2!О Прадерево.

Дерево,...,...,,...,, 217 Конечные структуры.............., .. 223 6 24. 4 25 $26 $2? $28 $29. $30 5 31. 5 32 ф 33 $34 6 35 6 36 $ 37 6 38 й 39 . 243 Г л а в а Гч'. Перечисление , 243 , 243 . 246 , 248 . 252 . 255 , 257 . 263 Введение Метол латинской композиции Перечисление путей Перечисление элементарных путей Перечисление элементарных контуров Перечисление последовательностей с повторением Перечисление факторов графа Перечисление рассечений Другие методы и задачи перечисления 6 40. $41 5 42 6 43 й 44 $45 $ 46 $47 $48 .

271 Г л а в а Ч. Оптимизация . 277 . 279 ности Метод динамического программирования Последовательные графы $52 6 53 б 54 , 291 Метод прогрессивных разделений и оценок (метод ветвления и ограничения) . . . . . . . . . . . . . . . , . . . . 299 Нахождение хорошего решения эвристическим методом... 324 Применение методов Монте. Карло . . .

. . . . . . . . 338 6 55 6 56 $49. Введение . 271 6 50. Числовая функция на графе.............. 271 6 51. Оптимизация пути в графе без контуров. Теоремы оптнмаль- ,,.....,.341 оптимального дерева, , 350 . 355 , 361 , 381 . 405 П р и л о ж е н и е А. Бинарная булеза алгебра. Кольцо классов вычетов по модулю и. Поля Галуа характеристики р...

415 , 415 . 415 . 42? . 432 . 435 Приложен не Б, Кодирование. Коды, обнаруживающие ошибки Б1. Введение Б2. Передача г-выборки БЗ. Коды, обнаруживающие и исправляющие ошибки Б4. Аналогия между циклическими и линейными кодами Б5. Коды сцепления Бб. Декодирование переетановкамн Литература Именной указатель Предметный указатель 6 67. Понятие й-оптимальности й 58. Оптимизация на прадереве. Отыскание являющегося частичным графом й 59. Задачи о временнбм упорядочении З 60. Оптимизация потока в сети й 61. Простой граф. Покрытие.

Паросочетание 6 62. Задача о назначении А1. Введение А2. Булеза алгебра А3. Кольцо классов вычетов по модулю и А4. Поля Галуа А5. Алгебра по модулю 2 . 439 439 . 439 . 445 . 460 . 465 . 468 . 472 . 475 , 477 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Развитие вычислительной техники и исследования операций вызвало повышенный интерес к комбинаторной математике. Оно привело, с одной стороны, к постановке новых комбинаторных задач, а с другой стороны, дало эффективные способы их решения с помощью электронных цифровых вычислительных машин. В предлагаемой книге известного французского математика и педагога А.

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

При написании книги автор стремился к тому, чтобы читатель, не обладающий предварительной подготовкой, получил дополнительный стимул к изучению этой области математики. Этому способствует большое количество примеров и иллюстративного материала. Простота и наглядность изложения делают ее доступной самому широкому кругу читателей. В процессе перевода и редактирования было выявлено н исправлено значительное количество ошибок и неточностей оригинала, особенно большим изменениям подверглись главы 1Ъ' и Ъ', Севастьянов Б. А.

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ (а, Ь, ..., 1), Е )( а !ы А 8 А=В (А(, Сагб(А) В с А В ий А В !ь А АОВ АП В С В,В А — В У, =)! Уз У! ФФУз )!!х Ех Е1х Х Е )со С ЕО!ХЕ1з!Х ° ° ° ХЕ! ! (Еи Еи '' Еа) [Ер, Е,, ..., Ер [ А,"„ С" Си! из ""ив 1и А )' (я) (2) Ег (х) Ьг (х) 01 (х) й) (х) з(и, г) Множество. Множество частей множества Е. Элемент а принадлежит множеству А. Пустое множество.

Множество А совпадает с множеством В. Число элементов конечного множества А. Множество В содержится в множестве А. Множество В строго содержится в множестве А. Множество В не содержится в множестве А. Объединение двух множеств. Пересечение двух множеств. Дополнение В по отношению к А. Разность. Из свойства У, следует свойство У,. Свойства У! и У, эквивалентны. Для всех х. Квантор общности. Существует х. Квантор существования. Существует одно и только одно х. Множество целых неотрицательных чисел; Х= (О, 1, 2, 3, ...!.

Х вЂ” (О). Множество всех целых чисел: Е (...,— 3,— 2,-1,0,1,2,3,...). Множество всех действительных чисел.  — (0). Множество всех комплексных чисел. Произведение и множеств Е1'1, Е1з), ..., Е1"1. Упорядоченнан г-выборка. Неупорядоченная г-выборка. Число размещений без повторения из га элементов по и. Число сочетаний без повторения из ги элементов по и. Число разбиений множества на й неупорядоченных выборок без повторения. Натуральный логарифм числа А Производящая функция, или я-преобразование функции 1(и), определенной на Х.

Экспоненциальная производящая функция, или экспоненциальное х-преобразование функции Г(з), определенной на Х. Оператор, переводящий 1(х) в 1(я+ й). Оператор, переводящий 1(х) в 1(х+ й) — 1(х). б Оператор взятия производной — 1(х) от 1(х). бх Оператор умножения ) (х) нз действительное число й. Числа Стирлинга первого рода. з(и, г) (А) Ол Вл ь бе( (( а ((, ( а ( рег ~(а)) Рл (зм гз' '' ' зл) Ь (и, Ь) Т (и, Ь) Мл Е(г, и] К(г, и) ГА Г А ОсЕХЕ ц+ А 6 = (Е, Г) или О = (Е, ц) О" (Хги Хэм „., Х,л) Г а «„Ь а(~ Ь а (6) НО) ц О =(Е Ц) (х,, х, , х, ) и (х",) у(6) тир(А) )п( (А) А ту В А зз В з)»зз л(х,, х,,, ..., х,л) р(х;„х,,, ..., х,"„) орт шах пНп с(ц ) 6=(Х,У, Г) Р(А; к), )л(х) и†= Ь (глоба) + СО (р) Числа Стирлиига второго рода.

Символ Кронекера. Целая часть числа А. Число беспорядков и элементов. Число перестановок и элементов с Ь совпадениями. Определитель матрицы ()а(). Перманент матрицы ))а!!. Денумератор цикловых классов. Присоединенные числа Стирлинга первого рода. Присоединенные числа Стирлинга второго рода. Число перестановок л «супружеских пар».