Изменения

|about=2|statement=Данный граф <tex>G</tex> можно пометить <tex dpi = "160">\frac{p!}{|\Gamma(G)|}</tex> способамиЗадача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Приведем набросок доказательства.  Пусть <tex>A</tex> = \{{---}} группа подстановок(G_1, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x G_2) \in X</tex> '''орбитой''' <tex>mid L(G_1) \Thetacap L(xG_2)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>= \alpha varnothing \cdot x = y}</tex> для некоторой подстановки . Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>overline{A}</tex>, состоящая из всех подстановок из <tex>A</tex>таким образом показав, оставляющих элемент <tex>x</tex> неподвижнымчто дополнение проблемы неразрешимо. Теорема является следствием соотношения <tex>Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контекстезамкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.}}

{| cellpadding="2"Для любого экземпляра ПСП <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 :Перечисл2S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>.jpg|thumb|left|720px|РисТогда <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>.]]|}

Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их Если данный экземпляр ПСП имеет решение, то <tex>16L(G_2)</tex>. Среди них содержит хотя бы одну строку вида <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4w\#w^R</tex> {{---}} графу <tex>K_{1, 3}</tex>. Порядок группы поэтому <tex>L(G_1) \Gammacap L(P_{4}G_2)\ne \varnothing</tex> равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>и наоборот, если он не имеет решения, то имеем <tex dpi = "160">\frac{4!}{|\GammaL(P_{4}G_2)|} = 12</tex> и не содержит строк такого вида, соответственно <tex dpi = "160">L(G_1) \frac{4!}{|\Gammacap L(K_{1, 3}G_2)|} = 4\varnothing</tex>.

== Теорема перечисления Пойа == Пойа показал, как получить формулу, перечисляющую орбиты в соответствии с весами и зависящую от циклической структуры подстановок данной группы. {{Теорема|statement=Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex> с орбитами Таким образом мы свели проблему соответствий Поста к <tex>\Theta_overline{1}, \Theta_{2} \cdots \Theta_{nA}</tex> и <tex>\omega</tex> {{---}} функция, приписывающая веса каждой орбите (весовая функция). Более тогоследовательно, <tex>\omega</tex> определяется задача о проверке на <tex>X</tex> так, что <tex>\omega(x) = \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}| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}\omega(x)</tex> для каждой орбиты <tex>\Theta_{i}</tex>. Домножив второе равенство на первое и сократив, получаем <tex>|A| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>. Суммируя по всем орбитам, находим <tex>|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>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5. Для подстановки D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\alpha#</tex> через , где <tex>j_\#</tex> {{k---}}новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \alphacap L(G_2)\ne \varnothing </tex> обозначим число циклов длины , тогда и только тогда, когда <tex>kL(G_1)\#L(G_2)\#</tex> в её разложении в произведение непересекающихся цикловсодержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

{{Лемма|author=Бернсайд|statement=Число Аналогично можно заметить, что пересечение <tex>NL(AG_1)</tex> орбит группы подстановок <tex>A</tex> равно <tex>N(A) = \frac{1}{|A|}\sum\limits_{\alpha \in A}j_{1}cap L(\alphaG_2)</tex>.|proof=Так как в доказательстве этой леммы мы не учитываем значения весовой функции, то <tex>|A|N(A) = \sum\limits_{\alpha \in A} \sum\limits_{x = ne \alpha x}1varnothing </tex>тогда и только тогда, но <tex>\sum\limits_{x = \alpha x}1когда </tex> и есть <tex>j_{1}L(\alphaG_1)</tex>, то есть для получения исходной формулы нужно поделить обе части равенства на <tex>|A|</tex>.}} = Теорема Гуйя-Ури = {{Определение|definition=Ориентированный сильно связный граф называется '''орсвязаными'''.}} == Лемма о длине цикла в ориентированном графе =={{Лемма|about=о длине цикла в ориентированном графе|statement= Пусть <tex>G</tex> {{---}} произвольный ориентированный граф и для каждой вершины <tex>v \in V#L(GG_2)</tex> выполняется <tex>deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.|proof=Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Из последней вершины <tex>v_s</tex> выходит хотя бы <tex>\delta - 1</tex> ребро в вершины, отличные от <tex>v_{s - 1}</tex>. Так как путь <tex>P</tex> максимальный, то продлить его нельзя, а значит, что из <tex>v_s</tex> выходят ребра только в вершины, содержащиеся в пути <tex>P</tex>. Пусть <tex>v_m \in P</tex> {{---}} вершина с наименьшим номером, в которую входит ребро из <tex>v_s</tex>. Тогда во множество <tex>\{v_m \dots v_{s - 1}\}</tex> входят не менее <tex>\delta</tex> ребер, выходящих из <tex>v_sR</tex>содержит палиндром. То есть в это множестве хотя бы <tex>\delta</tex> вершин. Значит, в цикле <tex>v_m \dots v_{s - 1} v_s</tex> не менее <tex>\delta + 1</tex> вершины.}} == Теорема Гуйя-Ури =={{Теорема|author=Гуйя-Ури, Ghouila-Houri|statement=Если <tex>G</tex> {{---}} сильно связный ориентированный граф c <tex>n</tex> вершинами и для каждой <tex>v \in V(G)</tex> выполняется <br><tex>\Bigg\{\begin{matrix} deg^{in}(v) \geqslant n/2 \\ deg^{out}(v) \geqslant n/2 \\

\end{matrix} </tex>Таким образом, <br>мы имеем:тогда <tex>G</tex> {{---}} гамильтонов.Утверждение|proofstatement=Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф Пусть дана грамматика <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>L(G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P ) = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>CL</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить). <br>следующие задачи неразрешимы:Пусть <tex>a</tex> {{---}} количество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>a</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней # Содержит ли <tex>l + 1</tex> вершина не является ни прямым предком <tex>v_0</tex>, ни прямым потомком <tex>v_lL</tex>тандемный повтор. <br>Рассмотрим оставшуюся <tex>a - 1</tex> вершину, отличную от # Содержит ли <tex>yL</tex>палиндром.