Теорема - перечисление
Cтраница 2
Его теорема перечисления, если ее соединить с его же теоремой декомпозиции, пригодна также для перечисления графов и орграфов. [16]
Многие классы деревьев могут быть перечислены с помощью той процедуры, которая изложена в предыдущих параграфах этой главы. Обычно сначала с помощью теоремы перечисления Пойа находят производящую функцию для корневых многообразий. Затем теорема о характеристике неподобия обеспечивает нас средством, позволяющим выразить ряд для некорневых деревьев через ряд для корневых деревьев. В этом параграфе мы рассмотрим несколько задач, которые могут быть успешно решены указанным способом. [17]
Соотношение (3.2.4), приводимое в основной теореме данного параграфа, является наиболее изящной из возможных формул, выражающих ряд t ( х) для деревьев через ряд Т ( х) для корневых деревьев. Доказательство формулы (3.2.4) зависит не только от теоремы перечисления взаимно однозначных функций, но и от следствия из устанавливаемой ниже теоремы о характеристике неподобия. [18]
Все деревья являются пленарными, так что число планарных деревьев равно числу всех деревьев. Плоские унициклические графы легко перечисляются с помощью теоремы перечисления Пойа ( см. соотношение (2.4.6)): в качестве перечисляющего ряда для фигур нужно взять перечисляющий ряд для плоских корневых деревьев, а в качестве группы конфигураций надо использовать диэдральную группу. [19]
В статье Харари [4] формула для / ( х, у) получена путем подходящего применения теоремы перечисления Пойа и обобщения формулы (3.1.1) на случай произвольной функции g ( x, у), зависящей от двух переменных. [20]
В статье Харари [4] формула для / ( х, у) получена путем подходящего применения теоремы перечисления Пойа и обобщения формулы (3.1.1) на случай произвольной функции g ( х, у), зависящей от двух переменных. [21]
В этом параграфе изучаются некоторые понятия, относящиеся к деревьям и связанные со структурами достаточно высокой размерности. Для того чтобы перечислить специальные двумерные структуры, называемые 2-деревьями, приходится дополнительно развить теорию характеристики неподобия и применять теоремы перечисления Пойа. Наши методы можно приспособить к перечислению таких 2-деревьев, которые уложены на плоскости, и, таким образом, предлагается новый подход к старой задаче о нахождении числа триангуляции многоугольника. [22]
В этом параграфе изучаются некоторые понятия, относя-циеся к деревьям и связанные со структурами достаточно высокой размерности. Для того чтобы перечислить специальные щумерные структуры, называемые 2-деревьями, приходится до-юлнительно развить теорию характеристики неподобия и применять теоремы перечисления Пойа. Наши методы можно приспособить к перечислению таких 2-деревьев, которые уложены га плоскости, и, таким образом, предлагается новый подход к старой задаче о нахождении числа триангуляции многоугольника. [23]
Глава 6 содержит доказательство мощной теоремы перечисления степенной группы; там же показано, как применять эту теорему. Глава 7, названная Суперпозиция, посвящена задачам перечисления таких конфигураций, которые могут быть построены путем наложения одних объектов на другие. [24]
Мы начнем с самых простых задач перечисления, а именно с перечисления помеченных графов. Затем приведем классическую теорему перечисления, принадлежащую Пойа, и применим ее к нахождению перечисляющих рядов для деревьев и других видов графов. Будет дано также обобщение теоремы Пойа ( так называемая теорема перечисления степенной группы), полезное при исследовании проблем перечисления, в которых эквивалентные классы задаются с помощью двух групп подстановок. [25]
Если с ( х) - ряд, перечисляющий элементы множества У, и А - группа подстановок с множеством объектов X, то, как мы видели в гл. Существует обширный класс задач, для решения которых весьма важно уметь перечислять орбиты в множестве Vх степенной группы ВА, когда группа В не является единичной. По этой причине упомянутый результат де Брейна мы в дальнейшем предпочитаем называть теоремой перечисления степенной группы. В качестве приложений этой теоремы приводятся решения задач перечисления самодополнительных графов и орграфов, графов с раскрашенными ребрами, конечных автоматов и самообратных орграфов. [26]
Если с ( х) - ряд, перечисляющий элементы множества Y, и А - группа подстановок с множеством объектов X, то, как мы видели в гл. Существует обширный класс задач, для решения которых весьма важно уметь перечислять орбиты в множестве Yx степенной группы ВА, когда группа В не является единичной. По этой причине упомянутый результат де Брейна мы в дальнейшем предпочитаем называть теоремой перечисления степенной группы. В качестве приложений этой теоремы приводятся решения задач перечисления самодополнительных графов и орграфов, графов с раскрашенными ребрами, конечных автоматов и самообратных орграфов. [27]
 |
Пять триангулированных пятиугольников, каждый из которых имеет ориентированное граничное ребро. [28] |
Сначала осуществим перечисление унициклических графов, потому что подход, используемый при их перечислении, может быть приспособлен к перечислению функциональных орграфов. Унициклический граф является связным графом, имеющим только один простой цикл. Если G - унициклический граф и его простой цикл имеет длину п, то G можно рассматривать как граф, имеющий корневые деревья, возможно тривиальные, прикрепленные к каждой из п вершин его цикла. Если степенная группа Е п имеет множество объектов Yx, то орбиты, состоящие из функций множества Vх, соответствуют в точности унициклическим графам. Следовательно, теорема перечисления Пойа дает такой результат. [29]
 |
Пять триангулированных пятиугольников, каждый из которых имеет ориентированное граничное ребро. [30] |
Страницы: 1 2 3