Матрицы инциденций и раскраски графа тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Краснова, Александра Юрьевна

• Краснова, Александра Юрьевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Краснова, Александра Юрьевна

Введение

Глава 1. Матрица инциденций обыкновенного графа

1.1 Матричные определения обыкновенного графа.

1.2 Общие свойства связности матрицы инциденций обыкновенного графа.

1.3 Свойства смежности матрицы инциденций обыкновенного графа.

Глава 2. Связность обыкновенного графа

2.1 Компоненты связности обыкновенного графа.

2.2 Алгоритм выделения компонент связности обыкновенного графа.

2.3 Точки сочленения, мосты и блоки обыкновенного графа.

Глава 3. Раскраски обыкновенного графа

3.1 Вершинная раскраска и хроматическое число.

3.2 Реберная раскраска и хроматический индекс.

3.3 Алгоритм вершинной раскраски обыкновенного графа.,

3.4 Алгоритм реберной раскраски обыкновенного графа

Глава 4. Задача оптимальной загрузки оборудования

4.1 Общая постановка задачи оптимальной загрузки оборудования.

4.2 Алгоритм решения задачи оптимальной загрузки ^ оборудования

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

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

В связи с этим актуальны исследования различных вопросов теории графов. В качестве темы моих исследований во время обучения в аспирантуре была тема раскраски графов. Дело в том, что мне было предложено продолжить исследования профессора Валерия Федоровича Горькового в направлении приложений. В качестве примера предлагалось рассмотреть задачу из книги Горькового В. Ф. [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 и разработанного алгоритма реберной раскраски графа было бы полезно сформулировать алгоритм определения наибольшего паросочетания.

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

Список литературы диссертационного исследования кандидат физико-математических наук Краснова, Александра Юрьевна, 2009 год

1. АхоА., ХопкрофтДж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

2. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1975. - 367 с.

3. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высш.шк., 1976. - 392 с.

4. Берж К. Теория графов и ее применение. Изд. иностр. лит., 1962. - 320 с.

5. ГоръковойВ. Ф. Графы Бержа: изоморфизм, декомпозиция, раскраски. СПб.: Изд. СПбУ, 1994, 183 с.

6. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1966. - 576 с.

7. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. - 353 с.

8. Зыков А. А. Основы теории графов. М.: Наука,1987. - 381 с.

9. ГрафоМапп Страница в интернете URL http://www.apmath.spbu.ru/gTafomann/.

10. Иванов Б. Н. Дискретная математика: Алгоритмы и программы. М.: Лаборатория Базовых знаний, 2003. - 288 с.

11. Краснова А. Ю. Об одном алгоритме раскрасок графа. //Проектирование научных и инженерных приложений в среде MATLAB: Труды III всероссийской научной конференции. Россия, СПб., 2326 октября 2007 г. СПб.: С.-Петерб. ун-та. - С. 230-237.

12. Краснова А. Ю. Об одном алгоритме раскраски графа и его модификациях //Вестн. С.-Петерб. ун-та. Сер. 10. 2008. Вып. 4. -СПб.: С.-Петерб. ун-та. С. 14-26.

13. Кристофидес Н. Теория графов: Алгоритмический подход. /Пер. с англ. Э. В. Вершкова и И. В. Коновальцева. Под ред. Г. П. Гаврилова. М.: Мир, 1978. - 432 с.

14. ЛипскийВ. Комбинаторика для программистов. /Пер. с польского В.А.Евстегнеева и О.А.Логиновой под ред. А.П.Ершова. М. Мир, 1988. - 215 с.

15. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. - 323 с.

16. Новиков Ф. А. Дискретная математика для программистов. -СПб.: Питер, 2001. 301 с.

17. Оре О. Графы и их применение. М.: Мир,1965. - 174 с.

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

19. СвамиМ., Тхуласираман К. Графы, сети и алгоритмы. -М.:Мир, 1984. -454 с.

20. Тараканов В. Е. Комбинаторные задачи и (ОД)-матрицы. М.: Наука, 1985. - 192 с.

21. Tamm У. Теория графов. М. Наука, 1988. - 424 с.

22. УилсонР. Введение в теорию графов. М.: Мир, 1977. - 208 с.

23. Успенский В. А., Семенов А. Л. Теория алгоритмов: основные понятия и приложения. М.: Наука, 1987. - 288 с.

24. Харари Ф. Теория графов /Пер. с англ. и предисл. В.П. Козырева; под ред. Г.П. Гаврилова. Изд. 2-е. М.: Едиториал УРСС, 2003. - 300 с.

25. Хитрое Г. М. Об определении разложимой матрицы и ее нормальной формы // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2006. Вып. 3. - СПб.: С.-Петерб. ун-та. - С. 85-91.

26. BrelazD. New Metods to Color the Vertices of a. Graph. //Commun. ACM 22, 4(Apr. 1979). Pp. 251-256.

27. WindersonA. A New Approximate Graph Coloring Algorithm. //Commun of ACM,1982. Pp. 325-329.

28. Bui T. N., Nguyen Т. H. An Agent-Based Algorithm for Generalized Graph Colorings. //GECCO'06, July 8-12, 2006, Seattle, Washington, USA. Pp. 19-26.

29. DiestelR. Graph Theory. Electronic Edition 2000.

30. KubaleM., JackowskiB. A Generalized Implicit Enumeration Algorithm for Graph Coloring. //Commun of ACM, Vol.28, No 4, Apr. 1985. Pp. 412-418.

31. MatulaD. W., LelandL. B. Smallest-Last Ordering and Clustering and Graph Coloring Algorithms. //J. of the Assoc. for Сотр. Machinery, Vol. 30, No 3, July 1983. Pp. 417-427.n