Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-triange-in-p — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 11 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
 
Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
  
[[Category:На проверку]]
 
  
==Стенин Сергей группа 974==
+
<!--Вообще-то, решения уже есть-->
  
<m>
+
[[Категория:Решенные задачи]]
 
+
Рассмотрим матрицу инцидентностей $A$, $a_{ij}=1$, если между вершинами $i$ и $j$ есть ребро и нулю иначе. Возведем $A$ в третью степень. Если на диагонали полученной матрицы есть $a_{ii}\neq 0$, то для $i$-ой вершины есть путь длины три из этой вершины в неё же, то есть в графе есть треугольник. Возведение матрицы инцидентностей в третью степень можно делать за $O(n^3)$, где $n = |V|$. Таким образом, получается полиномиальный по времени ($O(|V|^3)$) и по памяти ($O(|V|^2)$) алгоритм проверки наличия треугольника в графе.
+
 
+
 
+
 
+
</m>
+

Версия 15:49, 20 мая 2020

Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».