Изменения

{{Теорема|statement= Перечисления графов Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) =\{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = Помеченные графы =1, 2, \dots n</tex>. Тогда <tex>L(G_2) =\{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.

{{Определение|definition ='''Помеченный граф''' с Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>nL(G_1) \cap L(G_2) \ne \varnothing</tex> вершинами {{---}} граф, у которого каждая вершина помечена целым числом от и наоборот, если он не имеет решения, то <tex>1L(G_2)</tex> до не содержит строк такого вида, соответственно <tex>nL(G_1) \cap L(G_2) = \varnothing</tex>.}}

Более формально определить это понятие можно так: назовем распределением <tex>f</tex> меток в графе <tex>G</tex> с <tex>n</tex> вершинами биекцию между множеством вершин графа и множеством Таким образом мы свели проблему соответствий Поста к <tex>\overline{1 \cdots n\A}</tex>. Тогда помеченным графом называется пара <tex>(G, f)</tex>. {{Определение|definition =Два помеченных графа <tex>(G_{1}, f_{1})</tex> и <tex>(G_{2}, f_{2})</tex> '''изоморфны''', если существует изоморфизм между <tex>G_{1}</tex> и <tex>G_{2}</tex>следовательно, сохраняющий распределение метокзадача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

Все помеченные графы с тремя вершинами показаны на рисунке 1. По двум КС-грамматикам <tex>4G_1</tex> различных графа с и <tex>3G_2</tex> вершинами приводят к <tex>8</tex> различным помеченным графам. {| cellpadding="2"| || можно построить КС-грамматику для [[Файл:Перечисл1Замкнутость КС-языков относительно различных операций#.jpg|thumb|left|420px|РисD0. 19A. Помеченные графы с тремя вершинамиD0.]]|} Для нахождения числа помеченных графов с <tex>p</tex> вершинами нужно заметить, что каждое из <tex dpi = "165"> p\choose 2</tex> возможных ребер либо принадлежит графу, либо нетBE. {{Теорема|about=1|statement=Число помеченных графов с <tex>p</tex> вершинами равно <tex dpi = "165"> 2^{p\choose 2}</tex>D0.}} Следовательно, число помеченных графов с <tex>q</tex> ребрами равно <tex dpi = "165"> {p\choose 2}\choose q</tex>BD. {{Теорема|author=Кэли|statement=Число помеченных деревьев с <tex>p</tex> вершинами равно <tex> p^{p - 2}</tex>D0.}} {{Теорема|about=2|statement=Данный граф <tex>G</tex> можно пометить <tex dpi = "160">\frac{p!}{|\Gamma(G)|}</tex> способамиBA.|proof=Приведем набросок доказательстваD0.  Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>B0. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>D1. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным82. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контекстеD0.}} {| cellpadding="2"| || [[Файл:Перечисл2B5.jpg|thumb|left|720px|РисD0. 2BD. Помеченные деревья с четырьмя вершинамиD0.]]|} Рассмотрим примерB0. На рисунке 2 изображены все помеченные деревья с четырьмя вершинамиD1. Всего их <tex>16</tex>86. Среди них <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}</tex>D0. Порядок группы <tex>\Gamma(P_{4})</tex> равен <tex>2</tex>B8. Порядок группы <tex>K_{1, 3} = 6</tex>D1. Так как <tex>p = 4</tex>, то имеем 8F|конкатенации]] задаваемых ими языков <tex dpi = "160">\frac{4!}{|\GammaL(P_{4}G_1)|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\GammaL(K_{1, 3}G_2)|} = 4</tex>. == Теорема перечисления Пойа == Пойа показал, как получить формулу, перечисляющую орбиты в соответствии По аналогии с весами и зависящую от циклической структуры подстановок данной группы. {{Теорема|statement=Пусть этим мы можем рассматривать язык <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex> с орбитами <tex>\Theta_{1}, \Theta_{2} \cdots \Theta_{n}</tex> и <tex>\omega</tex> {{---}} функция, приписывающая веса каждой орбите L(весовая функцияG_1). Более того, <tex>\omega</tex> определяется на <tex>X</tex> так, что <tex>\omega#L(xG_2) = \omega(\Theta_{i})#</tex>, если где <tex>x \in \Theta_{i}</tex>. Тогда сумма весов орбит равна <tex>|A| \sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x} \omega(x)</tex>.|proof=Уже упоминалось о том, что порядок <tex>|A|</tex> группы <tex>A</tex> равен <tex>|A(x)| \cdot |\Theta(x)|</tex> для любого <tex>x \in X</tex>, где <tex>A(x)#</tex> {{---}} стабилизатор элемента <tex>x</tex>новый символ, не встречающийся в алфавите. Так как весовая функция постоянна на элементах данной орбитыЗаметим, что пересечение языков непусто, то справедливо равенство есть <tex>|\Theta_{i}| \omegaL(\Theta_{i}G_1) = \sum\limits_{x \in \Theta_{i}}\omegacap L(xG_2)</tex> для каждой орбиты <tex>\Theta_{i}ne \varnothing </tex>. Домножив второе равенство на первое , тогда и сокративтолько тогда, получаем когда <tex>|A| \omegaL(\Theta_{i}G_1) = \sum\limits_{x \in \Theta_{i}}|A#L(xG_2)|\omega(x)#</tex>содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1. Суммируя по всем орбитам, находим <tex>80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|A|\sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{i=1}^n \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>, откуда непосредственно следует доказываемое соотношениетандемный повтор]].}}

Как следствие из этой теоремы выведем традиционную формулу Бернсайда. Для подстановки Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \alphavarnothing </tex> через тогда и только тогда, когда <tex>j_{k}L(G_1)\alpha#L(G_2)^R</tex> обозначим число циклов длины <tex>k</tex> в её разложении в произведение непересекающихся цикловсодержит палиндром.

Таким образом, мы имеем:{{Лемма|author=БернсайдУтверждение|statement=Число Пусть дана грамматика <tex>N(A)G</tex> орбит группы подстановок <tex>A</tex> равно , <tex>NL(AG) = \frac{1}{|A|}\sum\limits_{\alpha \in A}j_{1}(\alpha)L</tex>.Тогда следующие задачи неразрешимы:|proof=Так как в доказательстве этой леммы мы не учитываем значения весовой функции, то # Содержит ли <tex>|A|N(A) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x}1L</tex>, но <tex>\sum\limits_{x = \alpha x}1тандемный повтор.# Содержит ли </tex> и есть <tex>j_{1}(\alpha)</tex>, то есть для получения исходной формулы нужно поделить обе части равенства на <tex>|A|L</tex>палиндром.