Полиномиальные сводимости и 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