Максимальная выполнимость формул в 2-КНФ: различия между версиями

Следующим шагом будет использование быстрого произведения расстояний для поиска треугольника с максимальным весом в реберно-взвешенном графе с n вершинами. Рассмотрим множество вершин G как множество {1, ..., n}. Определим A как матрицу размера n x n, такую, что A[i, j] = - w({i, j}), если существует ребро {i, j}, и A[i, j] = <math>\infty</math> в противном случае. Утверждение заключается в том, что треугольник с весом не менее K включает вершину i тогда и только тогда, когда <math>(A \otimes_d B \; A \otimes_d A) [i, j] \le -K</math>. Это объясняется тем, что данное неравенство выполняется тогда и только тогда, когда существуют отличные друг от друга j и k, такие, что {i, j}, {j, k}, {k, i} – ребра, и A[i, j] + A[j, k] + A[k, i] <math>\le</math> -K, то есть w({i, j}) + w({j, k}) + w({k, i}) <math>\ge</math> K.

 

Поэтому, найдя i, такой, что <math>(A \otimes_d B \; A \otimes_d A) [i, j]</math> минимизировано, мы получим вершину i, содержащуюся в максимальном треугольнике. Для получения фактического треугольника следует проверить все m ребер {j, k} на предмет того, является ли {i, j, k} треугольником. □