Фомин В.Л. Связанность и охват бинарных отношений

Материалы Всероссийской НПК «Право. Экономика. Общество» 1 апреля 2017 г.

Связанность и охват бинарных отношений

Connectivity and coverage of binary relations

 

Фомин Виктор Леонидович

Fomin Victor Leonidovich

Ст. преподаватель ВСФ ФГБОУВО РГУП, г. Иркутск

foislu@rambler.ru

 

Аннотация. В статье проводится систематизация свойств бинарных отношений «связанность» и «охват» на множестве в свете величинного подхода к их дефиниции. В анализе спектра значений свойства «связанность» автор придерживается единых позиций с рассмотрением аналогичного свойства орграфов. Проводимый анализ дает методологическое основание к компьютерному измерению рассматриваемых свойств бинарных отношений на дискретных множествах и орграфов.

Annotation. The article presents a systematization of the properties of binary relations «connectedness» and «coverage» on the set in the light approach to the property as the value to their definition. The spectrum analysis values of the properties «connectedness», the author adheres to the same position with the consideration of the similar properties of digraphs. The analysis provides a methodological Foundation to digital measurement of the considered properties of binary relations on discrete sets and digraphs.

Ключевые слова: бинарное отношение, орграф, связность отношения, связность графа, охват.

Keywords: a binary relation, digraph, connectivity relations, the connectivity of the graph, coverage.

 

В математической литературе большое внимание уделяется отношениям на множестве. В частности подробно рассматриваются свойства бинарных отношений (БО). Наиболее полным можно считать список свойств БО в справочнике И. Н. Бронштейна и К. А. Семендяева. [1] Автором настоящей статьи ранее была предпринята попытка систематизировать свойства БО в рамках величинного подхода [2] к дефиниции основных свойств БО — рефлексии, симметрии и транзитива.

Суть величинного подхода в том, что каждое свойство рассматривается как величина и может в конкретных случаях принимать то или иное значение. Например, свойству рефлексия, являющемуся величиной вербального (текстового) типа, соответствует спектр значений {«рефлексивно»; «антирефлексивно»; «полурефлексивно»}. [2] В настоящей работе нами в рамках величинного подхода исследуется спектр значений свойства связанность и вводится в рассмотрение еще одно свойство — охват.

Свойство связанность указывает на наличие связи отношением двух произвольно взятых элементов множества-носителя (условимся элементы  и  называть связанными по отношению ρ, если  или ).

В литературе рассматриваются свойства-признаки БО — связность (любые два различных элемента носителя связаны отношением) и несвязность в противном случае. Некоторые авторы (например, И. Н. Бронштейн и К. А. Семендяев) используют также свойство линейность, характеризующееся тем, любые два, не обязательно различных, элемента носителя связаны отношением. В рамках принятого нами величинного подхода эти свойства-признаки мы будем рассматривать как значения свойства связанность и будем обозначать эти значения словами «линейно», «связно» и «несвязно». А слова «линейность», «связность» и «несвязность» рассматривать как допустимый сниженный стиль высказываний.

Свойство связанность указывает на возможность разбиения (факторизации)  множества-носителя на классы по данному отношению. Связанные отношением элементы должны состоять в одном классе, и таким образом по связному отношению множество невозможно разбить.

Но множество не всегда разбивается отношением ρ и в случае несвязности последнего (точнее, когда связанность(ρ) ¹ «связно»). На рис. 1 показано отношение, которое не является связным, но множество не разбиваемо по этому отношению: в силу связи элементы x и y  должны быть в одном классе. В свою очередь элемент z связан с y, он должен быть том же классе. Таким образом, все элементы множества должны быть в одном классе.

 

Рис. 1 Рис. 2

 

На рис. 2 показано несвязное отношение. Проводя по нему разбиение носителя, мы выделяем подмножество  и одноэлементные классы  и . Возможно возражение о том, что разбиение проводится только по отношению ρ, являющемуся рефлексивным, симметричным и транзитивным (или строго выражаясь, если:

рефлексия(ρ) = «рефлексивно»,

симметрия(ρ) = «симметрично»,

транзитив(ρ) = «транзитивно».

Это замечание можно обойти, введением индуцированного отношения σ, обладающего всеми этими свойствами, и разбиением уже по нему.

Обратим также внимание на то, что в теории графов (ограничим их рассмотрение орграфами) также выделяются полные, сильно связные, связные и несвязные орграфы. Здесь термин «полный» соответствует термину «связное» для теории отношений. В сильно связном орграфе любые две вершины  взаимно достижимы, т. е. существует путь как из  в , так и обратный путь. В связном орграфе между любыми двумя вершинами существует путь хотя бы в одном направлении. В слабо связном орграфе — полупуть (последовательность вершин и ребер без учета направлений).  На несвязном орграфе выделяют компоненты связности, аналогичные классам разбиения.

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

{«линейно связно», «прямо связно», «сильно связно»,  «транзитно связно», «средно связно», «несвязно»}.

Характеристические условия значений в символической форме приводятся в таблице 1. В формулировках отношение обозначается символом ρ, а множество-носитель данного отношения — . Наличие пути от вершины  к вершине  (или транзитного отношения элемента  с элементом ) мы условимся указывать выражением . В целях достижения единственности значения связанности к основному условию (сформулированному в переменных , , )  даются конъюнктивные добавки в переменных , .

Таблица 1

Дефиниции значений связанности

Значение Характеризующие условия  
«линейно связно» (1.1)
«прямо связно» (1.2)
«сильно связно» (1.3)
«транзитно связно» (1.4)
«средно связно» (1.5)
«несвязно» (альтернативное значение) Не выполняется ни одно из условий (1.1-5) (1.6)

 

Введем в рассмотрение свойство охват, которое указывает, все ли элементы носителя участвуют в отношении. Элементы множества-носителя, не участвующие в отношении, мы будем называть изолированными элементами. Если множество содержит изолированные элементы, мы вправе предположить, что данные элементы не обладают вытекающим из данного отношения общим признаком (пусть пока еще не известным) — это объекты какой-то иной природы.

 

Рис. 3

 

На рис. 3 показано БО, по которому элементы  являются изолированными элементами, а элемент  — изолированным участником отношения. Разбиение дает классы: ,  и класс  — изолированное подмножество. Последнее несвязно, но данное отношение утрачивает свойство «быть основанием к разбиению».

Определим спектр значений свойства охват: {«всеохватно»; «охватно»; «неохватно»}.

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

Характеризующие условия для всех значений приведены в таблице 2. Здесь для однозначности свойства, подобно тому, как это сделано при дефинициях значений связанности, в условие (2.2) введена конъюнктивная добавка, сформулированная в переменных , .

 

Таблица 2

Дефиниции значений охвата

Значение Характеризующие условия  
«всеохватно» (2.1)
«охватно» (2.2)
«неохватно» Альтернативное значение (2.3)

 

Изложенная систематизация свойств БО придает теоретическую завершенность теме «Бинарные отношения». Удобство разграничения в рассуждениях понятий свойства и его значения проявляется, прежде всего, в достижении полноты исследования свойства — для любого отношения, заданного на множестве, оно приобретает какое-то значение и только одно.

Однозначность выявления значений свойств отношения, создает методическую основу компьютерного измерения свойства функции, аргументом которых должна служить матрица отношения (орграфа), представленная на рабочем листе электронной таблицы. Такие функции можно реализовать как функции, определяемые пользователем, на языке VBA для MS Excel.

Список источников

  1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов. / И.Н. Бронштейн, К.А. Семендяев; пер. с нем. — 2-е изд., перераб. — М., 1980.
  2. Фомин, В.Л. Величинный подход к дефиниции свойств бинарных отношений. // Современное общество и направления его развития : материалы Международной НПК (г. Ангарск, 24 марта, 2016 .) под общ. ред. Е. В. Барашевой [Текст] : Изд-во ИРНИТУ, 2016. — С. 97-100.

Добавить комментарий