Смешенный граф и формула его перечисления

Смешенный граф и формула его перечисления. Смешанный граф может содержать как неориентированные ребра, так и ориентированные. Например, граф, изображенный на рис 1, является смешанным графом с двумя неориентированными и тремя ориентированными ребрами. Рис. 1 Смешанный граф четвертого порядка. Неориентированный граф можно трактовать как смешанный граф, не имеющий ориентированных ребер.

Далее орграф можно рассматривать как смешанный граф, заменяя для этого каждую симметричную пару ориентированных ребер неориентированным ребром. [5] Одним из основных вопросов является получение формулы, перечисляющей смешанные графы с р вершинами в соответствии с числом неориентированных и ориентированных ребер в них. Рис. 2 16 смешанных графов третьего порядка. Пусть mpqr — число смешанных графов с р вершинами, q ориентированными ребрами и г неориентированными ребрами.

Тогда многочлен mp(х, у), перечисляющий смешанные графы с р вершинами в соответствии как с числом неориентированных, так и числом ориентированных ребер, определяется формулой (1), где q+1 ≤ . Из рис. 2 следует, что при р = 3 эта формула имеет вид (2). Чтобы вывести формулу для mp(х, у), мы воспользуемся слабо модифицированной формой теоремы Пойа. В этой модификации оба вида перечисляющих рядов для фигур применяются совместно со специальным цикловым индексом, зависящим от переменных двух. Получаем равенство. Таким образом, Z ( ; Sk, tk) является цикловым индексом редуцированной упорядоченной парной группы, в котором переменные Sk используются для пар взаимно обратных циклов, а переменные tk — для самообратных циклов.

Мы увидим, что, подставляя в это выражение вместо каждой переменной Sk функцию, а вместо каждой переменной tk функцию, получим многочлен mp(х, у). [1] Теорема. Перечисляющий многочлен для смешанных графов порядка р дается соотношением (4), где В качестве примера приведем некоторые детали для случая p=3. Сначала получаем формулу для циклового индекса: (6). Подставляя перечисляющие ряды для фигур: и, приходим к выражению (7), которое полностью согласуется с формулой (2), а соответствующие ему смешанные графы показаны на рис. 2. Соотношение (5) не требует комментариев, кроме замечания о том, что оно получается из формулы с помощью ее модификации в соответствии с той частью доказательства формулы, где показывается, что каждый четный цикл подстановки из Sp индуцирует самообратный цикл. Здесь представлен краткий набросок доказательства формулы (4). Причем, степенная группа действует на функциях из множества. Так как каждая такая функция f представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то f можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами.

Очевидно, что любые две функции из множества принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны.

Наконец, функциям обычным образом приписываются веса и, применяя взвешенный вариант леммы Бернсайда, получают соотношение (4). Идея использования выражения 1+2x+y состоит в следующем: слагаемое 1 соответствует парам несмежных вершин, в то время как 2х указывает на две возможные ориентации, а у — на неориентированное ребро.

Радикал в выражении, исчезает в mp(х, у), потому что каждая переменная Sk встречается только в четной степени, ибо взаимно обратные циклы обязательно появляются парами.

Аналогично двучлен 1+y отражает, как обычно, отсутствие ребра и наличие неориентированного ребра (ориентированные ребра просто запрещены для самообратных циклов). Радикал в, также исчезает в mp(х, у), ибо, как показано в формуле (5), в единственном ее произведении, содержащем tk, индексы к — четные. Это в свою очередь справедливо потому, что каждый самообратный цикл имеет четную длину.

Перечисляющие многочлены gp(x) и dp(x) для графов и орграфов будем считать выведенными. Многочлен ор(х) для направленных графов найден Харари. Заметим, что каждый из этих многочленов легко получается из mp(х, у), который является, таким образом, одновременным обобщением всех трех указанных перечислительных формул: dp(x) = mp(x, ), ор(х) = mр(х,0), gp(y) = mp(0, у) (8). Для р = 3 находим, используя соотношение (7): d3(x) = m3(x, ) = 1 + x + 4 о3(х) = m3(х,0) = 1 + x + g3(y) = m3(0, у) = 1 + y + Правильность этих выражений легко установить с помощью рис. 2. [3]