ПОИСК Статьи Чертежи Таблицы Перечисление и перебор из "Графы зубчатых механизмов " Часто под перечислением понимают две задачи определение числа объектов, принадлежащих некоторому конечному множеству и обладающих заданными свойствами, и построение списка этих объектов. В этой книге термин перечисление будет относиться только к первой задаче, в то время как во второй более логично говорить не о перечислении, а о переборе объектов, или о построении множества объектов, обладающих заданными свойствами. [c.28] Многие задачи перечисления (или подсчета) можно свести к следующей стандартной схеме раскрашивания объектов. [c.28] Поставим следующую задачу перечисления. Предположим, что Г —гиперграф, вершины которого подлежат раскрашиванию. Необходимо найти число различных вариантов раскрашивания заданной спецификации. [c.28] Прежде чем решать эту задачу, уточним сначала, что понимается под различными вариантами раскрашивания, т. е., когда следует считать, что гиперграфы окрашены одинаково, а когда — по-разному. Этот вопрос не так прост, как может показаться на первый взгляд. Ясно, что если два варианта раскрашивания отличаются соответствующими значениями величин а. в. Uy,. .то такие варианты следует считать различными. Если же спецификации совпадают, то ответ усложняется. [c.29] Другими словами подстановка g переводит элемент а е 1 2 в единственный элемент ga е 1 2 и не существует другого элемента Ь ф а, который этой подстановкой тоже переводится в ga (gb = ga). [c.30] Из этого примера видно, что подстановка g переводит множество 1 2, расположенное в порядке возрастания (верхняя строка), в то же самое множество, но, быть может, по-другому упорядоченное. Если А произвольно упорядоченное множество, то символом gA обозначим результат воздействия подстановки g на множество А, при этом А и gA как множества не отличаются, но могут быть по-разному упорядочены. [c.30] что такая запись полностью сохраняет информацию о подстановке. В частности, единичный цикл (7) говорит о том, что элемент 7 переходит сам в себя. [c.33] Оказывается, любая подстановка может быть аналогично разбита на циклы, причем единственным с точностью до порядка расположения циклов образом. Число элементов в цикле называется его длиной и множество циклов, представляющих подстановку, образует разбиение множества определения подстановки I г. [c.33] Пусть подстановка состоит из mi циклов единичной длины, ГП2 циклов длины 2 и т. д. И пусть hi, Лг. [c.33] Из определения следует, что не любое подмножество множества всех подстановок степени z может называться группой. [c.34] Самой простой является группа порядка 1, состоящая из одной единичной подстановки Е = е и называемая единичной. Легко проверить, что все перечисленные в определении условия для единичной группы выполнены. [c.34] Другой крайний случай представляет группа всех возможных подстановок степени z. Такая группа называется симметрической степени г и обозначается 5г. Ее порядок равен 5г = z . Все остальные (меньшего порядка) группы подстановок степени z являются подмножествами (подгруппами) множества Sz. [c.34] Вернемся к задаче о раскрашивании. Будем раскрашивать заданным набором красок а, р, у,. .. [c.35] Таким образом, понятие различная окраска приобрело точный смысл и теперь можно вернуться к задаче подсчета числа различных, или неэквивалентных раскрасок. [c.36] Ответ на поставленную задачу дает знаменитая теорема Пойа [5], которую в упрощенном варианте можно сформулировать следующим образом. [c.36] Рассмотрим несколько примеров применения теоремы Пойа. [c.37] Этот результат можно было предвидеть заранее, так как окраска k объектов из z различных равносильна выбору сочетания k элементов из г. [c.37] И этот результат был очевиден заранее, так как подобная раскраска равносильна всевозможным размещениям k элементов (красок) в z ячейках (объектах). [c.37] Предположим теперь, что вершины гиперграфа Г перенумерованы числами от 1 до г, а — произвольная подстановка, определенная на множестве 1 2. [c.37] Будем говорить, что подстановка g применена к гиперграфу Г, если вершине с номером / присвоен номер gj для всех / е 1 z. Другими словами после применения g к Г вершины гиперграфа получают новую нумерацию в соответствии с подстановкой g. [c.38] Вернуться к основной статье