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