Отношение толерантности: близость и пересекающиеся блоки

Два изображения могут отличаться совсем немного, второе и третье тоже похожи, но первое и третье уже различаются заметно. Такая близость не обязана передаваться по цепочке. В дискретной математике её удобно описать отношением толерантности: оно связывает каждый объект с самим собой и действует одинаково в обе стороны, но не требует транзитивности.
На модели ниже можно менять допустимую разность чисел и видеть матрицу связей. Обратите внимание, при каких порогах появляется тройка, нарушающая транзитивность, и что происходит при самых малом и большом порогах.
Близость как бинарное отношение
Пусть - множество объектов. Отношение называют толерантностью на множестве, если оно рефлексивно и симметрично:
Первое условие означает, что объект связан с собой; второе - что связь взаимна. При этом из и не обязательно следует . Слово «не обязательно» важно: транзитивные отношения тоже допускаются. Например, равенство одновременно является толерантностью и эквивалентностью.
Отношение состоит из упорядоченных пар, а не из самих объектов. Если и , симметричность требует присутствия обеих пар и . Чтобы разобраться с записью произведения множеств и пар, полезно вспомнить декартово произведение. В контексте алгебраических структур термин может дополнительно требовать совместимости отношения с операциями; здесь мы рассматриваем отношение на множестве без такого дополнительного условия.
Пример: порог расстояния
Возьмём и определим условием . Это учебная модель: числа могут обозначать значения признака, а единица - выбранный допуск. Каждое число отстоит от себя на ноль, а расстояние от до равно расстоянию от до . Следовательно, отношение рефлексивно и симметрично.
Движение ниже проходит по цепочке : каждый соседний шаг укладывается в допуск, но расстояние между крайними точками равно двум. Поэтому прямой связи концов нет. Это конкретное свидетельство отсутствия транзитивности, а не просто отсутствие какой-то пары.
Например, и принадлежат , но не принадлежит . Здесь выполняются обе посылки транзитивности, а заключение нарушается. При другом пороге вывод может измениться: на этом конечном множестве при пороге 0 остаётся только равенство, а при пороге 3 связаны все пары. Оба крайних отношения транзитивны.
Как читать матрицу
В строке и столбце поставим единицу, когда , и ноль в противном случае. Для порога 1 получается:

Диагональ содержит четыре единицы: каждая подтверждает связь элемента с собой. Матрица симметрична относительно диагонали: например, клетки и одинаковы. Всего в ней десять единиц, то есть десять упорядоченных пар, включая четыре диагональные. Проверяя по инструменту другие пороги 0, 2 и 3, получим соответственно 4, 14 и 16 пар.
Чтобы найти нарушение транзитивности, ищите не отдельный ноль, а цепочку: в клетках и стоят единицы, тогда как в - ноль. Это удобно автоматизировать тремя циклами по элементам. О матричных признаках других отношений подробнее рассказано в статье про свойства бинарных отношений.
Окрестность и блок: разные объекты
Окрестность элемента - множество всех элементов, связанных с ним: . В примере . Однако ноль и двойка между собой не связаны, поэтому внутри этой окрестности не все элементы попарно близки.
Назовём множество попарно совместимым, если . Блок - такое множество, которое нельзя расширить включением ещё одного элемента из , сохранив попарную совместимость. Максимальность здесь понимается по включению: блок не обязан иметь наибольший размер среди всех возможных блоков.
Для нашего примера блоки равны , и . В каждой паре расстояние не больше единицы; добавить к любой паре ещё один элемент нельзя. Окрестность не является блоком, потому что содержит несовместимые 0 и 2. Эти определения и связь блоков с покрытиями рассмотрены в исследовании On the coverings by tolerance classes.
Почему блоки пересекаются
Блоки и пересекаются по элементу 1, но не совпадают. Близость к одному и тому же элементу не заставляет крайние элементы быть близкими друг другу. Все три блока вместе покрывают , однако не образуют разбиения, поскольку пересекаются.
В графе можно убрать петли из рисунка и соединить разные вершины ребром, когда соответствующие элементы связаны. Блоки тогда соответствуют максимальным по включению кликам: множествам вершин, соединённых попарно и не расширяемых с сохранением этого свойства. Так можно искать блоки конечного отношения, но важно не смешивать максимальную клику с кликой максимального размера. Для связи с графовыми задачами см. также максимальное независимое множество: в дополнении графа клика исходного графа становится независимым множеством.
Как найти блоки по шагам
Для небольшого конечного множества удобно начать с матрицы. Сначала проверьте диагональ и зеркальные клетки: если хотя бы одно из этих условий не выполнено, перед нами не толерантность и выводы о её блоках применять без оговорок нельзя. Затем выберите элемент и попробуйте присоединить к нему другой, сохраняя единицы для всех пар внутри полученного множества. Для третьего элемента нужно проверить его связь не только с первым, но и со вторым. Продолжайте, пока ни один оставшийся элемент нельзя добавить.
Например, начнём с единицы. Ноль можно добавить, но после этого двойку добавить нельзя: клетка равна нулю. Получаем блок . Если вместо нуля выбрать двойку, возникает другой блок ; тройка к нему не добавляется из-за отсутствия связи с единицей. Начав с двойки и тройки, получим ещё . Чтобы убедиться в полноте списка, заметим: любые два числа, отличающиеся больше чем на единицу, несовместимы, а каждый одиночный элемент входит хотя бы в одну из перечисленных пар.
Один жадный проход не гарантирует полный список: выбор первого соседа влияет на результат. Для произвольной конечной матрицы можно перебрать подмножества, проверить попарные связи и оставить только не расширяемые. На больших множествах число подмножеств быстро растёт; используют алгоритмы перечисления максимальных клик, а размер данных и число самих блоков влияют на стоимость решения. Поэтому до вычислений полезно решить, нужны ли вообще все блоки или достаточно проверить один заданный кандидат.
Сравнение с эквивалентностью и применение
Отношение эквивалентности обладает теми же двумя свойствами и дополнительно транзитивно. Его классы либо совпадают, либо не пересекаются; у произвольной толерантности такое утверждение неверно. Если построить транзитивное замыкание нашего примера, цепочка свяжет все четыре числа. Это даст эквивалентность, но добавит пары вроде , не удовлетворяющие исходному порогу. Замыкание отвечает на вопрос о достижимости по цепочке, а не о прямой близости.
В задачах обработки данных пороговое отношение может описывать похожесть записей по выбранной метрике: одинаковая запись имеет расстояние ноль, а расстояние симметрично. Перед использованием нужно выбрать признаки, шкалу и порог; без этого слово «похоже» не определяет отношение. Пересекающиеся блоки полезны, когда один объект уместен в нескольких группах попарно похожих объектов. При этом толерантность сама по себе не выбирает лучший порог и не доказывает, что объекты принадлежат одной реальной категории.
Допуск также зависит от способа измерения. Пусть значения описывают разницу яркости, а не одинаковые идентификаторы: изменение масштаба измерения без соответствующего изменения порога может изменить набор пар. Если данные включают несколько признаков, сначала выбирают функцию расстояния и приводят признаки к сопоставимым шкалам. Метрическое расстояние с неотрицательным порогом гарантирует рефлексивность и симметричность такого отношения, но даже неравенство треугольника гарантирует лишь расстояние между концами не больше суммы двух шагов. При двух шагах по единице эта граница равна двум, а не одному.
При пороге 2 в нашем инструменте уже связаны 0 и 2, но цепочка показывает оставшийся разрыв: её шаги имеют длины 1 и 2, а концы разделены расстоянием 3. Сдвиг порога добавляет связи и меняет блоки, поэтому результат надо интерпретировать вместе с выбранным порогом. Если же цель - разделить данные на непересекающиеся категории, потребуется дополнительное правило; само отношение попарной близости такого правила не задаёт.
Частые ошибки
- Требовать нарушения транзитивности. Толерантность может оказаться транзитивной: тогда это также эквивалентность.
- Принимать окрестность за блок. Все элементы окрестности связаны с её центром, но не обязательно друг с другом.
- Считать блоки непересекающимися. Общий элемент двух блоков не делает их одинаковыми.
- Забывать диагональные пары. Симметричности недостаточно: для толерантности каждый элемент должен быть связан с собой.
- Путать непосредственную близость с достижимостью. Цепочка связей может соединять элементы, которые сами не связаны.
FAQ
Любая ли эквивалентность является толерантностью?
Да. Рефлексивность и симметричность входят в определение эквивалентности; транзитивность не мешает быть толерантностью.
Можно ли получить блоки из окрестностей?
Не просто объявив каждую окрестность блоком: сначала нужно проверить попарную совместимость и максимальность по включению.
Почему при пороге 2 отношение всё ещё нетранзитивно?
На множестве связаны 0 и 1, а также 1 и 3, но 0 и 3 находятся на расстоянии 3 и не связаны.
Коротко
Отношение толерантности рефлексивно и симметрично; транзитивность для него не обязательна. Пороговая близость показывает, почему соседние связи могут образовать цепочку без связи между концами. Максимальные попарно совместимые блоки покрывают множество, но могут пересекаться, поэтому обращаться с ними как с классами эквивалентности нельзя.
Читайте также

Свойства бинарных отношений: рефлексивность, симметричность
Разбор трёх ключевых свойств бинарных отношений: рефлексивность, симметричность, транзитивность - определения, матрицы, графы и типы отношений с примерами и задачами.

Булев куб: вершины, рёбра и расстояние Хэмминга
Булев куб простыми словами: как двоичные наборы становятся вершинами, когда они соседствуют, сколько в кубе рёбер и как найти расстояние между вершинами.

Частично упорядоченное множество: примеры и диаграмма
Разбираем частично упорядоченное множество: свойства отношения, сравнимые элементы, диаграмму Хассе и отличие максимального элемента от наибольшего на примерах.

Доминирующее множество в графе: определение и примеры
Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

Исчисление предикатов: язык, формулы и правила вывода
Исчисление предикатов описывает свойства объектов и отношения между ними. Разбираем устройство формул, пошаговый пример доказательства и поиск контрмодели.