4622
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 13:56, 25 марта 2025
, 25 март→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 28: | Строка 28: | ||
Пусть A и B – матрицы с элементами из R | Пусть A и B – матрицы с элементами из <math>\R \cup \{ \infty \}</math>. ''Произведением расстояний'' между A и B (сокращенно записываемым как <math>A \otimes_d B</math>) называется матрица C, определяемая по формуле <math>C[i, j] = min_{k = 1, ..., n} \{ A[i, k] + B[k, j] \}</math>. | ||
C[i, j] = | |||
Что касается m и n, то применительно к графам они обозначают количество ребер и вершин графа, соответственно. В то же время в КНФ-формулах m и n обозначают количество дизъюнктов и переменных, соответственно. | |||
== Основные результаты == | == Основные результаты == | ||
