Hardprob/Maximum Common Embedded Sub-Tree — различия между версиями

Текущая версия на 22:33, 17 апреля 2023

Деревья T₁ и T₂ с метками на вершинах.
Найти общее встроенное поддерево, т.е. помеченное дерево T', которое можно встроить в оба исходных дерева. Встраивание из T' в T, это инъективная функция от вершин T' в вершины T, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
Максимизировать размер общего поддерева, |T'|.

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Деревья <m>T_1</m> и <m>T_2</m> с метками на вершинах.
+* Деревья <em>T<sub>1</sub></em> и <em>T<sub>2</sub></em> с метками на вершинах.
 * Найти общее встроенное поддерево, т.е. помеченное дерево <em>T'</em>, которое можно встроить в оба исходных дерева. Встраивание из <em>T'</em> в <em>T</em>, это инъективная функция от вершин <em>T'</em> в вершины <em>T</em>, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
-* Максимизировать размер общего поддерева, <m>\vert T'\vert</m>.
+* Максимизировать размер общего поддерева, <em>|T'|</em>.
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+<!-- * {{has-testdata-and-visualization}} -->
+<!-- * {{has-pyomo-model}} -->
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>