алгоритм на связи вершин в графах

вес по критерям, я имел в виду

1. По-моему, во второй строке не 1*1---32*20, а 2*11---32*20.

2. Ты использовал связь 'a'(2)---(20)'c' два раза, что странно.

не 1*1---32*20, а 2*11---32*20.

опечатался

'a'(2)---(20)'c' два раза, что странно

why? Ладно, обе связи во втором графе соответствуют этой маске. Так какую же выбрать? опять возвращаемся к задаче выбора более подходящей связи -> к критериям?

Их вообще нельзя сопоставить, ибо набор вершин разный. в одном a,b,c,1,2,20. А во втором a,b,c,1,11,2,12,32,20,123,15

сопостовление вершин, в данном случае, отделено от сопоставления «коннекторов». В общей теории это значит, что вершины соостветствуют так:

a~a; b~b; c~c; 1~11~2~12~32~20~123~15

Ага. Ну, короче, похоже на то, что надо чётко определиться с функцией, которую ты хочешь максимизировать. Ты писал

эта связь неправильная, хотя, если более подходящей нет [...] нужно сопоставлять её

И тут, по-моему, кроется засада. Ведь то, есть или нет более подходящая связь, может зависеть от того, какая картина сложилась в других вершинах с их коннекторами.

Имеется такая зависимость или нет? Подсказка — если в функции, которую ты максимизируешь, все вершины участвуют независимо друг от друга, то и «подходящая связь» может выбираться не глядя на другие вершины (см. жадные алгоритмы). А если в функции, которую ты максимизируешь, слагаемые связаны каким-то общим условием (на рёбра или на коннекторы), то у тебя комбинаторная задача (см. задачу о рюкзаке, изоморфизм подграфу, MCS и вообще комбинаторную оптимизацию). Хотя можно и в таких задачах иногда обойтись без комбинаторного перебора  — см. остовное дерево.

1~11~2~12~32~20~123~15

час от часу не легче. Как это понять? Все вершины эквивалентны одной?

Так, ладно. Могут ли коннекторы соединять неограниченное количество вершин друг с другом?

более подходящая связь, может зависеть от того, какая картина сложилась в других вершинах с их коннекторами.

именно. Именно поэтому в моём алгоритме не выбираются ветви на каждом шаге, а изменяется их вес. Так сказать на каждую ветвь a---b смотрим с 2х сторон, со строны 'a' и со стороны 'b'

А если в функции, которую ты максимизируешь, слагаемые связаны каким-то общим условием (на рёбра или на коннекторы), то у тебя комбинаторная задача

ну да. И у меня есть алгоритм, который её решает. И благодаря ему я и получаю соответствие вершин. Я сначала хотел из него брать соответствие ветвей, но во-первых я его писал когда не ставилась задача соответствия рёбер и не ставилась даже в перспективе. А во-вторых его сложность, как комбинаторного алгоритма, боюсь, может ещё больше распухнуть от добавления в него нового функционала. Поэтому, на мой взгляд, будет проще анализировать немногочисленные, обычно 1-3, изоморфные подграфы, выданные как результат. Хотя это, вероятно, не лучшее решение :)

неограниченное количество вершин друг с другом?

в смысле может ли через 1 коннектор идти связи к n>1 вершинам? Да! иначе и задачи бы не было

Все вершины эквивалентны одной?

друг другу

1. Зарегистрировано появление нового термина: ветвь :) значение термина неизвестно.

2.

Поэтому, на мой взгляд, будет проще анализировать немногочисленные, обычно 1-3, изоморфные подграфы

Если бы ты написал бы строгим математическим языком, как считать функцию, которую ты стремишься максимизировать, я и другие люди могли бы попытаться подсказать алгоритм для этой задачи, или строго доказать, что быстрого алгоритма нет, или хотя бы указать на литературу.

Фактически, до сих пор задача не поставлена. В приведённом тобой алгоритме тоже на трезвую голову не понять ничего.

Предагаю сформулировать задачу в таких терминах:

Есть два графа: G1 и G2. В них есть вершины {a,b,c,...} и {p,q,r,...}, а также вершины-коннекторы {a(1), a(2), ..., b(1), b(2), ...} и {p(1), p(2), ..., q(1), q(2), ...}.

Ребро в графе может идти от вершины к коннектору с той же буквой, а также от коннектора к коннектору с другой буквой.

Задача: найти множество пар коннекторов {(X(i),Y(j)), X \in {a,b,c,...}, Y \in {p,q,r,...}} а также множество пар межконнекторных рёбер со следующими ограничениями:

[здесь надо указать ограничения на повторную используемость коннекторов в парах и рёбер в парах, если таковые ограничения есть] [надо также подумать о других ограничениях, например может ли пара рёбер выходить из коннекторов, которые пару не составляют, и может ли пара коннекторов иметь рёбра, которые не составлены в пары, и т.д.]

при этом максимизировать следующую функцию:

[здесть надо сформулировать «критерии» в виде: если для такой-то пары рёбер выполняется то-то и то-то, то функция увеличивается на 1]

ок, вроде всё верно.

[здесть надо сформулировать «критерии» в виде: если для такой-то пары рёбер выполняется то-то и то-то, то функция увеличивается на 1]

если установленно соответствие a~q, b~p, c~w, то

• если соблюдаются условия a(i)---b(j) && a(i)---c(k) && q(n)---p(m) && q(n)---w(l), тогда f(a(i)~q(n))<-f+1
• если соблюдаются условия a(i)---b(j) && a(k)---c(o) && q(n)---p(m) && q(e)---w(l), тогда f(a(i)~q(n))<-f+1

Уже понятнее, но всё же не до конца.

Во-первых, зачем писать f(a(i)~q(n)), если функция одна от всего набора пар. Но мысль в общем понятна — эти значения, видимо, суммируются по всем парам зафиксированных вершин.

Во-вторых, указана пачка рёбер (a(i)---b(j), q и т.д.), но не сказано — какие из них принадлежат к выбранному набору пар рёбер? Все они? Или часть из них просто рёбра графов и к выбранному набору не принадлежат?

В-третьих, не указано, как суммировать эти единицы, когда из вершины выходит много рёбер. Да что там много, если всего два ребра (и в первом графе и во втором), то мы их два раза посчитаем, поменяв местами b<->c и p<->w, или как?

неограниченное количество вершин друг с другом?

в смысле может ли через 1 коннектор идти связи к n>1 вершинам? Да! иначе и задачи бы не было

Так. хорошо. А теперь озвучь еще разок, в чем собсно задача?

Во-первых, зачем писать f(a(i)~q(n)), если функция одна от всего набора пар.

общая функция для всего набора? я просто думаю, что она складывается из ф-ций пар рёбер этого набора

но не сказано — какие из них принадлежат к выбранному набору пар рёбер? Все они?

опять же, если мы работаем с комбинаторикой, то у нас есть все возможные наборы пар соответствий рёбер. Тогда эти пачки включены в какие-то наборы

Да что там много, если всего два ребра (и в первом графе и во втором), то мы их два раза посчитаем, поменяв местами b<->c и p<->w, или как?

воот, я же про это и писал в предложенном мною алгоритме. Рассматривать нужно и связь a->b и b<-a, потому что относительно 'a' и её связей будут разные оценки относительно 'b'. Но, т.к. граф неоринтированный, можно считать соответствия ф-цию как f(a-b) = f(a->b) + f(b->a), как для одной связи a-b

найти такое множество рёбер графа B, которое максимально соответствует топологии рёбер графа A. С учётом коннекторов, или, если вам удобнее, неотделимых вершин класса 'c' от класса 'v'. Где соответствия вершин класса 'v' 2х графов заранее известно, а в классе 'c' все вершины эквивалентны между собой.

Что-то я стал запутываться снова.

Значение функции получается как сумма более маленьких значений по парам рёбер или по парам вершин-коннекторов?

1. По твоему комментарию выше вроде бы очевидно, что по парам вершин-коннекторов т.к. ты пишешь f(a(i)~q(n)); коннекторы a(i) и q(n) находятся в разных графах и поставлены в соответствие друг другу

2. Сейчас ты пишешь f(a-b), то есть как будто бы значение функции в ребре на одном графе, а также что функция «складывается из ф-ций пар рёбер этого набора»

Очевидно, из пп. 1 и 2 может быть верным лишь один. Какой?

Интересно, что является первопричиной - лисп или кикбоксинг?

Значение функции получается как сумма более маленьких значений по парам рёбер или по парам вершин-коннекторов?

я не правильно написал, правильно так

f(a'a(i)---b(j)'b ~ q'q(k)---p(m)'p) = 
= (f(a'a(i)->b(j)'b) ~ f(q'q(k)->p(m)'p)) +  (f(a'a(i)<-b(j)'b) ~ f(q'q(k)<-p(m)'p)) = 
= <с учётом истины a~q и b~p> = f(a(i)~q(k)) + f(b(j)~p(m))

Ребро состоит из 2х вершин и 2х коннекторов --> можно оценить ребро относительно других рёбер по его коннекторам(т.к. соответствие вершин дано заранее). А т.к. при рассмотрении 2х ребер:

• a'a(i)->b(j)'b
• q'q(k)->p(m)'p

нас интересует только соответствие b~p, то можно рассматривать a(i)~q(k). Если b~p верно,

• f(a(i)~q(k)) |> increment

В итоге, а так как у нас только одна пара коннекторов, в случае a->b && q->p, то итог будет сейчас, можно для каждой пары сопостовляемых ребер, соответствующей маске a'a(i)---_(_)'b ~ q'q(k)---_(_)'p, увеличить функцию f( a'a(i)---_(_)'b ~ q'q(k)---_(_)'p).

Теперь остаётся рассмотреть q->p, аналогично

поздно уже, может что напутал

Честное слово, пытался снова понять, и без малейшего успеха.

Понимаешь, ты написал алгоритм, написал цепочку преобразований и рассуждений которая, видимо, привела к его (алгоритма) появлению, но условия задачи всё ещё нет.

Преобразования и рассуждения, кстати, тоже никто никогда не поймёт. Потому что есть неписаное правило: если написана буква f, и за ней скобки, и такое встречается несколько раз, то f — это функция от того, что в скобках. Это может быть функция от

• вершины
  
• ребра
  
• пары вершин
  
• пары рёбер
  

но не от всего сразу! Нельзя писать в начале выражения f(пара рёбер), в середине f(пара неориентированных рёбер), а в конце f(пара вершин). Функция может принимать объекты лишь какого-то одного типа.

И чёрт с ним. Преобразования, упрощения, алгоритм — всё это посетители форума могут и сами сделать, не маленькие. Дай только условие! Больше ничего не надо.

Из-за того, что у тебя своё видение задачи и свой словарь терминов, ты натыкаешься на непонимание. Выход из этой ситуации есть: надо сформулировать задачу максимально скучно, избыточно, тупо и формально. С использованием знакомой всем со школы математической нотации. То есть, активно использовать слова типа:

• множество
  
• элемент из множества. Для краткости пишется так: x \in X
  
• множество пронумерованных элементов, принадлежащих какому-то надмножеству, пишется так: {a_i, a_i \in X}
  
• граф, множество вершин, множество рёбер
  
• пары вершин, пары рёбер. Пара x, y обозначается так: (x, y)
  
• множество пронумерованных пар элементов обозначается так: {(a_i, b_i)}. Если элементы из одного множества, то {(a_i, a_j)}, i != j
  
• инцидентные рёбра, соседние вершины, начало и конец ребра
  
• для всех ... существует ... такой что ...
  
• сумма ... по всем ... принадлежащим ...
  

Например:

f({(a_i, b_i)}) = сумма g((a_i, b_i)) по всем (a_i, b_i)
где
a_i принадлежит множеству вершин-коннекторов первого графа,
b_i принадлежит множеству вершин-коннекторов второго графа,
а_i != a_j при i !=j
b_i != b_j при i !=j

g({a_i, b_i}) = сумма ... по всем ..., где ...

Задача: найти множество пар {(a_i, b_i)} среди всех возможных, при котором функция f({(a_i, b_i)}) принимает максимальное значение.

Во фразах типа «все соседние вершины», указывай — это все соседние вершины в графе или все соседние вершины среди {a_i}. Всегда указывай множество, короче. Кроме того, в случаях, когда какое-то i не может быть равно какому-то j, надо это явно указывать.

Давай попробуем.

Дано:

• граф A и граф B
• ai - множество вершин A, bj - ... вершин B
• в паре (ai, bj): ai = bj, если i=j и ai != bj, если i!=j
• {ai(k)} - множество коннекторов вершины ai, {bj(m)} - множество коннекторов вершины ai
• ai(k) = bj(m), если ai=bj
• ребро r(ai(k), aj(n)) - ребро графа A, соединяющее вершины ai и aj через коннекторы ai(k) и aj(n) соответственно. Аналогично для B

Найти множество пар рёбер (r(ai(k), aj(n)), r(bi(l), bj(t)), составляющих граф C по вершинам abi и abj и коннекторам abi(k,l) и abj(n,t), максимально соответствующий по топологии графу A.
Т.е. f({(r(ai(k), aj(n)), r(bi(l), bj(t))}) принимает максимально значение.

в паре (ai, bj): ai = bj, если i=j и ai != bj, если i!=j

Я читаю: ai = bj. Это значит, натурально, ai совпадает с bj. А выше написано, что ai и bj — это элементы разных (непересекающихся) множеств. Не могут совпадать вершины двух разных графов. Получается противоречивая формулировка.

Я это пишу не для того, чтобы тебя тыкать носом, а чтобы условие задачи понять.

ai(k) = bj(m), если ai=bj

Появляется подозрение, что знаком равенства ты обозначаешь составление пары из двух элементов. Ты мог иметь в виду следующее:

Если в наборе пар вершин есть пара (ai, bj), то существуют такие k и m, что в том же наборе есть пара (ai(k), bj(m))

Если в наборе пар вершин есть пара (ai, bj), то для любого  ai(k) из множества коннекторов графа A найдётся такое m, что в наборе есть пара (ai(k), bj(m))

Если в наборе пар вершин есть пара (ai, bj), то для любого  ai(k) из множества коннекторов, участвующих в парах, найдётся такое m, что в наборе есть пара (ai(k), bj(m))

максимально соответствующий по топологии графу A. Т.е. f({(r(ai(k), aj(n)), r(bi(l), bj(t))}) принимает максимально значение.

Как определна функция f?

Теперь увидел, как определена f. Ты успел написать, пока я тебе отвечал

для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует ребро r(ai(u), ao(p)), где u!=i, то должно существовать и ребро r(bi(e), bj(m), где e!=l
для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует ребро r(ai(u), ao(p)), где u=i, то должно существовать и ребро r(bi(e), bj(m), где e=l

Уже много понятнее! Правда, по-моему вместо «u!=i», ты имел в виду «u!=k», а формулировку «где u=i» можно просто опустить, заменив в выражении u на i.

Верно ли, что ao не совпадает с aj?

Далее, ты пишешь, что функция «возрастает на парах, где выполняются условия». А если выполнятся оба условия — функция два раза возрастает? А если условия выполнятся многократно — для различных ao? «Возрастания» складываются?

Поправка

формулировку «где u=i» можно просто опустить, заменив в выражении u на i.

опять же, не на i а на k

Появляется подозрение, что знаком равенства ты обозначаешь составление пары из двух элементов.

именно, надо было, наверное, заменить = на ~

ai(k) = bj(m), если ai=bj

Я имелл в виду, что если ai~bj, то и ai(k) можно ставить в паре с bj(m)

вместо «u!=i», ты имел в виду «u!=k»

да

Верно ли, что ao не совпадает с aj?

да

А если выполнятся оба условия — функция два раза возрастает? А если условия выполнятся многократно — для различных ao? «Возрастания» складываются?

да

Дано:

• граф A и граф B
• ai - множество вершин A, bj - ... вершин B
• в паре (ai, bj): ai = bj, если i=j и ai != bj, если i!=j
• {ai(k)} - множество коннекторов вершины ai, {bj(m)} - множество коннекторов вершины ai
• ai(k) = bj(m), если ai=bj
• ребро r(ai(k), aj(n)) - ребро графа A, соединяющее вершины ai и aj через коннекторы ai(k) и aj(n) соответственно. Аналогично для B

Найти множество пар рёбер (r(ai(k), aj(n)), r(bi(l), bj(t)), составляющих граф C по вершинам abi и abj и коннекторам abi(k,l) и abj(n,t), максимально соответствующий по топологии графу A. Т.е.
f({(r(ai(k), aj(n)), r(bi(l), bj(t))}) принимает максимально значение.

фукция f определена на множестве допустимых пар рёбёр {(r(ai(k), aj(n)), r(bi(l), bj(t))} и возврастает на парах, для которых выполняются условия:

• для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и ребро r(bi(e), bo(m), где e!=l
• для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует ребро r(ai(k), ao(p)), где o!=j, то должно существовать и ребро r(bi(l), bo(m))

В данном случае расмматривается функция от направленных рёбер, для ненаправленных ф-ция строится как композиция соответствующих направленных. Т.е:
f(r(ai(k), aj(n)), r(bi(l), bj(t)) = g(r(ai(k), aj(n)), r(bi(l), bj(t)) + g( r(bi(l), bj(t)), r(ai(k), aj(n)))

я поправил, там несколько опечаток было

Окей. Заключительные вопросы:

1. Во множестве пар рёбер могут повторяться рёбра? То есть, может ли конкретное ребро, идущее из одного коннектора в другой, участвовать в друх парах?

2. На вcякий случай проверь, пожалуйста, формулировку условий для функции f. Они выглядят математически нормально, но по-человечески странно: есть ai, aj и ao, есть bi и bj, но нет никакого bo.

Вижу, чутьё насчёт bo меня не подвело. А что насчёт повторения рёбер (см. мой предыдущий коммент)?

1. Во множестве пар рёбер могут повторяться рёбра? То есть, может ли конкретное ребро, идущее из одного коннектора в другой, участвовать в друх парах?

в смысле может ли в одном множестве быть:

• (r1, r2) и (r1, r3) - да
• (r1, r2) и (r2, r1) - если рассматривается ф-ции g() от псевдо-направленных рёбер, где каждое ребро rn вида (ai(k),aj(m)) дублируется ребром (aj(m), ai(k)), то - да. Иначе нет.

Окей. Но как-то странно получается: если в графах A и B всего по одному ребру вида коннектор-коннектор, то решение, состоящее из этой пары рёбер, оказыватся не лучше пустого решения, т.к. ни одно из условий для f не может выполниться, банально по причине отсутствия ao и bo. Это нормально?

я писал что ф-ция f определена на _допустимых_ парах. Можно считать что то, что пара допустима, поднимает f от этой пары относительно пустого множества и недопустимых пар на порог достаточный для выборки этой пары.

Допустимая для f пара - пара вида (r(ai(k), aj(l)), r(bi(z), bj(t))

Можно считать что то, что пара допустима, поднимает f от этой пары относительно пустого множества и недопустимых пар на порог достаточный для выборки этой пары.

Зачем нам относительные пороги какие-то, давай в абсолютных числах считать, так проще.

Допустим, наличие пары в наборе поднимает значение f на 1. Далее, для пары (r(ai(k), aj(n)), r(bi(l), bj(t)) есть два условия:

если существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и ребро r(bi(e), bo(m), где e!=l
если существует ребро r(ai(k), ao(p)), где o!=j, то должно существовать и ребро r(bi(l), bo(m))

выполнение каждого из которых поднимает значение f на ... сколько?

К тому же, судя по тому, что ты не налагаешь ограничений на повторное использование рёбер в парах, т.е. может быть (r1, r2) и (r1, r3), то решение, максимизирующее функцию f — это просто набор всех возможных допустимых пар. Чем больше пар, тем больше значение f. Видимо, это не то, что ты хотел. Видимо, есть ещё какое-то ограничение на набор пар, которое ты не указал. Выбор очередной пары должен как-то граничивать возможность выбора следующей.

выполнение каждого из которых поднимает значение f на ... сколько?

на 1

решение, максимизирующее функцию f — это просто набор всех возможных допустимых пар. Чем больше пар, тем больше значение f.

я забыл указать, что последнее множество-ответ строится как {fmax(r(ai,aj), r(bi, bj))}.
Т.е. из каждого набора пар, вида (r(ai(z),aj(e)), r(bi(t), bj(d))) выбираются пары, где f(r(ai(k),aj(p)), r(bi(l), bj(h))) максимальна относительно остальных f(r(ai(q),aj(w)), r(bi(y), bj(u)))

Опять проблемы с определением f.

Есть разница: функция от пары рёбер и функция от множества пар рёбер. Функция от множества обозначается как f({(r1, r2), (r3,r4)...}). Функция от одной пары обозначается как f(r1, r2). Если ты один раз написал f от множества пар рёбер, нельзя потом говорить про f от пары рёбер. Можно сказать, что значение функции f от множества пар равно сумме значений функции g от каждой пары из множества, это будет понятно.

Если ты максимизируешь функцию g на множестве пар рёбер, допустимых для вершин ai,bi,aj,bj, то это одна задача, которая решается тривиально. (Вопрос о максимизации функции f после этого не стоит, потому что ты уже вычислил весь ответ путём локальной максимизации g на каждом участке.)

Если ты максимизируешь функцию f на всём множестве допустимых множеств допустимых пар рёбер, это другая задача, более сложная. Но нужно указать, какое множество допустимых пар является допустимым. Если любое — то, как я сказал, задача не имеет смысла, ты просто запихиваешь все допустимые пары в множество и ответ готов. Укажи ограничения.

Короче, ты не можешь максимизировать g и f одновременно, и тем более не можешь говорить о них как об одной функции и обозначать одной буквой.

И ещё:

если существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и ребро r(bi(e), bo(m), где e!=l
если существует ребро r(ai(k), ao(p)), где o!=j, то должно существовать и ребро r(bi(l), bo(m))

Тут много слов «существует» и «должно существовать». А к чему эти слова относятся — к изначальным графам A,B или к ответу (который ты назвал графом C)? Задача сильно зависит от этой детали.

из определеия вершины видно к какому графу она относится. тоже и для ребер.

я говорю про f от множества пар и не могу сказать про значение f в конкретной паре?

r(ai(u), ao(p)) может быть как в графе A, так и в какой-то паре из ответа.
r(bi(e), bo(m) может быть как в графе B, так и в какой-то паре из ответа.

Конечно не можешь. Так же как не можешь, например, вместо говорить о сортировке элемента списка.

Сортировка списка — это функция от списка, возвращающая другой список. А сортировка элемента списка — это бред.

То же самое с твоей числовой функцией. Она может быть либо от множества пар, либо от одной пары, но не от того и другого сразу.

r(ai(u), ao(p)) может быть как в графе A, так и в какой-то паре из ответа. r(bi(e), bo(m) может быть как в графе B, так и в какой-то паре из ответа.

ну так ответ и состоит из пар рёбер вида (ребро графа A, ребро графа B)

по поводу ф-ций, вечером подумаю как это записать математически, хотя, если честно, с этой математикой только сложнее получается, по-моему.

ну так ответ и состоит из пар рёбер вида (ребро графа A, ребро графа B)

Да. Ответ состоит из пар рёбер. А в условии написано «если существует ребро r(ai(u), ao(p)) ... то должно существовать ребро r(bi(e), bo(m)». Так где «существуют» и «должны существовать» указанные рёбра? Понятно, что всё, что имеется в наборе пар, имеется и в графах A и B. Но когда ты ставишь некоторое условие на функцию, то сказать «ребро существует в графе A» это не то же самое, что сказать «ребро существует в наборе пар». Разные задачи получатся. Просто припиши к словам «существует» указание множества (т.е. исходный граф или пары), и всё станет понятнее.

по поводу ф-ций, вечером подумаю как это записать математически, хотя, если честно, с этой математикой только сложнее получается, по-моему.

Да, но все попытки объясниться более простыми способами провалились.

• для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если графе A существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и в графе B ребро r(bi(e), bo(m), где e!=l
• для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует в A ребро r(ai(k), ao(p)), где o!=j, то должно существовать и в B ребро r(bi(l), bo(m))

Да, но все попытки объясниться более простыми способами провалились.

ну мне до сих пор кажется, что мы про простые вещи говорим сложным языком

для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если графе A существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и в графе B ребро r(bi(e), bo(m), где e!=l

для пары (r(ai(k), aj(n)), r(bi(l), bj(t)): если существует в A ребро r(ai(k), ao(p)), где o!=j, то должно существовать и в B ребро r(bi(l), bo(m))

Окей, но с такими условиями получается, что слагаемые, которые добавляются парами рёбер при (ai~bi,aj~bj), никак не зависят от того, какие пары выбраны в других местах! Например, при (ai~bi,ak~bk).

Также, никаких дополнительных условий на ограничение множества пар «в целом» ты не привёл.

Получается, что правила вычисления значения функции для одной пары зависят только от исходных A и B, и не зависят (по твоей формулировке) от того, что было выбрано на других вершинах.

Это странно, т.к. раньше ты утверждал обратное.

g( (r(ai(k), aj(n)), (r(bi(l), bj(t)))) ) ~ g(*)
r(ai(k), aj(o)) /in A
r(bi(z), bj(y)) /in B

gmax(*) <- правила:

• +1 для пары вида (r(ai(k), aj(n)), r(bi(l), bj(t)))
• +1 для пары (r(ai(k), aj(n)), r(bi(l), bj(t))): если существует ребро r(ai(u), ao(p)), где u!=k и o!=j, то должно существовать и ребро r(bi(e), bo(m), где e!=l
• +1 для пары (r(ai(k), aj(n)), r(bi(l), bj(t))): если существует ребро r(ai(k), ao(p)), где o!=j, то должно существовать и ребро r(bi(l), bo(m))

y( (r(ai, aj), (r(bi, bj))) ) = {gmax(*)}
ymax( (r(ai, aj), (r(bi, bj))) ) = sum( gmax(*) ), где gmax(*) \in {gmax(*)}
f( {y} )
fmax ( {ymax} )

Твоя нотация оригинальна, но совершенно непонятна.

Короче, пока получается всё тривиально: куски ответа вычисляются независимо на каждой четвёрке вида ((ai,aj)~(bi,bj)). Перебираешь все такие четвёрки, для каждой из них перебираешь все пары рёбер вида (r(ai(k), aj(n)), r(bi(l), bj(t)); для каждой пары вычисляешь g прямо по формуле, перебирая соседние вершины графа; пару с максимальным g записываешь в ответ.

Получаешь в итоге набор пар рёбер. Суммарные значения g на них дадут тебе значение f — максимальное из всех возможных. Что-то слишком просто выходит, не?

пару с максимальным g записываешь в ответ.

_пары_. У меня же там написано y( (r(ai, aj), (r(bi, bj))) ) = {gmax(*)}

я и говорю, что всё просто

пару с максимальным g записываешь в ответ.

_пары_

И употребил единственное число, потому что речь в том предложении шла о рассмотрении одной четвёрки вершин ((ai,aj)~(bi,bj)). Одна четвёрка — одна пара, верно?

я и говорю, что всё просто

А из-за чего тогда весь сыр-бор? Алгоритм медленно работает, или результат не устраивает?

Одна четвёрка — одна пара, верно?

да, я, видимо, не так понял

А из-за чего тогда весь сыр-бор? Алгоритм медленно работает, или результат не устраивает?

да нет, я же писал, что интересно какие алгоритмы предложат другие люди. Но другие людя меня не поняли)