Спецификация раскрашивания

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

Система различных представителей — 129 Сочленение— 16 Спецификация раскрашивания — 28 Список рёбер — 11 Степень группы — 34 Схема геометрически совместная — 174 [c.214]

Поставим следующую задачу перечисления. Предположим, что Г —гиперграф, вершины которого подлежат раскрашиванию. Необходимо найти число различных вариантов раскрашивания заданной спецификации. [c.28]

Прежде чем решать эту задачу, уточним сначала, что понимается под различными вариантами раскрашивания, т. е., когда следует считать, что гиперграфы окрашены одинаково, а когда — по-разному. Этот вопрос не так прост, как может показаться на первый взгляд. Ясно, что если два варианта раскрашивания отличаются соответствующими значениями величин а. в. Uy,. .то такие варианты следует считать различными. Если же спецификации совпадают, то ответ усложняется. [c.29]

На рис. 2.1 изображены три варианта раскрашивания одного и того же гиперграфа. Все варианты имеют одинаковую спецификацию а у. Однако легко [c.29]

Для каждого варианта раскрашивания введем понятие спецификации красок, символически записываемой в виде [c.64]

Очевидно, любому раскрашиванию объектов из множества 1 z, спецификация которого удовлетворяет условиям (2.31) — (2.35), однозначно соответствует семейство (2.30), задающее передаточное отношение (2.27). [c.65]

Теорема Пойа. Пусть V = а, р, у, — множество красок, 1 2—множество объектов, подлежащих раскрашиванию, и О—заданная группа подстановок на 1 2. Тогда число различных способов раскрашивания заданной спецификации (2.1) равно коэффициенту при одночлене (2.1) в многочлене [c.36]

Чтобы найти число способов раскрашивания данной спецификации, будем смотреть на (2.37) как на одночлен, состоящий из формальных переменных 0, е, т, Фь ф2, . фа-2, возведенных соответственно в степени М0, Ие, Ux, uu U2,. .., 0-2- Тогда согласно теореме Пойа это число равно коэффициенту при выражении вида (2.13) в многочлене [c.65]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...