Даны два списка строк U и V. Возьмите перекрестное произведение U и V, назовите этот набор W. Создайте новый список L такой, что L = {x + y: для всех (x, y) в W} Пример: U = [ab, cd], V = [gh, k]. Тогда L = [abgh, abk, cdgh, cdk]. И назовите эту операцию нахождения L из U, V как *.
L = U✕V
Теперь, учитывая L, найдите U и V. (обратный двоичному оператору). Предположим, что возможно только одно уникальное решение.
Эта проблема может быть решена с помощью некоторого метода сортировки или некоторого метода tr ie. Но для меня важно ответить на вопросы, приведенные ниже.
Мы составляем список всех возможных префиксов слов, присутствующих в списке L (назовем его P), и список всех возможных суффиксы слов, присутствующих в списке L (назовите его S). Мы создаем двудольный граф G (P, S, E), такой, что существует грань между префиксом x и суффиксом y, если x + y присутствует в L. Я совершенно уверен, что будет один полный двудольный подграф, присутствующий в it.
Сколько полных двудольных подграфов с числом ребер большим или равным длине L присутствует в этом двудольном графе G? Если существует полный двудольный подграф (назовем его G '(A, B, F)) с длиной, большей или равной L, можем ли мы доказать, что A✕B = L? Предположим, что в данном списке L есть только одно уникальное разложение (U, V).
Это не какая-либо домашняя задача, эти вопросы - мои сомнения. И я довольно новичок в теории графов, и я не знаю, как это доказать или сделать какой-либо вывод. Мне известно о том, что поиск полных двудольных подграфов не решаем за полиномиальное время.