Перечисляющий многочлен

Cтраница 1

Перечисляющие многочлены gp ( x) и dp ( x) для графов и орграфов были уже выведены раньше. [1]

Перечисляющие многочлены gp ( х) и dp ( х) для графов и орграфов были уже выведены раньше. [2]

Наконец, мы найдем перечисляющий многочлен для корневых графов с шестью вершинами, у которых в качестве корня берется циклическая тройка. [3]

Два графа с одинаковым распределением. [4]

Для каждого из них получим из рис. 2 перечисляющий многочлен в случае диграфа из трех вершин. [5]

Цикловой индекс этой группы находится, и теорема Пойа дает перечисляющий многочлен для числа графов с р вершинами и данным числом ребер. [6]

Десять самообратных орграфов с тремя вершинами. [7]

По причинам, указанным ниже, при выводе требуемой формулы теорема Пойа применяется к такому ограничению степенной группы, в котором подстановки действуют на взаимно однозначные функции. Прямой проверкой убеждаемся в том, что перечисляющий многочлен d a ( x) для самообратных орграфов с тремя вершинами имеет вид ( ср. [8]

Десять самообратных орграфов с тремя вершинами. [9]

По причинам, указанным ниже, при выводе требуемой формулы теорема Пойа применяется к такому ограничению степенной группы, в котором подстановки действуют на взаимно однозначные функции. Прямой проверкой убеждаемся в том, что перечисляющий многочлен d 3 ( х) для самообратных орграфов с тремя вершинами имеет вид ( ср. [10]

Эффективный метод Пойа для перечисления графов требует построения группы подстановок, орбиты которой соответствуют в точности изоморфным классам помеченных графов с р вершинами и q ребрами. После получения явной формулы для соответствующего циклового индекса, применив теорему Пойа с рядом 1 жв качестве перечисляющего ряда для фигур, находим перечисляющий многочлен, в котором коэффициент при xq равен числу ( р, д) - графов. [11]

Эффективный метод Пойа для перечисления графов требует построения группы подстановок, орбиты которой соответствуют в точности изоморфным классам помеченных графов с р вершинами и q ребрами. После получения явной формулы для соответствующего циклового индекса, применив теорему Пойа с рядом 1 а; в качестве перечисляющего ряда для фигур, находим перечисляющий многочлен, в котором коэффициент при xq равен числу ( р, д) - графов. [12]

Сколькими способами на шахматной доске вида п х п можно разместить k слонов так, чтобы никакие два из них не атаковали друг друга. Так как слоны перемещаются по диагоналям, то очевидно, что вся доска распадается на две отдельные доски, составленные соответственно из черных или из белых клеток, и что перечисляющий многочлен для всей доски оказывается произведением многочленов для досок из черных и белых клеток. Повернув доску на 45, мы превратим поставленную задачу в задачу о ладьях с ромбовидной доской. [13]

Страницы: 1