БАШОВА НАДЕЖДА ПЕТРОВНА КЛАССИФИКАЦИЯ И ПОДСЧЕТ ЧИСЛА ТОПОЛОГИЙ НА КОНЕЧНЫХ МНОЖЕСТВАХ

brief description

БАШОВА НАДЕЖДА ПЕТРОВНА УДК 519.1 КЛАССИФИКАЦИЯ И ПОДСЧЕТ ЧИСЛА ТОПОЛОГИЙ НА КОНЕЧНЫХ МНОЖЕСТВАХ 01.01.08 математическая логика, дискретная математика и теория алгоритмов Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель кандидат физико-математических наук, доцент Стеганцева Полина Георгиевна Запорожье 2016 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ 4 1 ОБЗОР ЛИТЕРАТУРЫ 10 Выводы по разделу 1 17 2 ПОДСЧЕТ И ПЕРЕЧИСЛЕНИЕ ТОПОЛОГИЙ С МАЛЫМ ЧИСЛОМ ЭЛЕМЕНТОВ 19 2.1 Аксиомы топологии на конечном множестве. Классификация топологий по числу элементов. Полные и неполные топологии и их свойства 19 2.2 Топологии-матрешки. Подсчет числа топологий-матрешек 22 2.3 Топологическая интерпретация чисел Моргана 35 2.4 Описание топологий 3-, 4-, 5 - класса и их подсчет 36 2.5 Подсчет негомеоморфных топологий в m-классе при m=3,4,5 41 2.6 Восстановление топологий на конечном множестве по топологии на его подмножестве 45 2.7 Выводы по разделу 2 48 3 ИССЛЕДОВАНИЕ ТОПОЛОГИЙ НА КОНЕЧНОМ МНОЖЕСТВЕ С ПОМОЩЬЮ ГРАФОВ 49 3.1 Частично упорядоченные множества. Решетки 49 3.2 Ориентированные графы. Основные понятия 51 3.3 Изображение топологий на конечных множествах колчанами 53 3.4 T -гомеоморфизм топологических пространств 54 3.5 Алгоритм построения T -колчанов 56 3.6 Свойства T -колчанов T0 -топологий. Критерий T0 -топологии в терминах T -колчанов 58 3.7 Теорема Стенли и T -колчаны топологий из некоторых классов 62 3.8 Выводы по разделу 3 76 4 СУЩЕСТВОВАНИЕ И СТРОЕНИЕ БЛИЗКИХ К ДИСКРЕТНОЙ ТОПОЛОГИЙ НА КОНЕЧНОМ МНОЖЕСТВЕ 78 4.1 Индекс элемента топологии 78 3 4.2 Вектор топологии и его свойства 83 4.3 Глубина множества в топологии и его связь с вектором топологии 86 4.4 Существование и строение близких к дискретной топологий 88 4.5 Выводы по разделу 4 97 5 КЛАССИФИКАЦИЯ И ОПИСАНИЕ ТОПОЛОГИЙ НА КОНЕЧНЫХ МНОЖЕСТВАХ ПРИ ПОМОЩИ БИЮНКТИВНЫХ БУЛЕВЫХ ФУНКЦИЙ 98 5.1 Связь булевых функций с топологиями на конечном множестве 98 5.2 Связь булевых функций, задающих топологии, с основными замкнутыми классами булевых функций 100 5.3 Связь булевых функций, задающих топологии, с классами Шеффера 103 5.4 Существенные и несущественные переменные в топологии. Связь веса топологии с числом несущественных переменных в ней 108 5.5 Вид 2-КНФ булевых функций, задающих близкие к дискретной топологии на конечном множестве 112 5.6 База булевой функции, задающей топологию 115 5.7 Выводы по разделу 5 116 ВЫВОДЫ 117 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 119 4 ВВЕДЕНИЕ Актуальность темы. Интерес к исследованию топологий на конечных множествах не ослабевает уже на протяжении долгого времени. На сегодняшний день задача о подсчете числа топологий на произвольном конечном множестве остается актуальной по нескольким причинам: • она до сих пор полностью не решена; • в печати постоянно появляются статьи с новыми результатами в этой области; • исследования по этой тематике перекликаются со многими разделами современной математики: алгебраическая топология, теория групп, комбинаторный анализ, теория графов. В общей постановке задача подсчета топологий на конечном множестве является NP -полной, то есть для нахождения решения этой задачи на сегодняшний день не существует алгоритма полиномиальной сложности, а все точные алгоритмы так или иначе сводятся к полному перебору. Первые результаты исследования топологий на конечных множествах появляются в 60-70-х годах двадцатого столетия в статьях H. Sharp, Jn. [34], J. W. Evans [13], S. D.Chatterji [9], D. Kleitman [19]. В работах H. Sharp, Jn. и J. W. Evans топологии на конечных множествах разбиваются на классы по числу элементов и исследуются в каждом классе отдельно. Для исследования топологий на конечных множествах используются транзитивные графы. В книге Ф. Харари [86] задача подсчета всех топологий на n -элементном множестве отождествляется с задачей подсчета всех помеченных транзитивных орграфов с n вершинами и относится к списку нерешенных задач. Параллельно с задачей подсчета всех топологий на конечном множестве рассматривается задача подсчета всех негомеоморфных топологий. Известно, что общее число T (n) ~ T0 -топологий и число T(n) всех топологий на n -элементном множестве связаны формулой: T( ) ( ) ( ) n S n m T m n m ~ , 1 ∑ = = ⋅ , где S(n, числа Стирлинга m) 5 второго рода. Впервые эта формула была опубликована в статье J. W. Evans [13]. В работах и D. Kleitman и В. Rothschild [19] рассматривались асимптотические оценки числа топологий на конечном множестве. Было доказано, что логарифм по основанию 2 от числа различных топологий на произвольном n -элементном множестве, при n → ∞ , асимптотически равен 4 2 n . При доказательстве этого факта использовалось опубликованное в работе S. D. Chatterji [9] неравенство 4 2 2 n Tn ≥ для общего числа всех топологий на n - элементном множестве. Вопросом подсчета топологий на произвольном конечном множестве занимался в своих работах З. И. Боревич [4, 5]. Он свел подсчет общего числа T0 -топологий на произвольном n -элементном множестве к подсчету помеченных T0 -топологий специального вида, связанных с набором ( ) p pm , , 1 K , где p1 +K+ pm = n . В работе [5] доказана периодичность последовательности вычетов числа помеченных T0 -топологий. Одной из последних работ в этом направлении является работа M. Y. Kizmaz [18], в которой автор доказывает, что для любого простого числа p имеет место сравнение T(p ) k ( p) k ≡ +1 mod , где ( ) k T p − число всех топологий на k p -элементном множестве. Для создания эффективного алгоритма подсчета топологий на произвольном конечном множестве возникает необходимость представления элементов топологии в такой форме, которую было бы легко сохранять в памяти компьютера. Это можно сделать, используя для кодирования топологий булевы функции. Такой подход был использован в работе И. А. Шилина. Сегодня, при исследовании булевых функций, кроме замкнутых классов Поста, много внимания уделяется исследованию классов Шефера, которые были введены в 1978 г. T. J. Schaefer [32]. Особый вклад при изучении вопроса о размерах и свойствах классов Шеффера внесли роботы авторов В. Б. Алексеева, С. П. Горшкова, С. А. Гизунова, В. А. Носова и А. В. Тарасова. 6 Все вышесказанное говорит об актуальности задачи исследования и подсчета топологий на конечном множестве. Именно этим вопросам и посвящена данная диссертационная работа. Связь работы с научными программами, планами, темами. Диссертационное исследование выполнено в соответствии с планами научных исследований кафедры алгебры и геометрии ГВУЗ «Запорожский национальный университет» МОНУ вне бюджетных и хоздоговорных тем. Цель и задачи исследования. Целью работы является классификация и подсчет топологий на произвольном конечном множестве. Основные задачи работы: • классификация топологий на конечных множествах; • исследование структуры топологий в некоторых классах; • описание топологий на конечных множествах графами специального вида; • разработка аппарата для доказательства существования топологий в m - классах при n n 2 m 2 1 ≤ ≤ − ; • исследование топологий на конечных множествах с помощью булевых функций. Объект исследования топологии на конечных множествах. Предмет исследования структура топологий на конечных множествах, свойства топологий на конечных множествах, специальные виды топологий на конечных множествах. Методы исследования. При решении поставленных задач в диссертации использовались комбинаторные методы, методы математического моделирования, теории графов, теории изображений частично упорядоченных множеств, теории булевых функций и теории кодирования. Научная новизна полученных результатов. В работе для исследования топологий на конечных множествах были использованы ориентированные графы (колчаны) и булевы функции. Колчаны, задающие топологии, названы в работе T -колчанами, для исследования топологий на конечных множествах использовались впервые. Показано, что булевы функции, задающие топологии на конечном множестве, являются биюнктивными слабо положительными и 7 слабо отрицательными булевыми функциями и имеют 2-КНФ, каждая дизъюнкция которой имеет вид x ∨ y . В работе получен ряд новых результатов: • явные формулы для подсчета топологий специального вида на произвольном n -элементном множестве; • критерий Т0 -топологий на конечных множествах в терминах T -колчанов; • теорема о существовании и структуре близких к дискретной топологий на конечных множествах; • теорема о виде 2-КНФ булевых функций, задающих близкие к дискретной топологии на конечных множествах. Обоснованность и достоверность научных положений и выводов диссертационной работы. В работе используется аналитический метод исследования. Доказательства всех теорем являются полными и обоснованными. Некоторые из полученных результатов повторяют результаты, полученные другими авторами, но в этой работе они получены другими методами. В ряде случаев полученные результаты были протестированы с помощью ЭВМ. Научное значение работы. Поскольку задача подсчета количества всех топологий на конечных множествах относится к нерешенным задачам, то сделанные в данной работе шаги к её решению, безусловно, имеют научное значение. Практическое значение полученных результатов. В данной работе исследование топологической структуры на конечных множествах проводится методами теории графов, комбинаторными методами, а также с помощью биюнктивных булевых функций. Оно будет интересным как для геометров, так и для специалистов по дискретной математике. Предложенный подход для классификации топологий на конечных множествах может быть распространен на любые частично упорядоченные множества, которые возникают при исследованиях в алгебраической топологии, дифференциальной топологии, k - значной логике, комбинаторном анализе, теории графов и др. 8 Топологии на конечных множествах и соответствующие им графы применяются в химии для описания молекулярной структуры, а топологические понятия применяются при анализе молекулярных структур. Тот факт, что топологии на конечных множествах задаются булевыми функциями, 2-КНФ которых имеет определенный вид, может быть использован для создания эффективного алгоритма подсчета всех топологий на конечных множествах. Личный вклад соискателя. Все основные результаты диссертационной работы, которые выносятся на защиту, получены автором лично. В публикациях, которые изданы в соавторстве, автору принадлежит: [1, 45, 47, 48] вывод формул для подсчета топологий-матрешек и топологий в классах с малым числом открытых множеств; [41, 43, 44, 49, 55, 57, 58] исследование топологий на конечных множествах с помощью ориентированных графов специального вида (Т -колчанов), доказательства свойств Т -колчанов T0 -топологий; [56, 59, 64, 66] применение понятий индекса элемента топологии, вектора топологии, глубины множества для оценки числа элементов топологии и исследования структуры близких к дискретной топологий на конечных множествах; [42, 46, 53, 54, 65] установление соответствия между топологиями на n -элементном множестве и булевыми функциями от n переменных, доказательство эквивалентности множества всех топологий на n -элементном множестве и множества всех биюнктивных 0-выполнимых и 1-выполнимых булевых функций от n переменных, доказательство теоремы о виде 2-КНФ булевых функций, которые задают близкие к дискретной топологии на конечном множестве. Апробация результатов диссертации. Основные положения диссертационной работы докладывались на таких научно-практических конференциях и семинарах: • научные семинары кафедры алгебры и геометрии Запорожского национального университета 2004-2015г.г.; • Международные конференции «Геометрия в Одессе» (г. Одесса − 2005 − 2008); 9 • Международная конференция по геометрии и топологии (г. Черкассы, ЧДТУ 2007); • Международная школа-семинар по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо − 2006); • Международная научно-практическая конференция «Математическое и программное обеспечение интеллектуальных систем» (г. Днепропетровск, ДНУ 2007); • Международный семинар «Геометрия в Астрахани 2007» «Симметрии: теоретические и методические аспекты» (г. Астрахань − 2007); • Межвузовские научно-практические семинары «Комбинаторные конфигурации и их применение» (г. Кировоград − 2010, 2011, 2015); • Международный научный семинар «Дискретная математика и её применение в экономическо-математическом моделировании и информационных технологиях» (г. Запорожье − 2012); • Всеукраинская научно-практическая конференция «Информатика и системные науки (ІСН-2015)» (г. Полтава − 2015); • научный семинар отдела топологий Института математики НАН Украины (г. Киев − 2015); • научный семинар кафедры алгебры и математической логики Киевского национального университета им. Тараса Шевченко (г. Киев − 2015); • Х летняя школа «Алгебра, Топология, Анализ» (Одесса 2015). Публикации. Основное содержание диссертации описано в 20 опубликованных работах: 6 статей [1, 43, 46, 53, 57, 66] в научных журналах и сборниках, которые входят в перечень специализированных журналов, утвержденных МОН Украины, и международных изданиях. Из них 2 статьи [43,66] в журналах из наукометрической базы SCOPUS, 1 статья [53] в журнале из наукометрической базы РИНЦ, 14 тезисов докладов в сборниках трудов научных конференций и семинаров.

bibliography

ВЫВОДЫ В диссертационной работе топологии на конечных множествах были исследованы с помощью графов специального вида и булевых функций. В соответствии с задачами диссертационного исследования получены такие основные научные результаты: 1. В m -классах топологий на n -элементном множестве для 2 ≤ m ≤ n +1 изучались топологии специального вида топологии-матрешки: получены формулы для вычисления числа всех помеченных и непомеченных матрешек длины l ; установлена связь между плотными матрешками и T0 -топологиями. 2. Для топологий из m -класса при m = 3,4,5 : выделены подклассы и описана структура топологий в каждом подклассе; найдена формула для числа всех помеченных и непомеченных топологий в подклассах и общего числа топологий в каждом классе; число помеченных топологий в каждом из этих классов выражено через число матрешек. 3. Установлено соответствие между множеством топологий на n - элементном множестве и множеством ориентированных графов особого вида (T -колчанов). Предложен алгоритм построения T -колчанов на произвольном конечном множестве. 4. Исследованы свойства T -колчанов T0 -топологий. 5. С помощью T -колчанов: для топологий из m -классов при 4 7 2 − = ⋅ n m , 1 2 n− , 5 13 2 − ⋅ n , 5 15 2 − ⋅ n описана их структура и получены формулы для общего числа этих топологий; найден новый m -класс топологий при 5 11 2 − = ⋅ n m ; описана структура и вычислено общее число топологий на n -элементном множестве в m -классах при n n k m − −− = + 1 1 2 2 для любого 1≤ k ≤ n −1. 6. Для исследования топологий на конечном множестве построен следующий аппарат: введено понятие индекса элемента топологии, вектора топологии, глубины множества; разработана методика оценки числа элементов топологии в зависимости от её вектора. 118 7. Для топологий из m -классов при n n 2 m 2 1 < ≤ − : с помощью введенного аппарата доказана теорема о их существовании и строении; описаны все соответствующие им T -колчаны; подсчитано общее число помеченных и непомеченных топологий в этих классах. 8. Доказана эквивалентность множества всех топологий на n -элементном множестве и множества всех биюнктивных 0-выполнимых и 1- выполнимых булевых функций от n переменных. Показано, что булевы функции, которые задают топологии на конечных множествах, принадлежат пересечению классов биюнктивных, слабо положительных и слабо отрицательных булевых функций и имеют 2-КНФ, каждая дизъюнкция которых имеет вид x ∨ y . 9. В терминах булевых функций дано определение некоторых топологических понятий и доказаны следующие теоремы: критерий несущественности переменной; о зависимости веса булевой функции от числа несущественных переменных; теорема о существовании топологий с m несущественными переменными, если m = 0,1K,n − 2,n . 10. Доказана теорема о виде 2-КНФ булевых функций, которые задают близкие к дискретной топологии на конечном множестве.