Матрицы инциденций и раскраски графа

• Автор: Краснова, Александра Юрьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 87 с. : ил.

Оглавление
Введение

Глава 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].
Использование матриц инциденций для раскраски графов оказалось удачным выбором, поэтому мне удалось построить алгоритм, удовлетворяющий предъявляемым к нему требованиям. Идеология, использованная при построении алгоритма раскраски обыкновенного графа, оказалась достаточно продуктивной, и мне удалось применить ее для построения алгоритма разложения обыкновенного графа на компоненты связности и, как следствие, для выделения блоков графа.

вершин. Наиболее известным полным двудольным графом является граф Кзуз, который изображен на рис. 2.3.
Рис. 2.3: Граф Кз,з-
Несвязный граф всегда можно представить как объединение связных компонент. Эти компоненты можно рассматривать независимо. Исследование же графа обычно сводится к изучению его компонент. Поэтому во многих случаях можно без ограничения общности предполагать, что рассматриваемый граф связен.
2.2 Алгоритм выделения компонент связности обыкновенного графа
Под выделением компонент связности обыкновенного графа С понимается такое разбиение множества вершин графа на непересе-кающиеся подмножества, что максимальные подграфы графа Є с вершинами принадлежащими указанным подмножествам являются связными графами никак не связанными между собой.
Вершины графа будем считать пронумерованными числами от 1 до п. Поэтому множество вершин будем отождествлять с множеством I = {1