Варианты раскрашивания

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

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

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

Рис. 2.1. Варианты раскрашивания гиперграфов

Во многих случаях можно считать, что неразличимость объектов задается группой подстановок G на их множестве. Тогда две функции (/i и /2) называются эквивалентными (а значит, эквивалентными являются и соответствующие им варианты раскрашивания), если существует такая подстановка g G, что для всех а е 1 2 [c.36]

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

Отметим, что любой вариант раскрашивания ги-перграфа можно рассматривать как частично определенную на множестве 1 z функцию [c.29]

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

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