Изменения

{{Теорема|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>. Для каждого экземпляра построим грамматики:|definition * <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>nw^R</tex> вершинами {{---}} граф, у которого каждая вершина помечена целым числом от разворот <tex>w</tex>.* <tex>1G_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>.

Более формально определить это понятие можно так: назовем распределением Если данный экземпляр ПСП имеет решение, то <tex>fL(G_2)</tex> меток в графе содержит хотя бы одну строку вида <tex>Gw\#w^R</tex> с , поэтому <tex>nL(G_1) \cap L(G_2) \ne \varnothing</tex> вершинами биекцию между множеством вершин графа , и множеством наоборот, если он не имеет решения, то <tex>\{1 \cdots n\}L(G_2)</tex>. Тогда помеченным графом называется пара не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G, fG_2)= \varnothing</tex>.

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

Все помеченные графы с тремя вершинами показаны на рисунке 1По двум КС-грамматикам <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>4L(G_1)L(G_2)</tex> различных графа . По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>3L(G_1) \cap L(G_2) \ne \varnothing </tex> вершинами приводят к , тогда и только тогда, когда <tex>8L(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|тандемный повтор]].

{| cellpadding="2"| || [[Файл:Перечисл1Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.jpg|thumb|left|420px|Рис. 1. Помеченные графы с тремя вершинами.]]|}

Для нахождения числа помеченных графов с <tex>p</tex> вершинами нужно заметитьТаким образом, что каждое из <tex dpi = "165"> p\choose 2</tex> возможных ребер либо принадлежит графу, либо нет.мы имеем:{{Теорема|about=1Утверждение|statement=Число помеченных графов с Пусть дана грамматика <tex>pG</tex> вершинами равно <tex dpi = "165"> 2^{p\choose 2}</tex>.}} Следовательно, число помеченных графов с <tex>q</tex> ребрами равно <tex dpi = "165"> {p\choose 2}\choose q</tex>. {{Теорема|author=Кэли|statement=Число помеченных деревьев с <tex>p</tex> вершинами равно <tex> p^{p - 2}</tex>.}} {{Теорема|about=2|statement=Данный граф <tex>G</tex> можно пометить <tex dpi = "160">\frac{p!}{|\GammaL(G)|}</tex> способами.|proof=Приведем набросок доказательства.  Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>XL</tex>. Для всякого элемента <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>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}} {| cellpadding="2"| || [[ФайлТогда следующие задачи неразрешимы:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]|} Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их # Содержит ли <tex>16L</tex>тандемный повтор. Среди них # Содержит ли <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}L</tex>палиндром. Порядок группы <tex>\Gamma(P_{4})</tex> равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>, то имеем <tex dpi = "160">\frac{4!}{|\Gamma(P_{4})|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\Gamma(K_{1, 3})|} = 4</tex>. == Теорема перечисления Пойа ==