Матрицы инциденций и раскраски графа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Санкт-Петербургский государетпенпый университет

Но, правах рукописи

Краснова Александра Юрьевна

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

01.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург - 2009

003464233

Работа выполнена на кафедре высшей математики факультета прикладной матсматики-процессов управления Санкт-Петербургского государственного университета

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, доцент Хитров Геннадий Михайлович

доктор физико-математических паук, профессор Смирнов Николай Васильевич (Санкт-Петербургский государственный университет)

кандидат физико-математических наук, доцент Новиков Федор Александрович (Санкт-Петербургский государственный политехнический университет)

Петрозаводский государственный университет.

Защита состоится " (ШЛ.иМ 2009 г. в ч. мин. на заседании совета Д.212.232.5У по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, В.О., Средний пр., 41/43, ауд. ■_£/>.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан " ¿1? "

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

2009

Ногин В.Д.

Общая характеристика работы

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

Цели и задачи исследования. Объектом исследования диссертации является проблема раскраски графов. Первоначально целью диссертации было продолжить исследования профессора Санкт-Петербургского государственного университета Валерия Федоровича Горькового в направлении приложений. В качестве примера предполагалось рассмотреть задачу оптимальной загрузки оборудования из монографии Горькового В.Ф. «Графы Бержа: изоморфизм] декомпозиция, раскраски». В данной книге производственный процесс моделировался графом, и в модели задача сводилась к оптимальной реберной раскраске графа. Поскольку реберную раскраску можно свести к более известной задаче вершинной раскраски, то предстояло начать с нее. В данном исследовании упор был сделан не столько на теории вопроса, сколько на практических алгоритмах минимальной раскраски графа. К алгоритмам предъявлялись следующие требования: они должны быть достаточно просты как для понимания, так и для реализации. Эти требования в свою очередь налагали требования на используемый математический аппарат - он должен быть удобным для программирования. Развитие на факультете прикладной математики - процессов управления (ПМ-ПУ) СПбГУ матричных методов в теории графов под руководством Геннадия Михайловича Хитрова с аналогичными целями, определило выбор математического аппарата. Однако оставался выбор. - на какие матрицы, связанные с обыкновенными графами (именно такие графы и рассматриваются в диссертации) ориентироваться: па матрицы смежности или матрицы инциденций. После колебаний и большого числа

П])()Г) п ошибок было решено остановиться на матрицах ипциденций. Выбор обосновывался двумя причинами: во-первых, в матрице инциденций, в отличие от матрицы смежности, информация о вершинах и ребрах содержится в явном симметричном виде; во-вторых, построением алгоритмов, базирующихся на матрице смежности, занималось много других специалистов. Идеология, использованная при построении алгоритма раскраски графа, оказалась достаточно продуктивной, и легко переносимой для построения алгоритма разложения графа па компоненты связности и, как следствие, для выделения блоков графа. Расширение в исследованиях области применения матриц инциденций потребовало более детального рассмотрения самих матриц инциденций.

Методы исследования. В диссертации используются сведения из хорошо известной теории матриц; в том числе общие свойства квадратных матриц с неотрицательными элементами.

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

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

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

графов, а ее материалы могут быть иенользованы при чтении специальных курсов для студентов математических специальностей ВУЗов. На основе полученных результатов были созданы программы для пакета «Zeronc», ориентированного на работу с графами.

Апробация работы. Основные результаты работы докладывались и обсуждались на международных научных конференциях студентов и аспирантов «Процессы управления и устойчивость» на факультете ПМ-ПУ СПбГУ в 2006., 2007 и 2008 годах; III всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB» в Санкт-Петербурге в 2007 году. Результаты диссертации докладывались также на семинарах кафедры высшей математики факультета ПМ-ПУ Санкт-Петербургского государственного университета.

Публикации. Основные результаты диссертационной работы отражены в 5 публикациях, в том числе в 1 статье, опубликованной в издании, рекомендованном ВАК. Список работ приведен в конце автореферата.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы. Работа изложена на 84 странице«, содержит 9 рисунков. Список литературы содержит 35 наименований.

Основное содержание работы

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

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

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

Матричный подход к теории обыкновенных графов всегда требует пояснения - о какой матрице, сопоставляемой графу, идет речь: о матрице смежности или матрице инциденций. Использование двух различных матриц для задания обыкновенного графа связано с двумя различающимися точками зрения на граф. Геометрически, обыкновенный грае}) - это множество точек (вершин) на плоскости, некоторые из которых соединены между собой ненаправленными отрезками. Кроме того, когда говорят об обыкновенных графах, то подразумевают, что соединяться могут только различные точки (вершины) и это соединение однократное. Таким образом «соединение» вершин, если не интересоваться характеристиками соединяющих отрезков, по сути, есть бинарное отношение на множестве вершин, т. е. некоторое подмножества декартова произведения множества вершин на себя. Это и есть первая точка зрения на обыкновенный граф. При этом вершины, между которыми имеется связь (соединение), называются смежными.

При второй точке зрения, соединяющие пары вершин ненаправленные отрезки, приобретают самостоятельное значение. Эти отрезки именуются ребрами. Каждое ребро ограничивается двумя вершинами. Вершина, ограничивающая некоторое ребро, называется инцидентной этому ребру. Таким образом, вторая точка зрения на обыкновенный граф базируется на рассмотрении двух множеств: множества вершин, которое будем обозначать через V, и множества ребер, которое будем обозначать через X, а также на отношении инцидентности. связывающим элементы двух указанных множеств. Обыкновенный граф обычно обозначают через С(У, X).

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

мера строк н столбцов совпадают с номерами вершин. Обозначим эту таблицу или, что - то же самое, матрицу через А, а ее элементы через ац (г - номер строки, у - номер столбца). При этом элемент ау равен 1, если вершина с номером г смежна с вершиной с номером ], и равен нулю - в противном случае (матрицу с такими элементами также называют (0,1)-матрицей). Очевидно, что для обыкновенного графа а^ = ац и а,ц = 0. Матрицу А, построенную таким образом, называют матрицей смежности графа.

При задании графа матрицей смежности А все различные представители графа задаются выражением А = РАР' (штрих, здесь и далее, означает транспонирование матрицы), где Р - матрица перестановки, т. с. все представители графа задаются с точностью до нумерации его вершин. Данное преобразование матрицы А в матрицу А является частным случаем преобразования подобия, поэтому его называют также преобразованием перестановочного подобия, а матрицы А и А - перестановочно подобными или Р-подобными.

В соответствии с тем, что перестановочно подобные симметричные (0,1)-матрицы с нулевой диагональю появились при описании одного и того же обыкновенного графа, то сам класс таких перестановочно подобных матриц можно назвать обыкновенным графом. Определение графа, как класса перестановочно подобных (0,1)-матриц, вполне соответствует определению «абстрактного графа», как класса изоморфных между собой графов.

При второй точке зрения на обыкновенный граф, описание (задание) связей между элементами множеств V и X можно осуществить с помощью прямоугольной таблицы или матрицы В, номера строк которой совпадают с номерами вершин (номерами элементов множества У), а номера столбцов с номерами ребер (номерами элементов множества X). Элемент Ь^ матрицы В равен 1, если вершина (vi 6 V) инцидентна ребру х^ (х^ 6 X), и равен нулю - в противном случае. Построенную таким образом матрицу В называют матрицей инциденций графа. Эта (ОД)-матрица в соответствии с ее построением обладает следующими свойствами: число строк этой матрицы совпадает с числом вершин, а число столбцов - с числом ребер обыкновенного графа; каждый столбец содержит ровно две единицы, все столбцы - различные.

Итак, если при некоторой фиксированной нумерации вершин и некоторой фиксированной нумерации ребер обыкновенному графу

X) соответствует матрица инциденций В, а при изменении ну-

мерации элементов множеств V и X матрица В, то матрицы В и В связаны между собой соотношением В = РВС} для некоторых матриц перестановок Р и <5, соответствующих размерностей. Преобразование матрицы В в матрицу В будем называть перестановочно эквивалентным преобразованием матриц, а сами матрицы В я В -перестановочно эквивалентными.

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

Если при построении матрицы смежности и матрицы инциденций графа используется одна и та же нумерация вершин графа, то независимо от нумерации ребер между этими матрицами существует известная связь:

А = В В' - сИад(ВВ'), (1.1)

где сИад(ВВ') - диагональная матрица, совпадающая с главной диагональю матрицы ВВ'.

В виде утверждения-теоремы представлена связь между перестановочно эквивалентными матрицами инциденций и соответствующими им матрицами смежности.

Теорема 1.1. Матрицы инциденций В и В будут перестановочно эквивалентными тогда и только тогда, когда соответствующие им по формуле (1.1) матрицы смежности А и А будут перестановочно подобными.

Два графа Си называются изоморфными, если между их вершинами существует взаимнооднозначное соответствие, сохраняющее смежность.

Приведены рассуждения относительно изоморфизма графов, которые, по сути, являются доказательством следующих теорем:

Теорема 1.2. Два обыкновенных графа изоморфны тогда и только тогда, когда их матрицы смежности перестановочно подобны.

Теорема 1.3. Два обыкновенных графа изоморфны тогда и только тогда, когда их матрицы инциденций перестановочно эквивалентны.

Из формулировок видно, что данные теоремы можно трактовать как правила проверки изоморфизма графов.

Граф ¿ч(\/1,Л'1) называется подграфом графа, С(У,Х), (-ели

Я V и Л'] С X. При этом, вершины и ребра, инцидентные в

графе С?1 (VI, А!-!), должны быть инцидентными и 15 графе X). Если У\ = V, то подграф называется остовным подграфом графа С(У,Х).

Если граф С(У, X) задай своей матрицей шщиденций В, то описание его подграфов получается из матрицы В путем вычеркивания ее нескольких строк и соответствующих им столбцов. Столбцы, соответствующие данной строке в матрице инциденцнй, соответствуют ребрам, инцидентным данной вершине в графе. Итоговая подматрица, будет обладать всеми свойствами матрицы шщиденций.

В графе С маршрутом называется чередующаяся последовательность вершин и ребер Уо, £1,г>1,£2> ••• хт эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины (а следовательно, и ребра) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его п вершин различны и п > 3. При этом цикл содержащий п вершин обозначается как п-цикл.

Граф С называется связным, если любая пара его вершин соединена простой цепью. Максимальный связный подграф графа С?, называется компонентой связности, или просто компонентой графа С.

Цепь, простая цепь, цикл, компонента - это, по сути, подграфы графа, обладающие некоторыми определенными свойствами. Чтобы изложить эти понятия на языке подматриц, в работе определено свойство связности па языке матриц шщиденций. В результате на матрицы шщиденций обобщено понятие разложимой матрицы, а также введено понятие почти разложимой матрицы шщиденций. При этом предполагается, что матрицы инциденцнй имеют число строк, большее либо равное 3.

Определение 1.4. Матрицу шщиденций размерности п х т. будем называть разложимой, если она содержит нулевые строки или

перестановочно эквивалентна матрице вида

В =

/ Ьц • • • ь1к 0 0 \

Ьп • ■ к,к 0 0

0 . .. 0 • Ь + 1,т

V о': .. 0 Ьп,к+1 /

(1.2)

Определение 1.4'. Матрицу инциденций размерности п х т будем называть неразложимой, если она не содержит нулевых строк и не является матрицей перестановочно эквивалентной матрице вида (1.2).

Определение 1.5. Матрицу инциденций будем называть почти разложимой по строкам, если она не является разложимой, но существует, по крайней мерс, одна строка, удаление которой, а также соответствующих ей столбцов, превращают полученную подматрицу в разложимую.

Теорема 1.4. Неразложимая матрица инциденцин размерности п х т будет почти разложимой по строкам тогда и только тогда, когда она перестановочно эквивалентна матрице вида

/ ь

В =

11

V о

V 0

Ь\к

о о

о о

ЬЧ,к+1 Ьч+1,к+1

Ьп,к+1

о о

\

п

, т )

(1.3)

Определение 1.6. Матрицу инциденций размерности п х т будем называть почти разложимой по столбцам, если она не является разложимой и перестановочно эквивалентна матрице вида:

В =

( ьи о

V о

Ь[Л-1

о

1>1А- 1 Ь/,4 О

О 1>1+1,4 Ьг+1,«+1

О

Он ,1+1

О \ о

(1.4)

Теорема 1.0. Если матрица инциденций почти разложима по столбцам, то она является и почти разложимой по строкам.

Один из основных результатов первой главы является доказательство следующих теорем, которые, по сути, являются правилами проверки графа на связность.

Теорема 1.5. Обыкновенный граф распадается на компоненты связности тогда и только тогда, когда его матрица инциденций разложима.

Теорема 1.5'. (Следствие из теоремы 1.1.) Грае}) связен тогда и только тогда, когда его матрица инциденций неразложима.

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

Данные определения позволили сформулировать достаточно очевидные утверждения:

• граф С имеет точки сочленения тогда и только тогда, когда его матрица инциденций почти разложима по строкам:

• аналогично, граф С имеет мосты тогда и только тогда, когда его матрица инциденций почти разложима по столбцам.

Подграф, образованный столбцом t матрицы инциденций вида (1.4) является мостом, а вершина, соответствующая строке q матрицы инциденций вида (1.3), - точкой сочленения. В таком случае, блокам графа будет соответствовать подграфы, образованные строками {61^,..., Ьч]} матрицы инциденций при ] = 1,..., к и строками {Ьад, • ■ •, Ьгу} при з = (к + 1),...,т.

Определение 1.7. Матрицу инциденций, пе являющуюся разложимой или почти разложимой по строкам, будем называть неразделимой.

Замечание 1.4. Матрица инциденций любого простого п-цикла перестановочно эквивалентна квадратной размерности п (ОД)-матрице

( 1 1 0 . . 0 0 \

0 1 1 . . 0 0

Я = 0 0 1 . . 0 0 (1

0 0 0 . . 1 1

V 1 0 0 . . 0 1 /

Теорема 1.7. Квадратная размерности п (ОД)-матрица Р с различными столбцами, у которой все строчные и столбцовые суммы равны 2, будет перестановочно эквивалентной матрице Н тогда и только тогда, когда она не является разложимой.

Определение 1.8. Если в графе б имеется простой остовный цикл 2, то (7 называется гамилътоновым графом, а 2 - галшлъто-новым циклом.

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

Теорема 1.8. Обыкновенный граф с п вершинами будет гамиль-тоновым тогда и только тогда, когда его матрица инциденций содержит квадратную подматрицу размерности п, со всеми строчными суммами равными 2 и не являющуюся разложимой матрицей.

Теорема 1.9. Матрица инциденций гамильтонова графа неразделима.

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

"Утверждение 1.1. Вершины и* и V} обыкновенного графа будут смежными тогда и только тогда, когда строка, являющаяся ада-маровым (поэлементным) произведением г-й и ^'-й строк матрицы инциденций В, будет содержать одну единицу, а все остальные элементы этой строки будут нулями.

Утверждение 1.2. Вершины Vi и обыкновенного графа будут несмежными тогда и только тогда, когда строка, являющаяся поэлементным произведением г-й и ¡¡-я строк матрицы инциденций В, будет чисто нулевой.

Утверждение 1.3. Вершины ,..., г^ обыкновенного графа будут попарно несмежными тогда и только тогда, когда обычная сумма ¿1-й, ..., г^.-й строк матрицы инциденций В будет (0,1)-строкой.

Утверждение 1.4. Пусть вершины ,..., обыкновенного графа попарно несмежные; вершина 1Цк+1 данного графа будет несмежной с предыдущими вершинами тогда и только тогда, когда адамарово произведение и-и-й строки матрицы инциденций В со строкой, равной сумме строк матрицы инциденций В с номерами ¿1,..., и-, будет нулевой строкой.

Аналогичные утверждения 1' — 4' формулируются и доказываются для свойства смежности ребер графа.

Утверждение 1.0. Матрица О = В'В — 2Е будет матрицей смежности так называемого реберного графа, построенного по графу, заданному матрицей инциденций В.

Реберным графом С*, построенным по графу С, называют граф, каждой вершине которого сопоставлено ребро графа и две вершины графа С смежны тогда и только тогда, когда смежны соответствующие ребра графа С.

Приведенные выше утверждения лежат в основе предлагаемых в диссертации алгоритмов.

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

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

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

Вершины графа считаются пронумерованными числами от 1 до п. Поэтому множество вершин отождествляется с множеством I = {!,.... и}. Упоминавшиеся выше подмножества обозначаются /ь ..., /д. При этом Ц]=1/; — 1ч 1) О }к = 0 при } к.

ШАГ 1. Пусть граф задан матрицей смежности А. Тогда по матрице А строится матрица инциденций В. Слева к матрице В приписывается столбец (1,2,..., я)', тем самым формируя «расширенную» матрицу инциденций, которая также обозначается через В. Под словами «строка г^ расширенной матрицы инциденций», пони-

мается отроки с элементом ¿^ н первом столбце.

ШАГ 2. Строится подмножество вершин Берется любая вершина ¿1 и помещается в 1\. Затем берется любая вершина ¿2 смежная с вершиной ¿1 и помещается также в 1\. Вычеркиваются в матрице В строки с номерами г\ и ¿2- Если в оставшейся подматрице нет столбцов с одной единицей, то 1\ построено. В Этом случае 1\ - {г1,г2}. Если после вычеркивания упомянутых строк появились столбцы с одной единицей, то процесс построения 11 продолжается. Для этого берется любой столбец с одной единицей, которая расположена, например, в строке с номером ¿3 (номер определяется по первому столбцу «расширенной» матрицы инциденций). Заносится номер ¿3 в Д и вычеркивается строка с номером ¿3. Если в оставшейся подматрице нет столбцов с одной единицей, то множество 1\ построено, если есть - процесс построения Д продолжается дальше. Этот процесс продолжается до тех пор, пока не исчерпаются все столбцы с одной единицей. В результате этого процесса можно прийти к двум возможным исходам.

1. Вычеркнуты все строки расширенной матрицы инциденций В, т. е. Д = I. Это означает, что граф связен или одно компонентен.

2. Процесс оборвался в результате исчерпывания столбцов с одной единицей, причем мощность построенного множества Д меньше п. То есть |Д| = ( < п.

Подграф с вершинами, номера которых принадлежат Д, будет компонентой связности исходного графа. Матрица инциденций этого графа будет подматрицей матрицы В, образованной вычеркнутыми строками. Подматрица матрицы В, образованная невычеркнутыми строками, является матрицей инциденций некоторого другого графа, поскольку столбцы этой матрицы содержат по две единицы. С этой подматрицей начинаем работать как с исходной матрицей, т. е. начинаем строить множество /2 С / — Д.

Если ¡2 ф / — /1, то строим множество /3 и так далее. На каком-то д-ои шаге получим, что I = и — Д и /г и ... и при

этом Д П Д = </) при ] ф к. Подматрицы матрицы В с номерами строк принадлежащими множеству Iк (к = будут являться

матрицей инциденций соответствующей к-й компоненты связности (к = 1,... , г/). Добавляя к э тим </ компонентам связности, компоненты соответствующие изолированным вершинам, если таковые были в исходном графе, получаем все компоненты связности исходного графа.

Некоторые связные графы можно сделать несвязными, удалив однз' вершину - точку сочленения. Поиск точек сочленения графа не является трудной задачей, поскольку сводится к удалению вершины графа II последующей проверке оставшегося подграфа па увеличение числа компонент связности графа. Таким образом, простую технику выделения компонент графа можно применить и для поиска точек сочленения графа, и как следствие, для построения блоков обыкновенного связного графа. Когда речь идет о блоках, то рассматриваются не просто компоненты преобразованного графа, а компоненты с присоединенными к ним соответствующими точками сочленения.

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

Раскраской графа называется приписывание цветов его вершинам (ребрам), при этом раскраска называется щютшьной если пика-кие две смежные вершины (ребра) не получают одинакового цвета. Далее вместо «правильная раскраска» будем просто говорить «раскраска».

Определение 3.1. Вершинной раскраской (или вершинной г-раскраской) графа называется разбиение множества вершин V графа X) на непересекающиеся непустые подмножества вершин (иг=1К = V) таким образом, что вершины, принадлежащие одному подмножеству, являются несмежными.

Аналогично, формулируется определение реберной раскраски обыкновенного графа.

Определение 3.5. Реберной расщмской (или реберной г-щскщс-кой) графа называется разбиение множества ребер X графа С{У, X) на непересекающиеся непустые подмножества ребер Х^ (и^Х^ = X) таким образом, что ребра, принадлежащие одному подмножеству, являются несмежными.

Вершины (ребра), принадлежащие одному подмножеству, можно считать окрашенными в один цвет - отсюда и «вершинная (реберная) раскраска графа». Граф называется г-хроматическим, если он обладает г-раскраской, но не обладает (г— 1)-раскраской; такое число г в случае вершинной раскраски называют хроматическим числом графа С и обозначают через \(С), в случае реберной раскраски -хроматическим индексом или реберным хроматическим числом и

обозначают х'(С)- Раскраску с таким числом красок будем называть оптимальной.

Приведено несколько основных известных результатов, относящихся к хроматическим числам.

Рассматривается однокомпонентный обыкновенный граф С (У, X). Как и в ранее представленных алгоритмах множество вершин' графа отождествляется с множеством I, определенного во второй главе.

Предлагаемый алгоритм раскраски вершин графа основан на последовательном переборе строк матрицы ипциденций с целью разбиения множества вершин графа на непересекающиеся подмножества попарно несмежных вершин. Данные подмножества обозначаются Ух,..., V,-. При этом и£=1 V} = V и V} П Ук = 0 при ] ф к. Построение подмножеств проводится последовательно: пока не будет выделено подмножество построение подмножества не начинается. Перебор заканчивается при выполнении условия иГУГ = V.

Алгоритм последовательного раскрашивания вершин графа.

ШАГ 1. Пусть граф задан матрицей смежности А. По матрице А строится матрица инциденций В и формируется «расширенная» матрица инциденций. Для этого слева к матрице В приписывается столбец /. Элементы первого столбца в операциях сложения и умножения строк подматрицы не участвуют.

ШАГ 2. Организуется цикл по г = 1, г при выполнении условия иГУТ = У. Начинается построение подмножества У,. Пусть г = 1.

2.1. Для этого фиксируется первая строка подматрицы В. Номер фиксированной строки помещается в множество V].

2.2. Для определения вершин несмежных с фиксированной вершиной последовательно фиксированная строка поэлементно умножается на строки, расположенные ниже в подматрице В.

a). В случае, если полученная фиксированная строка содержит хотя бы один элемент, равный единице, берем следующую строку.

b). В случае, если полученная фиксированная строка будет нулевой, номер прибавляемой строки (соответствующей несмежной вершине) помещается в множество Ц, а сама строка удаляется из подматрицы и выбирается следующая строка. При этом фиксированная строка имеет уже новое значение, полученное в результате суммирования строк с номерами, принадлежащими построенному подмножеству Уi.

Процесс построения подмножества V] продолжается до тех пор, пока не переберутся все строки подматрицы. После построения под-

множества Vj н преобразованной подматрице удаляется фиксированная строка. Переход к шагу 2 при г = г + 1.

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

Выписываются номера вершин в том порядке, как они появляются в множествах Vi, для всех множеств Ц (г = 1,... ,г). Получается столбец lt, сравнение которого со столбцом 1 позволяет однозначно определить матрицу перестановки Р из равенства It = PI. Умножая исходную матрицу инциденций В слева на матрицу Р, устанавливается матрица инциденций Bt «раскрашенного графа» (Bt = РВ). По матрице Bt строится матрица смежности Аи и разбивается на блоки горизонтальными и вертикальными полосами размерностей |(i = 1,...,г). Диагональные блоки в матрице смеж-ностей At будут состоять из нулей, поскольку вершины, входящие в множество Vi (г = 1,..., г), являются несмежными.

Число г множеств I\ при использовании предлагаемого алгоритма вершинной раскраски, вообще говоря, зависит от первоначальной нумерации вершин. Чтобы уменьшить эту зависимость, а заодно и число г, этот алгоритм применяется некоторое число раз, меняя единообразным способом исходную нумерацию вершин. Данную операцию изменения нумерации вершин будем называть перемешиванием. Число перемешиваний (обозначим его через ц) задается произвольным образом. Операция же перемешивания состоит в следующем: в матрице Bt переставляются строки с помощью матрицы Q, где Q - матрица с единицами вдоль побочной диагонали. Таким образом, обозначая полученную матрицу через Bs, имеем Bs = QBt. В результате работы процедуры будут найдены rj возможных раскрасок вгь ..., гп цветов.

Определение 3.6. К-оптимальностью (обозначим через К0pt) будем называть наименьшее число красок в возможной раскраске, имеющей место при повторений процедуры перемешивания вершин и последующего раскрашивания полученной матрицы инциденций, т. е. K0pt — iuin{r, 7*1,..., rv}. При этом раскраску, соответствующую Kopt. будем называть К-оптимальной pacKjia.cKou графа.

Ранее было отмечено, что алгоритм вершинной раскраски работает на однокомпонентных обыкновенных графах с матрицами смежности порядка п > 2. Тем не менее алгоритм раскраски можно

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

Задача раскраски ребер графа сводится к задаче раскрашивания вершин графа. Для определения одной из возможных раскрасок ребер достаточно применить алгоритм вершинной раскраски к реберному графу. Понятно, что полученная вершинная раскраска реберного графа С* будет реберной раскраской графа (?.

Согласно утверждениям 1' — 4', при последовательном переборе столбцов матрицы инциденций и выделении г подмножеств попарно несмежных ребер графа получим одну из возможных реберных раскрасок графа. Тогда алгоритм последовательного раскрашивания вершин графа, примененный к транспонированной матрице инциденций В, даст алгоритм реберной раскраски графа.

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

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

Г > Г!>•••> Г,,.

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

Замечание 3.4. Приведенные выше рассуждения позволяют сформулировать новое; понятие в теории графов - нормальная форма матриц инциденций графа.

Определение 3.8. Матрица инциденций «раскрашенного» неразделимого графа <• последовательной нумерацией вершин по классам (цветам) и соответствующей нумерацией ребер будем называть нормальной формой матрицы инциденций графа.

Под последовательной нумерацией понимается нумерация вершин первого выбранного класса, затем второго и гак далее.

Нахождение минимального числа цветов для раскраски графа является АТ'-полной задачей, поскольку все существующие точные

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

Заметим, что использование матриц инцидепций для решения задачи раскраски графа с вычислительной точки зрения предпочтительнее, поскольку максимально верхняя граница однократного перебора будет п{п - 1)/2.

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

В заключении по результатам исследования сделаны краткие выводы и приводится перечень основных результатов, выносимых на защиту:

• на матрицы шщиденций обобщено понятие разложимой матрицы, а также введены понятия почти разложимой матрицы, неразделимой матрицы, нормальных форм разделимой и неразделимой матриц;

• разработан алгоритм выделения компонент связности, и как следствие, алгоритм построения блоков графа;

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

• предложена модификация алгоритма вершинной раскраски графа, дающая реберную раскраску графа.

В приложении приведены машинный код программ описанных в диссертации алгоритмов, выполненных в среде МаЛаЬ, а также, результаты численной реализации данных алгоритмов для конкретных графов.

Список публикаций по теме диссертации Публикации в изданиях, рекомендуемых ВАК

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

- СПб.: С.-Петерб. ун-та. - С. 14-2(i.

Публикации и других изданиях

2. Краснова Л. К). Бинарные операции над (0,1)-матрицами и их моделирование. //Пр.Упр. и Уст.: Тр. 37-й Междунар. Науч. Копф. Студ. п Асп. - СПб.: Изд-во С.-Петерб. ун-та, 2006. -С. 359-3G4.

3. Краснова А. Ю. Метод последовательного раскрашивания вершин графа. //Пр.Упр. и Уст.: Тр. 38-й Междунар. Науч. Конф. Студ. и Асп. - СПб.: Изд-во С.-Петерб. ун-та, 2007. - С. 38-43.

4. Краснова Л. К). Обидном алгоритме раскраски графа. //Проектирование научных и инженерных приложений в среде MAT-LAB: Труды III всероссийской научной конференции. Россия, СПб., 23-2« октября 2007 г. - СПб.: С.-Петерб. ун-та. - С. 230237.

5. Краснова А. Ю. Об одном алгоритме выделения компонент связности графа. //Пр.Упр. и Уст.: Тр. 39-й Междунар. Науч. Конф. Студ. и Асп. - СПб.: Изд-во С.-Петерб. ун-та, 2008.

- С. 52-5С.

Подписано к печати 1X 02.09. Формат 60 х 84 '/к,. Бумага офсетная Гарнитура Times. Печать цифровая. Печ. л 1,0.

Тираж 10» экт Заказ 4397._

Отпечатано к Отделе операшнноп ионпр^фии химического фикусыет;1 СПбГУ 198504. Санкт-Петербург. Смрый Петергоф, Университетский пр., J6 Тел о.?>«х-«043. 42М919

Введение

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

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

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