Cтраница 2
Комбинаторная точка зрения также приводит к некоторым интересным классам с. Более того, некоторые графы характеризуются лишь своими комбинаторными свойствами. Мы уже упоминали результат Сейдела [66] относительно графов, для которых - 3 является наименьшим собственным значением. В действительности рассматриваемые параметры определяют указанные два класса графов и два исключительных примера. Для v 16, fe 6, К 2 существует негеометрический граф с теми же параметрами. [16]
Комбинаторная точка зрения также приводит к некоторым интересным классам с. Более того, некоторые графы характеризуются лишь своими комбинаторными свойствами. Мы уже упоминали результат Сейдела [66] относительно графов, для которых - 3 является наименьшим собственным значением. В действительности рассматриваемые параметры определяют указанные два класса графов и два исключительных примера. Для v 16, k 6, К 2 существует негеометрический граф с теми же параметрами. [17]
Рассмотрим пример применения этого метода. Первый шаг - разбить внешние спецификации на отдельные функции, комбинаторные свойства которых и должны тестироваться. В качестве примера займемся фрагментом спецификации, изображенным на рис. 12.1. Отметим, что эти спецификации слегка упрощены, чтобы пример был не слишком большим. [18]
Классическим примером комбинаторной оптимизационной задачи служит задача коммивояжера. Как показывает практика, наиболее эффективными в применении к ней являются алгоритмы, учитывающие ее комбинаторные свойства. Состоит она, как известно, в следующем. [19]
В настоящей работе излагаются результаты, относящиеся к классической теории узлов. В их основе лежит простая геометрическая идея, изложенная еще в конце XIX века, однако замечательные алгебраические и комбинаторные свойства этой конструкции оставались незамеченными в течение целого столетия. Развитие этой идеи привело к описанию узлов и зацеплений как центральных элементов некоторых конечно определенных полугрупп и к простому алгоритму распознавания тривиального узла. [20]
Полученные результаты позволяют проектировать оптимальные по стоимости единицы обслуженной нагрузки системы коммутации. В частности, из табл. 5.1 следует, что при с105 целесообразно использовать КП, близкие по вероятностно комбинаторным свойствам к неблокирующим схемам, где суммарные потери практически определяются потерями в пучках СЛ. Из сказанного следует, что общую оптимальную схему группо-образования получить невозможно. Оптимальность достигается только в конкретных случаях. [21]
Отметим, что максимальность сохраняется, если в фигуру с меньшим числом вершин ввести дополнительные вершины. Поэтому если в представлении фигуры, которая является расширением комбинаторно симметричной фигуры с меньшим числом элементов, обладающей определенным комбинаторным свойством ( например, максимальностью числа пересечений), симметрия сохраняется, то это свойство сохраняется и для большего множества. [22]
К наиболее изученным задачам этого класса относятся целочисленные задачи линейного программирования, в которых на все переменные ( либо на их часть) наложено требование целочисленности. Один из наиболее эффективных методов решения задач целочисленного программирования - г - метод ветвей и границ, исходящий прежде всего из конечности числа планов задачи и использующий ее комбинаторные свойства. Центральную идею комбинаторных методов составляет замена полного перебора всех планов их частичным перебором. Это осуществляется отбрасыванием некоторых подмножеств вариантов, заведомо не дающих оптимума. [23]
Матроиды были введены в начале тридцатых годов Биркгофом, Ван дер Варденом и Уитни, которые подошли к этому важному понятию с разных сторон. В своей книге Современная алгебра ( 1931) Ван дер Варден отмечает, что линейная независимость множеств векторов над полем и алгебраическая независимость множеств элементов поля над подполем имеют подобные комбинаторные свойства, а именно свойства ( 1 - 1) - ( 1 - 3) для независимых множеств матроидов, упомянутые перед теоремой 1.3.16. Матроиды, возникающие в случае линейной независимости векторов, в настоящее время называют линейными или координатизируемыми. [24]
У каждой топологической поверхности существует универсальное накрытие, являющееся односвяз-ной поверхностью. Если ограничиться случаем поверхностей без границ, то оказывается, что имеется лишь два типа односвязных поверхностей: 2-сфера и плоскость, если, конечно, в расчет принимаются только топологические, дифференциальные или комбинаторные свойства. [25]
Универсальная накрывающая поверхность является по определению односвязной поверхностью. Если рассматривать только поверхности без границ, то оказывается, что имеется лишь два типа односвязных поверхностей: замкнутая ориентируемая поверхность рода 0 и плоскость, при условии, конечно, что мы интересуемся только топологическими, ( вещественно) дифференциально-геометрическими или комбинаторными свойствами. [26]
Общая симметрия определяется правилами построения, применяемыми для соответствующего разбиения элементов множества на непересекающиеся подмножества, и полугруппой отображений между членами разбиения. Данное комбинаторное свойство сохраняется при отображениях, образующих полугруппу. Таким образом, операции симметрии не изменяют комбинаторное свойство, тогда как члены разбиения множества заменяются поэлементно. Напомним, что полугруппой называется множество элементов, замкнутое относительно некоторой операции, ассоциативное и содержащее единичный элемент. [27]
В § 1 мы напоминаем Главную теорему Мак-Магона и показываем на нескольких примерах ее силу. Познакомившись лично с монографией Мак-Магона [1915], читатель, безусловно, лучше бы оценил этот совершенный и быстрый способ решения различных вопросов, трудноразрешимых при иных подходах. В последующих параграфах мы изучаем моноид перегруппировок на множестве, введенный Картье и Фоата [1969], и показываем, что сущность Главной теоремы состоит в некоторых комбинаторных свойствах этого моноида. Наконец, в последних параграфах мы указываем еще одну интерпретацию Главной теоремы в терминах степенных рядов, связанных с некоторыми факторизациями свободного моноида. [28]
Комбинаторная революция в математике не идет на убыль, и поток книг и статей по комбинаторике не иссякает. Определенный вклад в такое развитие событий внес компьютер, позволивший анализировать комбинаторные задачи, слишком сложные для того, чтобы пытаться решать их другими методами. В крупных масштабах окружающий нас мир допустимо рассматривать как совокупность континуумов, описываемую методами математического анализа, но на микроуровне он предстает как мешанина дискретных элементов с загадочными скачкообразными переходами и любопытными комбинаторными свойствами. В некоторых современных теориях квантуются даже время и пространство. [29]
Первое из них возникает в результате чисто технического ограничения [ см. формулу (2.1) ] и обеспечивает единственность решения. Второе ограничение состоит в том, что коэффициент при любом одночлене системы равен нулю или единице. Это ограничение существенно и определяет комбинаторные свойства контекстно-свободных грамматик и языков. [30]