Hardprob/Minimum Cut Cover — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, …, \3<sub>\4</sub></em>)
Строка 1: Строка 1:
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
+
<!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}}
  
 
Граф <em>G=(V,E)</em>.
 
Граф <em>G=(V,E)</em>.
Строка 13: Строка 13:
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
+
* {{has-testdata-and-visualization}}
<!-- * {{has-pyomo-model}} -->
+
* {{has-pyomo-model}}
 
<!-- * {{has-npc-reduction}} -->
 
<!-- * {{has-npc-reduction}} -->
 
<!-- * {{add-random-fuzzing-tests}} -->
 
<!-- * {{add-random-fuzzing-tests}} -->

Версия 08:12, 19 апреля 2023

Minimum-cut-cover.png

Граф G=(V,E).

Найти коллекцию разрезов V1, …, Vm, т.е. коллекция подмножеств вершин , такая что каждое ребро графа (u,v)∈ E свои концы держит в разных подмножествах, т.е.

  • либо и
  • либо и

Минимизировать размер «m» этой коллекции.


Задача в лаб22 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.