За последние три десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики. В значительной степени через теорию графов происходит ныне проникновение математических методов в на. уку и технику.
В связи с этим актуальны исследования различных вопросов теории графов. В качестве темы моих исследований во время обучения в аспирантуре была тема раскраски графов. Дело в том, что мне было предложено продолжить исследования профессора Валерия Федоровича Горькового в направлении приложений. В качестве примера предлагалось рассмотреть задачу из книги Горькового В. Ф. [5] -«Задачу оптимальной загрузки оборудования». В данной монографии производственный процесс моделировался графом, и в модели задача сводилась к оптимальной реберной раскраске графа. Поскольку реберную раскраску можно свести к более известной задаче вершинной раскраски, то мне предстояло начать с нее. Оптимальная вершинная раскраска графа — это раскраска вершин графа в минимальное число цветов. Это число в теории графов называется хроматическим числом графа. Отыскание хроматического числа относится к трудным задачам теории графов [19]. Поэтому мне было предложено сосредоточиться не столько на теории вопроса, сколько на практических алгоритмах минимальной раскраски графа. К алгоритмам предъявлялись следующие требования: они должны быть достаточно просты как для понимания, так и для реализации. Эти требования в свою очередь налагали требования на используемый математический аппарат — он должен быть удобным для программирования. Поскольку мой научный руководитель Геннадий Михайлович Хитров занимается развитием матричных методов в теории графов именно с аналогичными целями, то проблемы с выбором математического аппарата не было. Однако оставался выбор, — на какие матрицы, связанные с обыкновенными графами (именно такие графы и рассматриваются в диссертации) ориентироваться: на матрицы смежности или матрицы инциденций. После колебаний и большого числа проб и ошибок было решено остановиться на матрицах инциденций. Выбор обосновывался двумя причинами: во-первых, в матрице инциденций, в отличие от матрицы смежности, информация о вершинах и ребрах содержится в явном симметричном видево-вторых, построением алгоритмов, базирующихся на матрице смежности, занималось много других специалистов [16, 22].
Использование матриц инциденций для раскраски графов оказалось удачным выбором, поэтому мне удалось построить алгоритм, удовлетворяющий предъявляемым к нему требованиям. Идеология, использованная при построении алгоритма раскраски обыкновенного графа, оказалась достаточно продуктивной, и мне удалось применить ее для построения алгоритма разложения обыкновенного графа на компоненты связности и, как следствие, для выделения блоков графа.
Расширение в исследованиях области применения матриц инци-денций потребовало более детального рассмотрения самих матриц инциденций. В результате на матрицы инциденций было обобщено понятие разложимой матрицы, а также введены понятия почти разложимой матрицы инциденций, неразделимой матрицы инциденций, нормальных форм разделимой и неразделимой матриц инциденций.
Изложение в диссертации полученных результатов потребовало обратного порядка по сравнению с их получением. Так в диссертации вначале излагается материал, связанный с теорией матриц инциденций, а затем алгоритмы. Параллельно указываются области применения полученных теоретических и практических (алгоритмы) результатов. Так проверка условия является ли граф гамильто-новым, требует проверки необходимых условий этого свойства, т. е. проверки является ли матрица инциденций графа неразделимой.
В связи с тем, что терминология теории графов еще далеко не устоялась, а матричная терминология только разрабатывается, то цитирование источников ограничивается в основном несколькими признанными источниками, а матричные определения в диссертации возможно излишне подробны.
Диссертационная работа включает в себя четыре главы.
Первая глава диссертации посвящена изучению матрицы инциденций обыкновенного графа, устанавливаются некоторые свойства этой матрицы, которые помогут раскрыть структуру графа. Поэтому свойства этих матриц и другие связанные с ними результаты, формулируемые в данной главе, будут широко использоваться в последующих главах.
В начале главы представлено матричное определение обыкновенного графа, для чего описываются матрицы смежности и инци-денций графа. Установлена связь между различными матричными определениями обыкновенного графа. В виде теоремы сформулирована связь между перестановочно эквивалентными матрицами ин-циденций и соответствующими им матрицами смежности. Доказываются очевидные свойства смежности вершин и ребер графа, выраженных в терминах матриц инциденций. Приведено определение изоморфных графовв виде теоремы формулируется правило проверки изоморфизма графов. Рассматриваются общие свойства матрицы инциденций, введены понятия разложимой, неразложимой и почти разложимой матриц инциденций. Один из основных результатов первой главы является доказательство ряда теорем, которые, по сути, являются правилами проверки графа на связность. Также проведен ряд рассуждений относительно организации проверки графа на существование в нем гамильтоновых циклов.
Во второй главе речь идет о таком важном понятии как связность. Вводная часть главы включает в себя ряд известных определений и фактов относительно компонент связности графа. Основную часть главы занимает довольно простой алгоритм выделения компонент графа, основанный на последовательном разбиении множества вершин графа (заданного матрицей) на непересекающиеся подмножества. Проведенные исследования показали, что простую технику проверки можно применить и для поиска точек сочленения графа. Завершается глава алгоритмом нахождения блоков обыкновенного связного графа.
Изучаемые свойства матрицы инциденций служат основой мощного инструмента при исследовании раскраски обыкновенного графа. Раскраске графа посвящена третья глава. В начале главы приведены основные определения и обозначения. Предложен алгоритм вершинной раскраски обыкновенного графа, основанный на рассмотрении матрицы инциденций и последовательном выделении непустых подмножеств множества вершин графа. Приводится процедура перемешивания, позволяющая приблизить число красок к хроматическому числу, и модификация предлагаемого алгоритма, дающая реберную раскраску графа. Модификация алгоритма позволяют эмпирически убедиться в эффективности алгоритма и его оптимальности (двумя различными способами мы получаем один и тот же результат).
В четвертой главе рассматривается один класс задач типа загрузки оборудования. Общая постановка задачи сопровождается графовой и матричной интерпретацией. Описано сведение задачи оптимальной загрузки оборудования к проблеме поиска минимальной реберной раскраски графа.
В заключении приводится перечень основных результатов диссертации, также перечислен ряд направлений для дальнейшего исследования, интерес к которым вытекает из результатов диссертации.
Результаты, представленные в данной диссертации, ранее опубликованы в [11], [12], [13], [14], [15]. Результаты докладывались на ежегодных конференциях «Процессы управления и устойчивость» факультета ПМ-ПУ СПбГУ в 2006, 2007, 2008 годахна III-й всероссийской научной конференции «Проектирование инженерных и научных приложений в среде Mal. Lab» в 2008 годуа также на заседаниях кафедры высшей математики факультета ПМ-ПУ СПбГУ.
Заключение
.
Итоги и направления дальнейших исследований.
Основными результатами, которые получены в результате проведенных исследований являются новыми и состоят в следующем: на матрицы инциденций обобщено понятие разложимой матрицы, а также введены понятия почти разложимой матрицы инциденций, неразделимой матрицы инциденций, нормальных форм разделимой и неразделимой матриц инциденцийразработан алгоритм выделения компонент связности обыкновенного графа, и как следствие, алгоритм построения блоков обыкновенного графаразработан простой алгоритм вершинной раскраски обыкновенного графа, основанный на последовательном выделении непустых подмножеств множества вершин графаприводится процедура перемешивания, позволяющая приблизить число красок к хроматическому числу, и две модификации предлагаемого алгоритма, дающие реберную раскраску обыкновенного графа. Параллельно указываются области применения полученных теоретических и практических (алгоритмы) результатов. Так проверка условия является ли граф гамильтоновым, требует проверки является ли матрица инциденций графа неразделимой.
Ниже приведен ряд направлений для исследований, интерес к которым напрямую вытекает из полученных в данной работе результатов.
В Главе 3 было упомянуто правило проверки условия гамильто-новости графа. Наряду с задачей поиска гамильтонова цикла существует задача проверки является ли граф эйлеровым.
Эйлеров граф это граф, который содержит эйлеров цикл, т. е. замкнутую цепь, содержащую все вершины и все ребра графа. Понятно, что эйлеров граф должен быть связным.
Согласно Теореме 7.1 из [28, стр. 83] связный граф G будет эйлеровым тогда и только тогда когда каждая вершина графа G имеет четную степеньили когда множество ребер графа G можно разбить на простые циклы. Отметим, что эта теорема справедлива также и для мультиграфов.
В настоящее время важной и актуальной как для теории графов, так и для приложений задач теории графов является задача планарности. Известно много критериев плаиарности графа. В том числе и результат Мак-Лейна описания планарности, основанной на рассмотрении циклической структуры графа.
Теорема 11.16. [28, стр. 140] Граф G планарен тогда и только тогда, когда каждый его блок, имеющий по крайней мере три вершины, обладает таким базисом циклов Z, Z2,., Zm и таким У дополнительным Zq, что любое ребро блока принадлежит точно двум из этих (га + 1) циклов.
Базис циклов, графа G, определяется как базис пространства циклов графа G, состоящий только из простых циклов (базис циклов графа G является максимальным набором независимых простых циклов графа G или минимальным набором простых циклов, от которых зависят все циклы) [28, стр. 55].
Разработка нового алгоритма построения эйлерова граф с использованием матрицы инциденций графа дало бы возможность сформулировать новый критерий план арности.
Было бы интересно рассмотреть раскраску плоских карт и попытаться обосновать гипотезу четырех красок.
На основе замечания 3.1 и разработанного алгоритма реберной раскраски графа было бы полезно сформулировать алгоритм определения наибольшего паросочетания.
Более подробного изучения заслуживают также вопросы обобщения предлагаемой теории на случай произвольного графа.
