EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#отношение толерантности#дискретная математика#бинарные отношения#отношение близости#блоки толерантности
Отношение толерантности: близость и пересекающиеся блоки

Два изображения могут отличаться совсем немного, второе и третье тоже похожи, но первое и третье уже различаются заметно. Такая близость не обязана передаваться по цепочке. В дискретной математике её удобно описать отношением толерантности: оно связывает каждый объект с самим собой и действует одинаково в обе стороны, но не требует транзитивности.

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

Близость как бинарное отношение

Пусть AA - множество объектов. Отношение T⊆A×AT \subseteq A\times A называют толерантностью на множестве, если оно рефлексивно и симметрично:

∀a∈A ⁣:aTa,∀a,b∈A ⁣:aTb⇒bTa.\forall a\in A\colon aTa, \qquad \forall a,b\in A\colon aTb\Rightarrow bTa.

Первое условие означает, что объект связан с собой; второе - что связь взаимна. При этом из aTbaTb и bTcbTc не обязательно следует aTcaTc. Слово «не обязательно» важно: транзитивные отношения тоже допускаются. Например, равенство одновременно является толерантностью и эквивалентностью.

Отношение состоит из упорядоченных пар, а не из самих объектов. Если a≠ba\ne b и aTbaTb, симметричность требует присутствия обеих пар (a,b)(a,b) и (b,a)(b,a). Чтобы разобраться с записью произведения множеств и пар, полезно вспомнить декартово произведение. В контексте алгебраических структур термин может дополнительно требовать совместимости отношения с операциями; здесь мы рассматриваем отношение на множестве без такого дополнительного условия.

Пример: порог расстояния

Возьмём A={0,1,2,3}A=\{0,1,2,3\} и определим aTbaTb условием ∣a−b∣≤1|a-b|\leq 1. Это учебная модель: числа могут обозначать значения признака, а единица - выбранный допуск. Каждое число отстоит от себя на ноль, а расстояние от aa до bb равно расстоянию от bb до aa. Следовательно, отношение рефлексивно и симметрично.

Движение ниже проходит по цепочке 0,1,20,1,2: каждый соседний шаг укладывается в допуск, но расстояние между крайними точками равно двум. Поэтому прямой связи концов нет. Это конкретное свидетельство отсутствия транзитивности, а не просто отсутствие какой-то пары.

Маркер проходит от 0 через 1 к 2 и обратно: соседние расстояния равны единице, а расстояние между крайними точками превышает допуск.

Например, (0,1)(0,1) и (1,2)(1,2) принадлежат TT, но (0,2)(0,2) не принадлежит TT. Здесь выполняются обе посылки транзитивности, а заключение нарушается. При другом пороге вывод может измениться: на этом конечном множестве при пороге 0 остаётся только равенство, а при пороге 3 связаны все пары. Оба крайних отношения транзитивны.

Как читать матрицу

В строке aa и столбце bb поставим единицу, когда aTbaTb, и ноль в противном случае. Для порога 1 получается:

MT=(1100111001110011).M_T=\begin{pmatrix} 1&1&0&0\\ 1&1&1&0\\ 0&1&1&1\\ 0&0&1&1 \end{pmatrix}.
Матрица пороговой близости для чисел от нуля до трёх: на диагонали и рядом с ней стоят единицы
Матрица пороговой близости для чисел от нуля до трёх: на диагонали и рядом с ней стоят единицы

Диагональ содержит четыре единицы: каждая подтверждает связь элемента с собой. Матрица симметрична относительно диагонали: например, клетки (0,1)(0,1) и (1,0)(1,0) одинаковы. Всего в ней десять единиц, то есть десять упорядоченных пар, включая четыре диагональные. Проверяя по инструменту другие пороги 0, 2 и 3, получим соответственно 4, 14 и 16 пар.

Чтобы найти нарушение транзитивности, ищите не отдельный ноль, а цепочку: в клетках (0,1)(0,1) и (1,2)(1,2) стоят единицы, тогда как в (0,2)(0,2) - ноль. Это удобно автоматизировать тремя циклами по элементам. О матричных признаках других отношений подробнее рассказано в статье про свойства бинарных отношений.

Окрестность и блок: разные объекты

Окрестность элемента aa - множество всех элементов, связанных с ним: T(a)={b∈A∣aTb}T(a)=\{b\in A\mid aTb\}. В примере T(1)={0,1,2}T(1)=\{0,1,2\}. Однако ноль и двойка между собой не связаны, поэтому внутри этой окрестности не все элементы попарно близки.

Назовём множество BB попарно совместимым, если B×B⊆TB\times B\subseteq T. Блок - такое множество, которое нельзя расширить включением ещё одного элемента из AA, сохранив попарную совместимость. Максимальность здесь понимается по включению: блок не обязан иметь наибольший размер среди всех возможных блоков.

Для нашего примера блоки равны {0,1}\{0,1\}, {1,2}\{1,2\} и {2,3}\{2,3\}. В каждой паре расстояние не больше единицы; добавить к любой паре ещё один элемент нельзя. Окрестность T(1)T(1) не является блоком, потому что содержит несовместимые 0 и 2. Эти определения и связь блоков с покрытиями рассмотрены в исследовании On the coverings by tolerance classes.

Почему блоки пересекаются

Блоки {0,1}\{0,1\} и {1,2}\{1,2\} пересекаются по элементу 1, но не совпадают. Близость к одному и тому же элементу не заставляет крайние элементы быть близкими друг другу. Все три блока вместе покрывают AA, однако не образуют разбиения, поскольку пересекаются.

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

Как найти блоки по шагам

Для небольшого конечного множества удобно начать с матрицы. Сначала проверьте диагональ и зеркальные клетки: если хотя бы одно из этих условий не выполнено, перед нами не толерантность и выводы о её блоках применять без оговорок нельзя. Затем выберите элемент и попробуйте присоединить к нему другой, сохраняя единицы для всех пар внутри полученного множества. Для третьего элемента нужно проверить его связь не только с первым, но и со вторым. Продолжайте, пока ни один оставшийся элемент нельзя добавить.

Например, начнём с единицы. Ноль можно добавить, но после этого двойку добавить нельзя: клетка (0,2)(0,2) равна нулю. Получаем блок {0,1}\{0,1\}. Если вместо нуля выбрать двойку, возникает другой блок {1,2}\{1,2\}; тройка к нему не добавляется из-за отсутствия связи с единицей. Начав с двойки и тройки, получим ещё {2,3}\{2,3\}. Чтобы убедиться в полноте списка, заметим: любые два числа, отличающиеся больше чем на единицу, несовместимы, а каждый одиночный элемент входит хотя бы в одну из перечисленных пар.

Один жадный проход не гарантирует полный список: выбор первого соседа влияет на результат. Для произвольной конечной матрицы можно перебрать подмножества, проверить попарные связи и оставить только не расширяемые. На больших множествах число подмножеств быстро растёт; используют алгоритмы перечисления максимальных клик, а размер данных и число самих блоков влияют на стоимость решения. Поэтому до вычислений полезно решить, нужны ли вообще все блоки или достаточно проверить один заданный кандидат.

Сравнение с эквивалентностью и применение

Отношение эквивалентности обладает теми же двумя свойствами и дополнительно транзитивно. Его классы либо совпадают, либо не пересекаются; у произвольной толерантности такое утверждение неверно. Если построить транзитивное замыкание нашего примера, цепочка 0,1,2,30,1,2,3 свяжет все четыре числа. Это даст эквивалентность, но добавит пары вроде (0,3)(0,3), не удовлетворяющие исходному порогу. Замыкание отвечает на вопрос о достижимости по цепочке, а не о прямой близости.

В задачах обработки данных пороговое отношение может описывать похожесть записей по выбранной метрике: одинаковая запись имеет расстояние ноль, а расстояние симметрично. Перед использованием нужно выбрать признаки, шкалу и порог; без этого слово «похоже» не определяет отношение. Пересекающиеся блоки полезны, когда один объект уместен в нескольких группах попарно похожих объектов. При этом толерантность сама по себе не выбирает лучший порог и не доказывает, что объекты принадлежат одной реальной категории.

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

При пороге 2 в нашем инструменте уже связаны 0 и 2, но цепочка 0,1,30,1,3 показывает оставшийся разрыв: её шаги имеют длины 1 и 2, а концы разделены расстоянием 3. Сдвиг порога добавляет связи и меняет блоки, поэтому результат надо интерпретировать вместе с выбранным порогом. Если же цель - разделить данные на непересекающиеся категории, потребуется дополнительное правило; само отношение попарной близости такого правила не задаёт.

Частые ошибки

  • Требовать нарушения транзитивности. Толерантность может оказаться транзитивной: тогда это также эквивалентность.
  • Принимать окрестность за блок. Все элементы окрестности связаны с её центром, но не обязательно друг с другом.
  • Считать блоки непересекающимися. Общий элемент двух блоков не делает их одинаковыми.
  • Забывать диагональные пары. Симметричности недостаточно: для толерантности каждый элемент должен быть связан с собой.
  • Путать непосредственную близость с достижимостью. Цепочка связей может соединять элементы, которые сами не связаны.

FAQ

Любая ли эквивалентность является толерантностью?
Да. Рефлексивность и симметричность входят в определение эквивалентности; транзитивность не мешает быть толерантностью.

Можно ли получить блоки из окрестностей?
Не просто объявив каждую окрестность блоком: сначала нужно проверить попарную совместимость и максимальность по включению.

Почему при пороге 2 отношение всё ещё нетранзитивно?
На множестве {0,1,2,3}\{0,1,2,3\} связаны 0 и 1, а также 1 и 3, но 0 и 3 находятся на расстоянии 3 и не связаны.

Коротко

Отношение толерантности рефлексивно и симметрично; транзитивность для него не обязательна. Пороговая близость показывает, почему соседние связи могут образовать цепочку без связи между концами. Максимальные попарно совместимые блоки покрывают множество, но могут пересекаться, поэтому обращаться с ними как с классами эквивалентности нельзя.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Свойства бинарных отношений: рефлексивность, симметричность

Свойства бинарных отношений: рефлексивность, симметричность

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

11 июня 202610 минут
Булев куб: вершины, рёбра и расстояние Хэмминга

Булев куб: вершины, рёбра и расстояние Хэмминга

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

8 ноября 20268 минут
Частично упорядоченное множество: примеры и диаграмма

Частично упорядоченное множество: примеры и диаграмма

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

8 ноября 20269 минут
Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

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

8 ноября 20268 минут
Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов: язык, формулы и правила вывода

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

8 ноября 20268 минут