Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-triange-in-p — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 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> |
Версия 11:03, 22 ноября 2014
Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
Стенин Сергей группа 974