О некоторых подграфах графа бинарных отношений тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Аль Джабри Халид Шиа Хайралла

  • Аль Джабри Халид Шиа Хайралла
  • кандидат науккандидат наук
  • 2016, ФГБУН Институт математики и механики им. Н.Н. Красовского Уральского отделения Российской академии наук
  • Специальность ВАК РФ01.01.06
  • Количество страниц 80
Аль Джабри Халид Шиа Хайралла. О некоторых подграфах графа бинарных отношений: дис. кандидат наук: 01.01.06 - Математическая логика, алгебра и теория чисел. ФГБУН Институт математики и механики им. Н.Н. Красовского Уральского отделения Российской академии наук. 2016. 80 с.

Оглавление диссертации кандидат наук Аль Джабри Халид Шиа Хайралла

Введение

Глава 1. Граф бинарных отношений

§ 1. Диаметр графа бинарных отношений

§ 2. Граф частичных порядков

§ 3. Опорные множества графа частичных порядков

Глава 2. Граф рефлексивно-транзитивных отношений

и граф конечных топологий

§ 4. Граф рефлексивно-транзитивных отношений

§ 5. Граф конечных топологий

Глава 3. Граф ациклических отношений (ациклических орграфов)

§ 6. Граф ациклических отношений

§ 7. Опорные множества графа ациклических отношений

Заключение

Литература

Обозначения

Рекомендованный список диссертаций по специальности «Математическая логика, алгебра и теория чисел», 01.01.06 шифр ВАК

Введение диссертации (часть автореферата) на тему «О некоторых подграфах графа бинарных отношений»

ВВЕДЕНИЕ

Задача перечисления конечных топологий, эквивалентная задаче перечисления транзитивных ориентированных графов, традиционно включается во все списки нерешенных задач перечисления графов. При этом отмечается, что вычисление числа T(n) всех помеченных топологий, которые можно ввести на фиксированном конечном множестве из n элементов, наталкивается на значительные трудности, — необходимое машинное время растет по экспоненте, что затрудняет вычисление значений T (n) даже при малых n.

Первые результаты в данном направлении представлены в работах следующих авторов: L. Comtet [7], V. Krishnamurthy [22], H. Sharp [28], M. Erne [10], S.K. Das [8] и др. В общей сложности были вычислены значения T (n) для всех n ^ 11. Параллельные исследования проводили [35-37,45] советские математики З.И. Боревич, В.И. Родионов, В.В. Бумагин и польские коллеги В. Венслав и Э. Добровольский (стало известно новое число T(12) ). Позднее в работе M. Erne и K. Stege [12] были вычислены значения T(13) и T(14). Благодаря разработке эффективных алгоритмов вычислений (авторы — G. Brinkmann и B.D. McKay, [5]) в настоящее время известны значения T (n) для всех n ^ 18.

Асимптотические свойства последовательности { T (n)} изучали следующие специалисты: M. Erne [10,11], D.J. Kleitman и B.L. Rothschild [19], S. Finch [15] и др. В работах З.И. Боревича [38,39] исследована периодичность вычетов числа конечных помеченных топологий.

Одним из направлений перечисления конечных топологий является исследование совокупности чисел {T0(n, k)}, где T0(n,k) — это количество T0 -топологий, определенных на множестве из n элементов и имеющих ровно k открытых множеств. Истоки этих исследований заложили H. Sharp [29] и R.P. Stanley [30]. Отметим некоторые работы современных авторов: M. Benoumhani, M. Kolli [3,4,20,21], K. Ragnarsson и B.E. Tenner [25], И.Г. Величко, П.Г. Стеганцева и Н.П. Башова [40]. В них исследуется рас-

пределение количества открытых множеств в диапазоне от n +1 до 2n.

Коллеги M. Erne [1З], G. Pfeiffer [24], G. Brinkmann и B.D. McKay [б] и ряд других авторов исследовали конечные непомеченные топологии (получение каких-либо точных перечислительных формул здесь является еще более сложной задачей по сравнению с помеченным случаем). Ряд ученых изучает группы автоморфизмов конечных топологий (в обзоре отметим лишь современную работу [1S], авторы — D. Kim, Y.S. Kwon и J. Lee).

В независимых работах В.И. Родионова [44] и M. Erne [11] получены соотношения рекуррентного характера между отдельными классами конечных топологий. Анализ этих соотношений привел к появлению основного объекта исследований диссертации — графа (2х2, E(X)) бинарных отношений («графа графов»). Через 2х2 обозначено множество вершин, состоящее из всех бинарных отношений множества X произвольной природы, а E(X) — это множество ребер, состоящее из неупорядоченных пар смежных бинарных отношений множества X. (Понятие смежности определяется в [48].)

К тематике исследований тесно примыкает родственная задача перечисления ациклических ориентированных графов того или иного частного вида. Решение задачи перечисления всех ациклических орграфов оказалось существенно проще, — математики R.W. Robinson [26], R.P. Stanley [З1], В.А. Лисковец [42] и В.И. Родионов [27] доказали ряд соотношений рекуррентного характера между отдельными классами ациклических орграфов, а В.И. Родионов получил формулу

An(x)= ^ (-1)n-k ( n ) (1+x )(n2-р2-...-р2V2.

pi + ...+Р2 =n pi,...,pk

(Суммирование ведется по всем упорядоченным наборам (p1,... ,pk) натуральных чисел таких, что p1 + ... + pk = n. ) Через

то

r

г=0

обозначена производящая функция (полином), в которой Апг — это количество помеченных ациклических графов порядка п, имеющих ровно г дуг.

Если An == An(1) и

^ A

A(t)=V An 2-(2) tn

^ n!

n=0

— хроматическая производящая функция, то согласно [31] справедливо

A(t)= [£ ^ 2-(2) tn]-1.

n=0 n!

Возможность применения производящих функций послужила основой новых исследований ациклических орграфов. Среди них отметим современные работы ученых: E.A. Bender, L.B. Richmond, R.W. Robinson и N.C. Wormald [1], E.A. Bender и R.W. Robinson [2], I.M. Gessel [16], R.P. Stanley [32], В.А. Лисковец [23], D. Dolzan и P. Oblak [9] и др.

Настоящая работа посвящена изучению графа графов ^ 2х, E(X)), содержащего различные семейства графов (не только транзитивные и ациклические). Таким образом, рассматриваемые в диссертации вопросы связаны с актуальными задачами теории графов.

Цель работы состоит в изучении основного объекта исследований — графа (2х , E(X)) и некоторых его подграфов, что предполагает детальное исследование отдельных классов бинарных отношений и их опорных множеств. (Понятие опорного множества определяется в [48, 53] как для транзитивных, так и для ациклических графов.) Еще одна задача — это получение новых перечислительных формул в теории графов.

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

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

является рефлексивно-транзитивным отношением, то и другое отношение — рефлексивно-транзитивное. Получена явная формула для числа связных компонент графа конечных топологий. Показано, что если одно из смежных отношений графа является ациклическим отношением, то и другое отношение — ациклическое. Получена явная формула для числа связных компонент графа ациклических отношений.

Работа носит теоретический характер. Ее результаты и методы могут быть использованы при дальнейшем изучении строения графа ( 2х2, E(X)). Наибольшие перспективы имеет исследование структурных свойств опорных множеств различных семейств бинарных отношений.

Основные результаты работы представлены на:

- XLI итоговой студенческой научной конференции (Ижевск, Удмуртский государственный университет, 2013);

- 45-й Международной молодежной школе-конференции «Современные проблемы математики и её приложений» (Екатеринбург, Институт математики и механики УрО РАН, Уральский федеральный университет, 2014);

- Всероссийской конференции с международным участием «Теория управления и математическое моделирование» (Ижевск, Удмуртский государственный университет, 2015);

- Российской научной конференции «Алгебра, анализ и смежные вопросы математического моделирования» (Владикавказ, Северо-Осетинский государственный университет, 2015);

- International Conference «Groups and graphs, algorithms and automata» (Yekaterinburg, Ural federal university, IMM UB RAS, IM SB RAS, 2015).

По теме диссертации опубликовано 8 печатных работ, из них 3 — в ведущих научных журналах, рекомендованных ВАК, 3 — в материалах международных и всероссийских конференций (РИНЦ).

В списке литературы, приведенном в конце работы, содержатся известные автору работы, в которых рассматриваются конечные топологии и ациклические графы в аспектах, близких к теме диссертации.

Приступим к краткому изложению содержания диссертации.

В главе I на множестве всех бинарных отношений произвольного множества X вводится бинарное рефлексивное отношение смежности и определяется основной объект исследований — граф бинарных отношений.

Первый параграф носит подготовительный характер и посвящен нахождению диаметра графа бинарных отношений. Пусть В = {0,1} — булево множество, X — произвольное множество, а X2 = X х X — прямое произведение. Функции X2 ^ В будем называть характеристическими. Всякое подмножество а С X2, называемое бинарным отношением (или просто отношением) на множестве X, порождает характеристическую функцию

ХЛ2 о ( А 1 1 если (Х,У) £

Ха : ^ ^ В Ха (Х,У)= <

I 0, если (ж, у) £ а.

Далее функцию ха(•, •) будем обозначать через а (•, •). С другой стороны, всякая характеристическая функция Х : X2 ^ В порождает бинарное отношение ах С X2 такое, что (ж, у) £ ах, если х(ж,у) = 1. Отображение а ^ а (•, •) является биекцией между множеством бинарных отношений и множеством характеристических функций. В силу этого обстоятельства мы называем а как отношением, так и функцией.

Определение 1. Пусть X = У и 2 — дизъюнктное объединение двух подмножеств (допускается, что У = 0 или 2 = 0). Предположим, что отношение а С X2 таково, что а(ж,у) = 0 для всех (ж, у) £ У х 2. Оно порождает отношение т С X2 такое, что

т(ж, у) = 1 — а(у,ж) для всех (ж, у) £ У х 2, т(ж, у) = 0 для всех (ж, у) £ 2 х У, т(ж, у) = а(ж,у) для всех (ж, у) £ У2 и 22.

Отношение т называется смежным с отношением а.

Из определения следует, что если т смежно с а, то и а смежно с т,

и этот факт мы записываем в виде диаграммы а

YxZ

т. Например,

10 0 0 0 10 0 1111 110 1

{1}х{2,3,4} <->

110 0 0 10 0 0111 0101

{2,4}х{1,3} <->

1000 0100 0010 1101

{2,3}х{1,4} <->

1000 110 0 1011 1001

(1)

Таким образом, X порождает пару (2х 2 ,Е (X)), где через 2х обозначено множество вершин, состоящее из всех бинарных отношений множества X, а Е(X) — это множество ребер, состоящее из неупорядоченных пар смежных бинарных отношений множества X (так как допускается, что У = 0, то Е(X) содержит все петли). Пару С^) = ( 2х2, Е(X)) будем называть (неориентированным) графом бинарных отношений множества X.

Через Са(X) будем обозначать ту компоненту связности графа С^),

х2

которая содержит данное отношение а £ 2х .

Лемма 1. Для любых двух несмежных отношений а', а" £ Са(X) графа (2х2, Е(X)) существует отношение т £ Са(X) такое, что У 'х £' У "х £ "

/

а

т

//

а ,

У' х Z' = 0, У'' х Z'' = 0.

Следовательно, справедлива

Теорема 1. Если card X = 1, то диаметр графа G(X) равен 2.

Замечание 1. В силу леммы 1 в любой компоненте связности графа G(X) любые два отношения либо смежны, либо инцидентны некоторому третьему отношению. Условие несмежности отношений существенно. Например, в компоненте 1I <—> 11 <—> |J01 графа G({ 1, 2 }) первые два

отношения смежны, но не инцидентны одновременно третьему отношению.

В § 2 определяется граф частичных порядков. Пусть Уо^) — это совокупность всех частичных порядков, определенных на множестве X.

Теорема 2. Пусть отношения а и т смежны. Включение а £ Уо^) имеет место тогда и только тогда, когда т £ Уо^).

Таким образом, множество Уо(Х) порождает подграф ),Е(X)

графа С(Х). Будем называть его графом частичных порядков.

Отношение а £ ^о(Х) и элемент х £ X порождают множества = 1х(а) = { у £ X: а(х, у) = 1, а(у,х) = 0 }, К = Кх(а) = { у £ X: а(х, у) = а(у, х) = ^ }, 4 = Лх(а) = { у £ X: а(х, у) = 0, а(у, х) = 1 }.

Лемма 2. Справедливы равенства:

1) а(у, г) = 1 для всех (у, г) £ х 1х,

2) а(у, г) = 0 для всех (у, г) £ х [ и </х],

3) а(у, г) = 0 для всех (у, г) £ [ и х </х.

В силу леммы 2 определена последовательность

а <-► а' <-► ах (2)

смежных частичных порядков, которая порождает такой частичный порядок ах £ ^о^), что ах(х,у) = ах(у,х) = для всех у £ X. Таким образом, для фиксированного частичного порядка а £ ) определено отображение X —> (X), сопоставляющее элементу х £ X частичный порядок ах £ (X) (может оказаться, что ах = ау при х = у ). Заметим также, что это отображение определено однозначно, — в алгоритме (2) используются однозначно определенные множества 1х(а), Кх(а), 4х(а).

Лемма 3. Пусть частичные порядки а, т принадлежат одной и той же компоненте связности графа ). Тогда ах = тх для любого х £ X.

Как следствие, справедливо следующее утверждение: в каждой компоненте связности (X) графа частичных порядков (И^),Е(X)) для любого х £ X существует единственный частичный порядок т такой, что т(х,у) = т(у,х) = при всех у £ X, причем т = ах.

Замечание 2. Зафиксируем х £ X. В компоненте (X) существует единственный частичный порядок ах такой, что ах(х,у) = ах(у,х) =

при всех y Е X, поэтому компоненте Ga (X) можно взаимно-однозначно сопоставить частичный порядок ах, определенный на множестве X \{ x }, такой, что ax(y, z) = ax(y, z) для всех y, z Е X \ { x }.

Если cardX < то (можно считать, что X = {1,...,n} — отрезок натурального ряда), то существует взаимно-однозначное соответствие между множеством V0(X) и множеством всех помеченных транзитивных орграфов, определенных на X (см., например, [43, с. 28]); в свою очередь, существует взаимно-однозначное соответствие между этим множеством и множеством всех помеченных To -топологий, определенных на X (см., например, [46, с. 256]). Обозначим через T0(n) число таких топологий (в частности, card V0(X) = T0(n)). Следовательно, в силу замечания 2 справедлива

Теорема 3. Если n ^ 2 и X = { 1,...,n}, то количество компонент связности графа (V0(X),E(X)) равно T0(n — 1).

В § 3 вводится понятие опорного множества и исследованы его свойства: совокупность

S(а) = { y Е X: а(х, y) = 5xy для всех x Е X }

называется опорным множеством частичного порядка а Е V0(X). Опорные множества частичных порядков из диаграммы (1) равны {3}, {1,3}, {3,4}, {2,3} соответственно. Согласно [42] справедливо утверждение:

если card X < то и а Е V0(X), то S (а) = 0.

Если S(а)= X, то а называется тривиальным частичным порядком.

Лемма 4. Пусть cardX < то. Для любого нетривиального частичного порядка а Е V0(X) и для любого y Е X \ S(а) существует х Е S(а) такое, что а(x,y) = 1.

Лемма 5. Пусть cardX < то, а частичные порядки а и т принадлежат одной и той же компоненте связности графа (V0(X),E(X)). Равенство S(а) = S(т) имеет место тогда и только тогда, когда а = т.

Предложение 1. Пусть cardX < то. Для любого а Е V0(X) и для любого непустого подмножества S С S(а) существует единственное т Е (X) такое, что S(т) = S, причем т смежно с а.

Предложение 2. Пусть card X < то. В любой компоненте связности (X) графа (V0(X),E(X)) для любого непустого подмножества S С X, состоящего не более, чем из двух элементов, существует единственный частичный порядок т такой, что S(т) = S.

Замечание 3. Пусть S(Ga) = { S(т) С X : т Е (X) } — совокупность всех опорных множеств частичных порядков, принадлежащих компоненте (X). В силу предложений 1-2 справедливо: 1) 0 Е S(G); 2) если 0 = а С в С X и в Е S(GCT), то а Е S(G); 3) если а С X и | а | < 2, то а Е S). Другими словами, совокупность S(Ga) является частично упорядоченным множеством относительно естественного отношения включения множеств со следующей спецификой: 1) вместе с каждым элементом множество S) содержит все его непустые подмножества; 2) S(Ga) содержит все одно- и двухэлементные подмножества множества X. Таким образом, для описания частично упорядоченного множества S(Ga) достаточно указать все его максимальные элементы.

Замечание 4. Пусть card X = n. Из теоремы 3 и предложения 2 следует, что в множестве V0(X) имеется в точности: 1) nT0(n — 1) различных частичных порядков, опорное множество которых содержит ровно один элемент; 2) 2 n (n — 1) T0(n — 1) различных частичных порядков, опорное множество которых содержит ровно два элемента. Следовательно, имеет место утверждение, доказанное ранее в независимых работах [11,44]: для любого n ^ 2 справедливо равенство

To(n) = 1 n (n+1) To(n — 1) + card { аЕ Vo({1,... ,n }): | S(а)| ^ 3 }.

Вторая глава состоит из двух параграфов, посвященных рефлексивно-транзитивным отношениям и конечным топологиям. В § 4 исследуется граф

рефлексивно-транзитивных отношений. Через V(X) обозначим совокупность всех рефлексивно-транзитивных отношений, определенных на множестве X. (Другими словами, отношения удовлетворяют аксиомам рефлексивности и транзитивности.) Для любых а £ V(X) и х £ X справедливо

иа(х) = { у £X: а(х, у) = 1 } = 0.

Предложение 3. Пусть а £ V(X), х,у £ X. Включение у £ иа(х) имеет место тогда и только тогда, когда иа (у) С иа (х).

Отношение а £ V(X) порождает на множестве X отношение эквивалентности: пишем х ~ у тогда и только тогда, когда иа(х) = иа(у). Класс эквивалентности, содержащий элемент х £ X, обозначаем [х]а (или х).

Предложение 4. Пусть а £ V(X) и х,у £ X. Тогда

1) [х]а С иа(х);

2) если у £ иа(х), то [у]а С иа(х); поэтому иа(х) = У ;

сиа (х)

3) а(£,п) = 1 для всех (£,п) £ [х]^;

4) а(£, п) = а(х, у) для всех (£,п) £ [х]а х [у]а;

5) если [х]а = [у]а, то а(£,п) а(п,^) = 0 для всех (£,п) £ [х]а х [у]а.

Теорема 4. Пусть отношения а и т смежны. Включение а £ V(X) имеет место тогда и только тогда, когда т £ V(X).

Таким образом, множество V(X) порождает подграф (V(X),Е(X) графа С^) (граф рефлексивно-транзитивных отношений).

Пусть а £ V(X). Через [X]а обозначим совокупность всех классов эквивалентности множества X. В силу предложения 4 определена характеристическая функция а: [X^ В такая, что а (х, у) = а(^,п), где (^,п) — произвольная пара из прямого произведения х х у. Показано, что а (как бинарное отношение) — это частичный порядок на множестве [X]а. Следовательно, а порождает граф С0) = (Vo([X]а),Е)). Таким образом, а £ ^(И^) и определена компонента связности графа С^^^), содержащая частичный порядок а (обозначим ее Сд)).

Предложение 5. Если а и т — смежные рефлексивно-транзитивные отношения, определенные на множестве X, то [X]а = [X]т.

Предложение 6. Пусть рефлексивно-транзитивные отношения а и т определены на множестве X, а а и т — это порожденные ими частичные порядки, определенные на множествах [X]а и [X]T соответственно. Отношения а и т смежны тогда и только тогда, когда смежны отношения а и т.

Предложение 7. Для любого рефлексивно-транзитивного отношения а Е V(X) связные графы Gq(X) и GQ([X]q) изоморфны.

В § 5 исследуется граф конечных топологий.

Отношение а Е V(X) называем конечным, если card [X]q < то. Совокупность всех таких отношений обозначим через W (X).

Через T(X) обозначим совокупность всех конечных топологий, определенных на множестве X. Для любых T Е T (X) и x Е X существует наименьшее открытое множество ST (x), содержащее x. Топология T Е T(X) порождает функцию а : X 2-> B такую, что а(х, у) = 1, если у Е ST (x), а иначе а(x,y) = 0. Она является характеристической функцией для некоторого рефлексивно-транзитивного отношения. Более того, а Е W(X).

Предложение 8. Отображение Ф: T(X) ^ W (X) биективно.

Если cardX < то, то всякая топология T, заданная на X, конечна, то есть T Е T(X). Для любого а Е V(X) справедливо card [X]q < то, поэтому а Е W(X). Значит, W(X) = V(X) и 1тФ = V(X).

В силу биекции Ф-1: V(X) ^ T(X) можно считать, что вершинами графа (V(X),E(X)) являются конечные топологии (элементы множества T(X)). При этом можно говорить, что топологии T, T' Е T(X) смежны, если смежны отношения Ф^), Ф(^) Е V(X). Можно также говорить, что (T(X),E(X)) — это граф конечных топологий.

Теорема 5. Если X = { 1,..., n }, то ( [7,14,17])

n

card T(X) = ^ S(n,m) To(m),

m=1

а количество компонент связности графа (T(X),E(X)) равно

n

^ S(n,m)To(m-1),

m=1

где S(n,m) — это числа Стирлинга 2-го рода.

В главе III исследованы ациклические отношения (ациклические ориентированные графы), заданные на конечном множестве X = { 1,...,n}. Отношение а Е 2х2 называем ациклическим, если:

1) а(х,х) = 0 для всех x Е X;

2) для всех m > 1 и для всех (x1,..., xm) Е Xm имеет место равенство

m

a(xm,Х1)П a(xk-i,Xk) = 0. k=2

В § 6 определен граф ациклических отношений и некоторые его атрибуты. Семейство ациклических отношений обозначим через A(X). Легко установить взаимно-однозначное соответствие между множеством A(X) и множеством всех ациклических орграфов, определенных на X. Следовательно, справедливо утверждение: для любого а Е A(X) множество

S(а) = { у Е X: а(х, у) = 0 для всех x Е X }

не пусто [42]. Мы называем множества S(а) опорными (как в первой главе). Если в диаграмме (1) у всех отношений поменять диагональные элементы с 1 на 0, то получатся ациклические отношения, опорные множества которых равны {3}, {1,3}, {3,4}, {2,3} соответственно.

Очевидно, всякий подграф ациклического орграфа является ациклическим, следовательно, имеет место утверждение:

если а Е A(X) и 0 = Y С X, то a|Y2 е A(Y) и S(a|Y2) = 0.

(Через а|рхд мы обозначаем сужение функции а на прямоугольник Рх^ Всякое отношение а Е А(Х) порождает два семейства множеств:

X0 = X,

Хк = 5 (а|х к-1хх к-!) = 0, Xк = Хк-1\Хк, к = 1,...,р. Разбиение (Х1,...,Хр) таково, что Х1 = 5(а), справедливо представление

а =

0 *

0 0 *

*

0 0 *

0 0 0 0

Х1

Х2

ХР

Х1 Х2

. .. Хр

(символ * означает, что в блоке Хк-1 х Хк, к = 2,... ,р, в каждом столбце имеется хотя бы одна единица, а символ 0 означает, что блок состоит целиком из нулей) и определены отношения ак Е 2х2, к = 1,... ,р,

Ук х^

к1

а

ак, где Ук =и X*, ^ = У X,,

з=1

*=к

причем все отношения ак, ат, к, т = 1,... ,р, к = т, смежны и различны.

Теорема 6. Пусть отношения а и т смежны. Включение а Е А^) имеет место тогда и только тогда, когда т Е А^).

Таким образом, множество А^) порождает подграф ( А^),Е(X) графа С^.) Будем называть его графом ациклических отношений (или графом ациклических орграфов).

Лемма 6. Пусть X = {1,..., п}, п > 2. Для любых двух отношений а/,а// Е (X) графа (А^),Е(X)) существует отношение т Е (X) такое, что

у 'х ^' У "х z "

т

а'',

У' х = 0, У" х = 0.

Если в диаграмме (1) у всех отношений поменять диагональные элементы с 1 на 0, то получатся ациклические отношения. Для крайних отношений имеется отношение, инцидентное им обоим:

0 0 0 0 I 0 0 0 0 I I 0 0 0 0 0 0 0 0 {1,2}х{3,4} 0 0 0 0 {2,3,4}х{1} 10 00 1101 * * 0001 * * 1001 •

1 1 0 0 I 0 0 0 0 I I 1 0 0 0

В § 7 доказаны утверждения об опорных множествах и получена явная формула для числа компонент связности графа ациклических отношений.

Лемма 7. Пусть отношения а и т принадлежат одной и той же компоненте связности графа (А(Х ),Е (X)). Равенство Б (а) = Б (т) имеет место тогда и только тогда, когда а = т.

В силу теоремы 6 справедливо ак Е А(Х), поэтому определены опорные множества Б(ак), к = 1,... ,р.

Предложение 9. Для любого к = 1,... ,р справедливы включения

Хк С Б (ак) С Б (а) и Хк.

Предложение 10. Для любого а Е А(Х) и для любого непустого подмножества Б С Б (а) существует единственное т Е Оа (X) такое, что Б(т) = Б, причем т смежно с а.

В силу этих предложений и леммы 7 справедливо

Предложение 11. Для любого а Е А(Х) и для любого х Е X существует единственное отношение т Е Оа(X) такое, что Б(т) = { х }.

Через Б) = { Б(т) С X: т Е Са(X) } обозначим совокупность всех опорных множеств ациклических отношений, принадлежащих компоненте Оа(X). В силу предложений 10-11 справедливо: 1) 0 Е Б); 2) если 0 = а С в С X и в Е Б), то а Е Б); 3) если а С X и | а | = 1, то

а Е S). Другими словами, совокупность S(G) является частично упорядоченным множеством относительно естественного отношения включения множеств со следующей спецификой: 1) вместе с каждым элементом множество S) содержит все его непустые подмножества; 2) S(Ga) содержит все одноэлементные подмножества множества X. Таким образом, для описания частично упорядоченного множества S(Ga) достаточно указать все его максимальные элементы. Заметим еще, что в соответствии с замечанием 3 в аналогичной совокупности S(Ga) (определенной для частичных порядков) в обязательном порядке содержатся все двухэлементные подмножества.

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

В соответствии с предложением 11 каждой компоненте (X) графа (A(X),E(X)) соответствует единственное т Е A(X) такое, что S(т) = {1}. Значит, количество связных компонент графа равно card A(1) (X), где

A(v)(X) = { а Е A(X): S(a) = { 1,..., v } }, v = 1,...,n.

Лемма 8. Для любых n Е N и v = 1,... ,n справедливо равенство card A(v)(X)= V (-1)n+1-v-k f n -v \ 2(^-...-PkV2,

где суммирование ведется по всем упорядоченным наборам (p1,... ,pk) натуральных чисел таких, что p1 + ... + pk = n и v ^ p1.

Теорема 7. Если X = { 1,..., n}, то ( [27])

n

V p1,.

Pl + ...+Pfc =n

а количество компонент связности графа (A(X),E(X)) равно

card A(1)(X) = V (-1)n-k f П -1 ) 2(n2-P2-...-P2k)/2.

^ \P1- 1, .....Pk/

card A(X )= ^ (-1)n-k ( П )2 (n2-p1-...-p2)/2,

ГЛАВА I. ГРАФ БИНАРНЫХ ОТНОШЕНИЙ

В настоящей главе на множестве всех бинарных отношений произвольного множества X вводится бинарное рефлексивное отношение смежности и определяется основной объект исследований — граф бинарных отношений («граф графов»). Первый параграф носит подготовительный характер: определяется отношение смежности бинарных отношений и излагаются основные понятия, конструкции и обозначения. В параграфе доказано, что диаметр нетривиального графа бинарных отношений равен 2. В § 2 определяется граф частичных порядков — подграф графа бинарных отношений. Если cardX = n < то, то существует взаимно-однозначное соответствие между множеством всех частичных порядков и множеством всех помеченных транзитивных ориентированных графов, определенных на X, в свою очередь, существует взаимно-однозначное соответствие между этим множеством и множеством всех помеченных T0 -топологий, определенных на X. Если To(n) — число таких топологий, то число связных компонент графа частичных порядков равно T0(n — 1). В § 3 вводится понятие опорного множества частичного порядка и исследованы структурные свойства совокупности опорных множеств частичных порядков связной компоненты графа.

§ 1 . Диаметр графа бинарных отношений

Пусть B = { 0,1 } — булево множество, X — произвольное множество, а X2 = X х X — прямое произведение. Функции X2 ^ B будем называть характеристическими. Всякое подмножество а С X2, называемое бинарным отношением (или просто отношением) на множестве X, порождает характеристическую функцию

хл2 D ( A J 1 если (Х,У) Е

Ха : X ^ B Ха (x,y) = <

I 0, если (x,y) Е а.

Далее функцию ха(•, •) будем обозначать через а(-, •). С другой стороны, всякая характеристическая функция Х : X2 ^ B порождает бинарное отношение ах С X2 такое, что (x,y) Е ах, если x(x,y) = 1. Очевидно,

отображение а ^ а(-, •) является биекцией между множеством бинарных отношений и множеством характеристических функций. В силу этого обстоятельства мы называем а как отношением, так и функцией.

Определение 1. Пусть X = У и 2 — дизъюнктное объединение двух подмножеств (допускается, что У = 0 или 2 = 0). Предположим, что отношение а С X2 таково, что а(ж,у) = 0 для всех (ж, у) Е У х 2. Оно порождает отношение т С X2 такое, что

т(ж, у) = 1 — а(у,ж) для всех (ж, у) Е У х 2, т(ж, у) = 0 для всех (ж, у) Е 2 х У, т(ж, у) = а(ж,у) для всех (ж, у) Е У2 и 22. Отношение т называется смежным с отношением а.

Из определения следует, что если т смежно с а, то и а смежно с т, и этот факт мы записываем в виде диаграммы а < У — > т. Например, X = { 1,..., 6 }, У = { 1, 2 }, 2 = { 3, 4, 5, 6 },

1 0 п

0 1 и

0 0 10 10

1 0 1110

00 0010

11 0 0 0 1

У х^ <->

10 01 10 10 1110

и 10 10 1110 0010 0 0 0 1

(См. также диаграмму (1).) Применяя обозначение а|рдля сужения функции а на прямоугольник Р х получаем блочное представление

а|у 2 0

аЬ2

У

= а т =

т |у 2

0 т и 2

У 2

У 2 У 2

Так как а(ж,у) = 0 для всех (ж, у) Е У х 2, то в блоке У х 2 записан

«обобщенный» ноль (аналогично в блоке 2 х У отношения т). В остальных блоках значения неизвестны, и там мы поступаем следующим образом. Берем за основу, например, отношение а и проставляем в его блоках условный символ г; так как т|у2 = а|у2 и т= а|^2, то в диагональных блоках отношения т тоже пишем символ г; наконец, в блоке У х 2 отношения т пишем

Похожие диссертационные работы по специальности «Математическая логика, алгебра и теория чисел», 01.01.06 шифр ВАК

Список литературы диссертационного исследования кандидат наук Аль Джабри Халид Шиа Хайралла, 2016 год

ЛИТЕРАТУРА

[1] Bender E.A., Richmond L.B., Robinson R.W., Wormald N.C. The asymptotic number of acyclic digraphs, I // Combinatorica. 1986. Vol. 6. № 1. P. 15-22.

[2] Bender E.A., Robinson R.W. The asymptotic number of acyclic digraphs, II // Journal of Combinatorial Theory. Series B. 1988. Vol. 44. № 3. P. 363-369.

[3] Benoumhani M. The number of topologies on a finite set // Journal of Integer Sequences. 2006. Vol. 9. Article 06.2.6.

[4] Benoumhani M., Kolli M. Finite topologies and partitions // Journal of Integer Sequences. 2010. Vol. 13. Article 10.3.5.

[5] Brinkmann G., McKay B.D. Posets on up to 16 points // Order. 2002. Vol. 19. № 2. P. 147-179.

[6] Brinkmann G., McKay B.D. Counting unlabelled topologies and transitive relations // Journal of Integer Sequences. 2005. Vol. 8. Article 05.2.1.

[7] Comtet L. Recouvrements, bases de filtre et topologies d'un ensemble fini // C. R. Acad. Sci. 1966. Vol. AB262. P. A1091-A1094.

[8] Das S.K. A machine representation of finite T0 topologies //J. Assoc. Comput. Mach. 1977. Vol. 24. № 4. P. 676-692.

[9] Dolzan D., Oblak P. Invertible and nilpotent matrices over antirings // arXiv: 0806.2996v2 [math.AC]. 2008. http://arxiv.org/pdf/0806.2996.pdf

[10] Erne M. Struktur- und anzahlformeln fur topologien auf endlichen mengen // Manuscripta Math. 1974. Vol. 11. P. 221-259.

[11] Erne M. On the cardinalities of finite topologies and the number of antichains in partially ordered sets // Discrete Mathematics. 1981. Vol. 35. P. 119-133.

[12] Erne M., Stege K. Counting finite posets and topologies // Order. 1991. Vol. 8. № 3. P. 247-265.

[13] Erne M. The number of partially ordered sets with more points than incomparable pairs // Discrete Mathematics. 1992. Vol. 105. P. 49-60.

15

16

17

18

19

20

21

22

23

24

25

Evans J.W., Harary F., Lynn M.S. On the computer enumeration of finite topologies // Comm. ACM. 1967. Vol. 10. P. 295-297. Finch S. Transitive relations, topologies and partial orders // 2003. Published electronically at http://algo.inria.fr/csolve/posets.pdf Gessel I.M. Counting acyclic digraphs by sources and sinks // Discrete Mathematics. 1996. Vol. 160. P. 253-258.

Gupta H. Number of topologies on a finite set // Res. Bull. Panjab. Univ. (N.S.). 1968. Vol. 19. P. 231-241.

Kim D., Kwon Y.S., Lee J. Enumerations of finite topologies associated with a finite graph // Kyungpook Math. J. 2012.

http://dx.doi.org/10.5666/KMJ.0000.00.0.1

Kleitman D.J., Rothschild B.L. Asymptotic enumeration of partial orders on a finite set // Trans. Amer. Math. Soc. 1975. Vol. 205. P. 205-220. Kolli M. Direct and elementary approach to enumerate topologies on a finite set // Journal of Integer Sequences. 2007. Vol. 10. Article 07.3.1. Kolli M. On the cardinality of the T0 topologies on a finite set // International Journal of Combinatorics. 2014. Vol. 2014. Article ID 798074, 7 pages. http://dx.doi.org/10.1155/2014/798074

Krishnamurthy V. On the number of topologies on a finite set // Amer. Math. Monthly. 1966. Vol. 73. № 2. P. 154-157.

Liskovets V.A. More on counting acyclic digraphs // arXiv: 0804.2496v1 [math.CO]. 2008. http://arxiv.org/pdf/0804.2496.pdf

Pfeiffer G. Counting transitive relations // Journal of Integer Sequences. 2004. Vol. 7. Article 04.3.2.

Ragnarsson K., Tenner B.E. Obtainable sizes of topologies on finite sets // Journal of Combinatorial Theory. Series A. 2010. Vol. 117. P. 138-151. Robinson R.W. Counting labeled acyclic digraphs // New directions in the theory of graphs: Proc. Third Ann Arbor Conference on Graph Theory / New York: Academic Press, 1971. P. 239-273.

[27] Rodionov V.I. On the number of labeled acyclic digraphs // Discrete Mathematics. 1992. Vol. 105. P. 319-321.

[28] Sharp H., Jr. Quasi-orderings and topologies on finite sets // Proc. Amer. Math. Soc. 1966. Vol. 17. № 6. P. 1344-1349.

[29] Sharp H., Jr. Cardinality of finite topologies // Journal of Combinatorial Theory. 1968. Vol. 5. P. 82-86.

[30] Stanley R.P. On the number of open sets of finite topologies // Journal of Combinatorial Theory. Series A. 1971. Vol. 10. P. 74-79.

[31] Stanley R.P. Acyclic orientations of graphs // Discrete Mathematics. 1973. Vol. 5. P. 171-178.

[32] Stanley R.P. Acyclic orientations of graphs // Discrete Mathematics. 2006. Vol. 306. № 10-11. P. 905-909.

[33] Айгнер М. Комбинаторная теория. М.: Мир, 1982. 558 c.

[34] Биркгоф Г. Теория решеток. М.: Наука, 1984. 568 c.

[35] Боревич З.И. К вопросу перечисления конечных топологий // Зап. на-учн. сем. ЛОМИ. 1977. Т. 71. С. 47-65.

[36] Боревич З.И., Венслав В., Добровольский Э., Родионов В.И. Число помеченных топологий на девяти точках // Зап. научн. сем. ЛОМИ. 1978. Т. 75. С. 35-44.

[37] Боревич З.И., Бумагин В.В., Родионов В.И. Число помеченных топологий на десяти точках // Зап. научн. сем. ЛОМИ. 1979. Т. 86. С. 5-10.

[38] Боревич З.И. О периодичности вычетов числа конечных помеченных топологий // Зап. научн. сем. ЛОМИ. 1980. Т. 103. С. 5-12.

[39] Боревич З.И. О периодичности вычетов числа конечных помеченных T0-топологий // Зап. научн. сем. ЛОМИ. 1982. Т. 114. С. 32-36.

[40] Величко И.Г., Стеганцева П.Г., Башова Н.П. Перечисление топологий близких к дискретной на конечных множествах // Известия вузов. Математика. 2015. № 11. С. 23-31.

[41] Зыков А.А. Основы теории графов. М.: Наука, 1987. 384 c.

[42] Лисковец В.А. О числе максимальных вершин случайного ациклического орграфа // ТВП. 1975. Т. 20. Вып. 2. С. 412-420.

[43] Оре О. Теория графов. М.: Наука, 1980. 336 с.

[44] Родионов В.И. Об одном соотношении в конечных топологиях // Зап. научн. сем. ЛОМИ. 1980. Т. 103. С. 114-116.

[45] Родионов В.И. О некоторых рекуррентных соотношениях в конечных топологиях // Зап. научн. сем. ЛОМИ. 1982. Т. 114. С. 174-179.

[46] Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.

ПУБЛИКАЦИИ АВТОРА

[47] Аль Джабри Х.Ш. Граф частичных порядков, определенных на счетном множестве // ХЫ итоговая студ. научн. конф.: материалы конф. / Удмуртский гос. ун-т. Ижевск, 2013. С. 19-21.

[48] Аль Джабри Х.Ш., Родионов В.И. Граф частичных порядков // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 4. С. 3-12.

[49] Аль Джабри Х.Ш., Родионов В.И. О графе частичных порядков // Современные проблемы математики и её приложений: тр. 45-й Междунар. молод. шк.-конф. / Ин-т математики и механики УрО РАН, Урал. фед. ун-т. Екатеринбург, 2014. С. 3-6.

[50] Аль Джабри Х.Ш. Граф рефлексивно-транзитивных отношений и граф конечных топологий // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2015. Т. 25. Вып. 1. С. 3-11.

[51] Аль Джабри Х.Ш. О графе рефлексивно-транзитивных отношений // Теория управления и математическое моделирование: тез. докладов Всероссийской конф. с межд. участием / Удмуртский гос. ун-т. Ижевск, 2015. С. 325-326.

[52] Аль Джабри Х.Ш., Родионов В.И. О подграфах графа бинарных отношений // Алгебра, анализ и смежные вопросы математического модели-

рования: тез. докладов Российской научн. конф. / Северо-Осетинский гос. ун-т. Владикавказ, 2015. С. 13-14.

[53] Аль Джабри Х.Ш., Родионов В.И. Граф ациклических орграфов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2015. Т. 25. Вып. 4. С. 441-452.

[54] Al' Dzhabri Kh.Sh. On subgraphs of graph of binary relations // Groups and graphs, algorithms and automata: abstracts of the international conference and PhD summer school / Ural federal university, IMM UB RAS, IM SB RAS. Yekaterinburg, 2015. P. 30.

ОБОЗНАЧЕНИЯ

X — произвольное множество

X2 ^ { 0,1} — характеристическая функция

2х2 — совокупность бинарных отношений множества X

а <-> т — диаграмма смежных бинарных отношений а, т Е 2х

( 2х2, Е(X)) — граф бинарных отношений

(X) — связная компонента графа бинарных отношений, содержащая а Уо^) — совокупность частичных порядков множества X ( V (X), Е(X)) — граф частичных порядков

Т0(п) — число Т0-топологий, определенных на множестве { 1,..., п} V(X) — совокупность рефлексивно-транзитивных отношений множества X ( V(X), Е(X)) — граф рефлексивно-транзитивных отношений Т(X) — совокупность конечных топологий, определенных на множестве X (Т(X),Е(X)) — граф конечных топологий

А^) — совокупность ациклических отношений множества { 1,..., п} ( ),Е(X)) — граф ациклических отношений (ациклических графов) Ап — число ациклических графов, определенных на множестве { 1,..., п} S(а) — опорное множество частичного порядка а Е Уо^) S(а) — опорное множество ациклического отношения а Е А^)

— символ Кронекера S(п,т) — числа Стирлинга 2-го рода

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.