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

Версия 02:14, 26 декабря 2014

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

@@ Строка 1: / Строка 1: @@
 Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
-[[Category:На проверку]]
+[[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>