Cтраница 1
Проблема перечисления и классификации комбинаторных типов многогранников, заданных в аналитической форме, поставлена впервые. Применение традиционного аппарата в виде помеченных граничных комплексов многогранников в такой форме задания приводит к ряду затруднений. Чтобы их преодолеть, в монографии введен новый прием перечисления и классификации многогранников с помощью полуматроидов многогранников, несущих информацию об инцидентных отношениях между вершинами и гранями максимальной размерности. Благодаря этому приему получены критерии комбинаторной эквивалентности помеченных многогранников ( § 1 гл. [1]
Многие проблемы перечисления формулируются так, что ответ можно дать, найдя формулу для числа орбит ( систем транзитивности), определяемых группой подстановок. Часто орбитам приписываются веса; Пойа [1] показал, как получить формулу, перечисляющую орбиты в соответствии с весами и зависящую от циклической структуры подстановок данной группы. Обращение теоремы Пойа связано с обобщением хорошо известной перечислительной формулы, принадлежащей Бернсайду [ 1, стр. [2]
Поскольку проблемы перечислений встречаются в теории вероятностей в самых неожиданных случаях, то нужно более широко применять методы теории вероятностей для получения асимптотических результатов. Эрдеш н Спенсер [16] обсуждают некоторые применения теории вероятностей. Комбинаторные проблемы, которые они рассматривают, гораздо менее удобны для обсуждаемых здесь методов: пытаться найти для них производящую функцию или сумму было бы безнадежно. [3]
Теперь мы рассмотрим проблему перечисления всех функций, принадлежащих классу сложности. [4]
Центральной в комбинаторной теории многогранников является проблема перечисления и классификации многогранников с заданной структурой его граней. [5]
Так как коды множества 3) ( /) являются в точности экстремальными унтер-решениями системы 5 ( L) уравнений в словах, из теоремы 2.4.5.1 об алгоритмической неразрешимости проблемы перечисления всех экстремальных унтер-решений уравнений в словах сразу получаем аналогичный факт, относящийся к оптимальному кодированию. [6]
Понятие неприводимого множества можно ввести также для борелевских множеств высших классов ( множество класса ot называется неприводимым, если ни в какой окрестности своей произвольной точки оно не принадлежит к низшему классу); понятие абсолютного множества данного класса вводится аналогично тому, как оно было введено в § § б и 9 для специального случая G § - и / - множеств. Возникает проблема перечисления ( или по меньшей мере проблема определения мощности) всех топологических типов неприводимых нульмерных множеств заданного класса. Аналогичная проблема возникает и для так называемых Л - множеств. [7]
Текст книги делится на три большие части. Первые четыре главы связаны с проблемами перечисления. Главы 5 - 9 посвящены промежуточной области - теоремам о выборе. В главах 10 - 16 речь идет о существовании и построении схем. [8]
Настоящая книга является наиболее полным изданием в области комбинаторного анализа. Она состоит из трех основных частей: проблемы перечисления, теоремы выбора н связанные с ними-вопросы-и проблемы существования н построения блок-схем. Книга написана ма высоком научном уровне и освещает самые новейшие достижения в области комбинаторики. [9]
В подходе, ставшем классическим, исходят из алкильных радикалов, затем используют полученные при их перечислении величины для подсчета алканов. Для того чтобы понять некоторые последствия, связанные с пренебрежением исключенным объемом, рассмотрим эту проблему перечисления алкильных радикалов глубже. [10]
Мы начнем с самых простых задач перечисления, а именно с перечисления помеченных графов. Затем приведем классическую теорему перечисления, принадлежащую Пойа, и применим ее к нахождению перечисляющих рядов для деревьев и других видов графов. Будет дано также обобщение теоремы Пойа ( так называемая теорема перечисления степенной группы), полезное при исследовании проблем перечисления, в которых эквивалентные классы задаются с помощью двух групп подстановок. [11]
О двух комбинаторно экивалентных многогранниках говорят также, что они являются многогранниками одного типа. Проблема выявления всех комбинаторных типов d - многогранников с фиксированным числом вершин или граней является важнейшей в комбинаторной теории многогранников. Для а 2 проблема тривиальна: два многоугольника комбинаторно эквивалентны тогда и только тогда, когда они имеют одинаковое число вершин. Однако уже в случае d 3 проблема перечисления комбинаторных типов многогранников, несмотря на ее большое практическое значение в кристаллографии, полностью не решена. [12]
Теперь легко определить число свободных деревьев с помеченными вершинами ( см. упр. Число упорядоченных деревьев с помеченными вершинами также нетрудно определить, поскольку мы знаем ответ на эту задачу для случая, когда никакой маркировки нет ( см. упр. Итак, в настоящем подпункте по существу решены все проблемы перечисления трех основных классов деревьев, как с помеченными, так и с непомеченными вершинами. [13]