Содержание к диссертации
Введение
Глава 1. Матрица инциденций обыкновенного графа 7
1.1 Матричные определения обыкновенного графа 7
1.2 Общие свойства связности матрицы инциденций обыкновенного графа 17
1.3 Свойства смежности матрицы инциденций обыкновенного графа 27
Глава 2. Связность обыкновенного графа 31
2.1 Компоненты связности обыкновенного графа 31
2.2 Алгоритм выделения компонент связности обыкновенного графа 34
2.3 Точки сочленения, мосты и блоки обыкновенного графа 37
Глава 3. Раскраски обыкновенного графа 41
3.1 Вершинная раскраска и хроматическое число 41
3.2 Реберная раскраска и хроматический индекс 47
3.3 Алгоритм вершинной раскраски обыкновенного графа 49
3.4 Алгоритм реберной раскраски обыкновенного графа . 53
Глава 4. Задача оптимальной загрузки оборудования 57
4.1 Общая постановка задачи оптимальной загрузки оборудования 58
4.2 Алгоритм решения задачи оптимальной загрузки оборудования
Заключение 62
Приложение 65
- Общие свойства связности матрицы инциденций обыкновенного графа
- Алгоритм выделения компонент связности обыкновенного графа
- Алгоритм вершинной раскраски обыкновенного графа
- Общая постановка задачи оптимальной загрузки оборудования
Введение к работе
За последние три десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики. В значительной степени через теорию графов происходит ныне проникновение математических методов в науку и технику.
В связи с этим актуальны исследования различных вопросов теории графов. В качестве темы моих исследований во время обучения в аспирантуре была тема раскраски графов. Дело в том, что мне было предложено продолжить исследования профессора Валерия Федоровича Горькового в направлении приложений. В качестве примера предлагалось рассмотреть задачу из книги Горькового В. Ф. [5] -«Задачу оптимальной загрузки оборудования». В данной монографии производственный процесс моделировался графом, и в модели задача сводилась к оптимальной реберной раскраске графа. Поскольку реберную раскраску можно свести к более известной задаче вершинной раскраски, то мне предстояло начать с нее. Оптимальная вершинная раскраска графа - это раскраска вершин графа в минимальное число цветов. Это число в теории графов называется хроматическим числом графа. Отыскание хроматического числа от-
носится к трудным задачам теории графов [19]. Поэтому мне было предложено сосредоточиться не столько на теории вопроса, сколько на практических алгоритмах минимальной раскраски графа. К алгоритмам предъявлялись следующие требования: они должны быть достаточно просты как для понимания, так и для реализации. Эти требования в свою очередь налагали требования на используемый математический аппарат - он должен быть удобным для программирования. Поскольку мой научный руководитель Геннадий Михайлович Хитров занимается развитием матричных методов в теории графов именно с аналогичными целями, то проблемы с выбором математического аппарата не было. Однако оставался выбор, - на какие матрицы, связанные с обыкновенными графами (именно такие графы и рассматриваются в диссертации) ориентироваться: на матрицы смежности или матрицы инциденций. После колебалий и большого числа проб и ошибок было решено остановиться на матрицах инциденций. Выбор обосновывался двумя причинами: во-первых, в матрице инциденций, в отличие от матрицы смежности, информация о вершинах и ребрах содержится в явном симметричном виде; во-вторых, построением алгоритмов, базирующихся на матрице смежности, занималось много других специалистов [16, 22].
Использование матриц инциденций для раскраски графов оказалось удачным выбором, поэтому мне удалось построить алгоритм, удовлетворяющий предъявляемым к нему требованиям. Идеология, использованная при построении алгоритма раскраски обыкновенного графа, оказалась достаточно продуктивной, и мне удалось применить ее для построения алгоритма разложения обыкновенного графа на компоненты связности и, как следствие, для выделения блоков графа.
Расширение в исследованиях области применения матриц инци-денций потребовало более детального рассмотрения самих матриц инциденций. В результате на матрицы инциденций было обобщено понятие разложимой матрицы, а также введены понятия почти разложимой матрицы инциденций, неразделимой матрицы инциденций, нормальных форм разделимой и неразделимой матриц инциденций.
Изложение в диссертации полученных результатов потребовало обратного порядка по сравнению с их получением. Так в диссертации вначале излагается материал, связанный с теорией матриц инциденций, а затем алгоритмы. Параллельно указываются области применения полученных теоретических и практических (алгоритмы) результатов. Так проверка условия является ли граф гамильто-новым, требует проверки необходимых условий этого свойства, т. е. проверки является ли матрица инциденций графа неразделимой.
В связи с тем, что терминология теории графов еще далеко не устоялась, а матричная терминология только разрабатывается, то цитирование источников ограничивается в основном несколькими признанными источниками, а матричные определения в диссертации возможно излишне подробны.
Диссертационная работа включает в себя четыре главы.
Первая глава диссертации посвящена изучению матрицы инциденций обыкновенного графа, устанавливаются некоторые свойства этой матрицы, которые помогут раскрыть структуру графа. Поэтому свойства этих матриц и другие связанные с ними результаты, формулируемые в данной главе, будут широко использоваться в последующих главах.
В начале главы представлено матричное определение обыкно-
венного графа, для чего описываются матрицы смежности и инци-денций графа. Установлена связь между различными матричными определениями обыкновенного графа. В виде теоремы сформулирована связь между перестановочно эквивалентными матрицами ин-циденций и соответствующими им матрицами смежности. Доказываются очевидные свойства смежности вершин и ребер графа, выраженных в терминах матриц инциденций. Приведено определение изоморфных графов; в виде теоремы формулируется правило проверки изоморфизма графов. Рассматриваются общие свойства матрицы инциденций, введены понятия разложимой, неразложимой и почти разложимой матриц инциденций. Один из основных результатов первой главы является доказательство ряда теорем, которые, по сути, являются правилами проверки графа на связность. Также проведен ряд рассуждений относительно организации проверки графа на существование в нем гамильтоновых циклов.
Во второй главе речь идет о таком важном понятии как связность. Вводная часть главы включает в себя ряд известных определений и фактов относительно компонент связности графа. Основную часть главы занимает довольно простой алгоритм выделения компонент графа, основанный на последовательном разбиении множества вершин графа (заданного матрицей) на непересекающиеся подмножества. Проведенные исследования показали, что простую технику проверки можно применить и для поиска точек сочленения графа. Завершается глава алгоритмом нахождения блоков обыкновенного связного графа.
Изучаемые свойства матрицы инциденций служат основой мощного инструмента при исследовании раскраски обыкновенного графа. Раскраске графа посвящена третья глава. В начале главы при-
ведены основные определения и обозначения. Предложен алгоритм вершинной раскраски обыкновенного графа, основанный на рассмотрении матрицы инциденций и последовательном выделении непустых подмножеств множества вершин графа. Приводится процедура перемешивания, позволяющая приблизить число красок к хроматическому числу, и модификация предлагаемого алгоритма, дающая реберную раскраску графа. Модификация алгоритма позволяют эмпирически убедиться в эффективности алгоритма и его оптимальности (двумя различными способами мы получаем один и тот же результат).
В четвертой главе рассматривается один класс задач типа загрузки оборудования. Общая постановка задачи сопровождается графовой и матричной интерпретацией. Описано сведение задачи оптимальной загрузки оборудования к проблеме поиска минимальной реберной раскраски графа.
В заключении приводится перечень основных результатов диссертации, также перечислен ряд направлений для дальнейшего исследования, интерес к которым вытекает из результатов диссертации.
Результаты, представленные в данной диссертации, ранее опубликованы в [11], [12], [13], [14], [15]. Результаты докладывались на ежегодных конференциях «Процессы управления и устойчивость» факультета ПМ-ПУ СПбГУ в 2006, 2007, 2008 годах; на Ш-й всероссийской научной конференции «Проектирование инженерных и научных приложений в среде Mal.Lab» в 2008 году; а также на заседаниях кафедры высшей математики факультета ПМ-ПУ СПбГУ.
Общие свойства связности матрицы инциденций обыкновенного графа
При второй точке зрения, соединяющие пары вершин ненаправленные отрезки, приобретают самостоятельное значение. Эти отрезки именуются ребрами. Каждое ребро ограничивается двумя вершинами. Вершина, ограничивающая некоторое ребро, называется инцидентной этому ребру. Говорят также, что ребро инцидентно ограничивающей его вершине. Две вершины инцидентные одному и тому же ребру называются смежными. Это определение смежных вершин не противоречит определению смежных вершин, данному выше. Аналогично понятию смежных вершин, вводится понятие смежных ребер. Два. ребра называются смежными, если они инцидентны одной и той же вершине.
Например, у графа на рис. 1.1 вершины v\ и г 2 смежные, а и VQ - нет; аналогично, ребра х\ и Х2 смежные, а Х\ и хз - нет. При этом ребро х\ инцидентно вершине V\.
Таким образом, вторая точка зрения на обыкновенный граф базируется на рассмотрении двух множеств: множества вершин, которое будем обозначать через V, и множества ребер, которое будем обозначать через X, а также на отношении инцидентности, связывающим элементы двух указанных множеств. Обыкновенный граф обычно обозначают через G(V,X) [8].
При первой точке зрения на обыкновенный граф описание (задание) связей между вершинами (по сути - описание (задание) графа) можно осуществить с помощью квадратной таблицы (квадратной матрицы), строки и столбцы которой соответствуют различным вершинам. Будем предполагать, что вершины пронумерованы, и номера строк и столбцов совпадают с номерами вершин. Обозначим эту таблицу или, что - то же самое, матрицу через А, а ее элементы через dij (і - номер строки, j - номер столбца). При этом элемент а - равен 1, если вершина с номером г смежна с вершиной с номером j, и равен О, в противном случае (матрицу с такими элементами также называют (0,1)-матрицей [6]). Очевидно, что для обыкновенного графа ац — dji и ац = 0. Матрицу А, построенную таким образом, называют матрицей смежности графа. Например, матрица смежности графа, представленного на рис. 1.1, будет выглядеть следующим образом:
Нетрудно также видеть, что изменение нумерации вершин ведет к перестановке строк и такой же перестановке столбцов в матрице А, или, как еще говорят, к перестановке рядов в матрице. Перестановка строк в матрице А задается с помощью умножения этой матрицы слева на так называемую матрицу перестановки, которую обозначим через Р. Матрица Р является квадратной (ОД)-матрицей, у которой в каждой строке и каждом столбце ровно по одной 1. Если идет речь, о «точно такой же перестановке столбцов» в матрице А, как и перестановке строк, задаваемой матрицей Р, то матрицу А, умножают справа на матрицу, транспонированную к матрице Р, т. е. на матрицу Р [6] (штрих, здесь и далее, означает транспонирование матрицы). Таким образом, если при исходной нумерации вершин графу соответствовала матрица смежности А, то при измененной с помощью матрицы перестановки Р нумерации вершин тому же графу будет соответствовать матрица. А — PAP . Данное преобразование матрицы А в матрицу А является частным случаем преобразования подобия, поэтому его называют также преобразованием перестановочного подобия, а матрицы Аи А- перестановочно подобными или Р-подобными [29].
В соответствии с тем, что перестановочно подобные симметричные (0,1)-матрицы с нулевой диагональю появились у нас при описании одного и того же обыкновенного графа, то сам класс таких перестановочно подобных матриц можно назвать обыкновенным графом. Определение графа, как класса перестановочно подобных (0,1)-матриц, вполне соответствует определению «абстрактного графа», как класса изоморфных между собой графов (смотри, например, [28, стр.139] или [25, стр. 22]).
При второй точке зрения на обыкновенный граф, описание (задание) связей между элементами множеств V и X можно осуществить с помощью прямоугольной таблицы или матрицы В, номера строк которой совпадают с номерами вершин (номерами элементов множества V), а номера столбцов с номерами ребер (номерами элементов множества X). Элемент Ьц матрицы В равен 1, если вершина Vi (vi Є V) инцидентна ребру Xj (XJ Є X), и равен 0 в противном случае. Построенную таким образом матрицу В называют матрицей инциденций графа. Таким образом, матрица инциденций для графа.
Алгоритм выделения компонент связности обыкновенного графа
Пусть матрица почти разложима по строкам. Тогда существует строка, удаление которой, а также удаление соответствующих ей столбцов, превращает оставшуюся подматрицу в разложимую матрицу ипциденций размерности (п — 1) х mi, где ті равно числу га, уменьшенному на величину строчной суммы удаляемой строки. Удаление строки и соответствующих ей столбцов, соответствует, как отмечалось выше удалению вершины и инцидентных ей ребер. В силу исходного предположения, полученный подграф распадается на два. несвязанных между собой подграфа: G\ и G . Эти подграфы будут также подграфами исходного графа G. Пронумеруем вершины исходного графа следующим образом. Сначала нумеруем вершины графа входящие в подграф G\. Предположим, что число вершин в подграфе G\ равно q—1. Затем присваиваем номер q вершине, которую удаляли. Затем нумеруем оставшиеся вершины графа G, т. е. вершины входящие в подграф (.
Нумерацию ребер производим следующим образом. Начиная с первой вершины, нумеруем произвольным образом ребра инцидентные этой вершине, затем переходим к нумерации еще непронумерованных ребер инцидентных второй вершине и так далее до конца. Матрица инциденций, соответствующая графу G с такой нумерацией вершин и ребер, будет иметь вид (1.3). Матрицы инциденций, соответствующие одному и тому же графу, при различных нумерациях его вершин и ребер будут перестановочно эквивалентны. Следовательно, почти разложимая по строкам матрица инциденций перестановочно эквивалентна матрице вида (1.3).
Достаточность. Пусть матрица инциденций графа имеет вид (1.3). Тогда подматрица, полученная из матрицы (1.3) удалением q-Vi строки и соответствующих ей столбцов, будет иметь вид (1.2). Следовательно, матрица (1.3) почти разложима по строкам. Что и требовалось доказать. Определение 1.6. Матрицу инциденций размерности (n х га) будем называть почти разложимой по столбцам, если она не является разложимой и перестановочно эквивалентна матрице вида Замечание 1.4. В матрице (1.4) среди совокупностей элементов, ровно но одному элементу равно 1, а все остальные элементы равны 0. Теорема 1.5. Обыкновенный -граф распадается на компоненты связности тогда и только тогда, когда его матрица инциденций разложима. Доказательство. Для случая, когда граф имеет изолированные вершины, утверждение теоремы тривиально. Поэтому будем предполагать, что граф не имеет изолированных вершин. Необходимость. Пусть граф распадается на компоненты связности. Объединим компоненты в две группы. Пронумеруем вершины графа следующим образом: сначала нумеруем вершины первой группы компонент, затем, продолжаем нумерацию вершин второй группы компонент. Точно также нумеруем ребра. Очевидно, что в этом случае матрица инциденций графа будет иметь вид (1.2), т. е. является разложимой матрицей. Достаточность. Пусть матрица инциденций графа разложима. Преобразуем ее с помощью перестановки строк и столбцов к виду (1.2). Перенумеруєм вершины и ребра графа в соответствии с номерами строк и столбцов преобразованной матрицы. Тогда преобразованная матрица будет матрицей инциденций исходного графа с измененной нумерацией вершин и ребер. Диагональные (ненулевые) блоки преобразованной матрицы, очевидно, будут матрицами инциденций двух графов, никак между собой несвязанных. Это и означает, что граф распадается на компоненты связности. Что требовалось доказать. Теорема 1.5 . Граф связен тогда и только тогда, когда его матрица инциденций неразложима. (Следствие из теоремы 1.1.) «Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент; ребро с таким же свойством называется мостом. Таким образом, если v - точка сочленения связного графа G, то граф G — v не связен. Неразделимым графом называется связный, непустой, не имеющих точек сочленения граф. Блок графа - это его максимальный неразделимый подграф. Если G -неразделимый граф, то часто он сам называется блоком» [28, стр. 41]. Введенные с помощью цитаты определения позволяют сформулировать достаточно очевидные утверждения: граф G имеет точки сочленения тогда и только тогда, когда его матрица инциденций почти разложима по строкам; аналогично, граф G имеет мосты тогда и только тогда, когда его матрица инциденций почти разложима по столбцам. Таким образом, подграф, образованный столбцом t матрицы инциденций вида (1.4) является мостом, а вершина, соответствующая строке q матрицы инциденций вида (1.3), - точкой сочленения. В таком случае, блокам графа будет соответствовать подграфы, образованные строками {bij,... ,bqj} при j = 1,...,к и {bqj,... ,bnj} при j = (к + 1),..., т матрицы инциденций вида 1.3 и аналогично, строками {bij,... ,Ьц} при j = 1,...,t и строками {&(2+i)j,..., bnj} при j — t,... ,m матрицы инциденций вида 1.4. Теорема 1.6. Если матрица инциденций почти разложима по столбцам, то она является и почти разложимой по строкам. Другими словами, если у графа есть мост, то каждая из его концевых вершин является точкой сочленения. Доказательство. Действительно, пусть матрица инциденций совпадает с матрицей вида (1.3). Тогда не нарушая общности рассуждений можно считать, что ЬЦ = 1 И 6/+І,І = 1, а остальные элементы столбца с номером t равны нулю. Нетрудно видеть, что подматрицы, оставшиеся после удаления строки I или строки / + 1, с соответствующими столбцами, имеют вид (1.2). Что и требовалось доказать. Определение 1.7. Матрицу инциденций, не являющуюся разложимой или почти разложимой по строкам, будем называть неразделимой.
Алгоритм вершинной раскраски обыкновенного графа
Поскольку каждая изолированная вершина в графе является компонентой связности, то в целях упрощения изложения алгоритма будем считать, что исходный граф G не содержит изолированных вершин.
Алгоритм предполагает, что обыкновенный граф G может задаваться не только своей матрицей инциденций В, но и матрицей смежности А. Это делается прежде всего потому, что несмотря на все указанные ранее преимущества матриц инциденций матрица смежности, как правило, более компактная. Более того по матрице смежности легко строится матрица инциденций. В силу предположения об отсутствии у графа G изолированных вершин следует, что ни матрица А, ни матрица В не имеют нулевых строк. Кроме того матрица А как матрица смежности обыкновенного графа является (ОД)-матрицей со свойствами А = А и SpA = 0 (след равен нулю). У (ОД)-матрицы В каждый столбец содержит ровно две единицы, остальные элементы столбца равны нулю. У матрицы В нет одинаковых столбцов (обыкновенный граф не имеет кратных ребер).
Пусть обыкновенный граф задан матрицей смежности А. Тогда по матрице А строим матрицу инциденций В. Слева к матрице В приписываем столбец (1,... ,n) , тем самым сформировав «расширенную» матрицу инциденций, которую также обозначим через В. Под словами «строка it расширенной матрицы инциденций», будем понимать строку матрицы В с элементом ik в первом столбце.
Строим подмножество вершин Д. Берем любую вершину і\ и помещаем ее в Д. Затем берем любую вершину «2 смежную с вершиной ц и помещаем ее также в Д. Вычеркиваем в «расширенной» матрице В строки с номерами Д и %2- Если в оставшейся подматрице нет столбцов с одной единицей, то Д построено. В этом случае Д = {г і, гг}. Если после вычеркивания упомянутых строк появились столбцы с одной единицей, то продолжаем процесс построения Д. Для этого берем любой столбец с одной единицей, которая расположена, например, в строке с номером г з (номер определяется по первому столбцу «расширенной» матрицы инциденции). Заносим номер гз в Д и вычеркиваем строку с номером гз. Если в оставшейся подматрице нет столбцов с одной единицей, то множество Д построено, если есть - процесс построения Д продолжаем дальше. Этот процесс продолжаем до тех пор, пока не исчерпаем все столбцы с одной единицей. В результате этого процесса мы можем прийти к двум возможным исходам. 1. Вычеркнуты все строки «расширенной» матрицы В, т. е. Д = I. Это означает, что граф связен или однокомпоиентен. 2. Процесс оборвался в результате исчерпывания столбцов с одной единицей, причем мощность построенного множества Д меньше п. То есть Д = I п. Подграф с вершинами, номера которых принадлежат Д, будет компонентой связности исходного графа. Матрица инциденции этого графа будет подматрицей матрицы Б, образованной вычеркнутыми строками. Подматрица матрицы В, образованная невычеркну-тыми строками, является матрицей инциденции некоторого другого графа, поскольку столбцы этой матрицы содержат по две единицы. С этой подматрицей начинаем работать как с исходной матрицей, т. е. начинаем строить множество h Q I — h Если І2 ф I — Д, то строим множество із и так далее. На каком-то g-ом шаге мы получим, что / = и Д = Д U ... U Iq при этом Ij П It — 0 при j 7 к. Подматрицы матрицы В с номерами строк принадлежащими множеству Д (к = 1,..., q) будут являться матрицей инциденций соответствующей к-й компоненты связности. Добавляя к этим q компонентам связности, компоненты соответствующие изолированным вершинам, если таковые были в исходном графе, мы получим все компоненты связности исходного графа.
Нулевые столбцы, появляющиеся в подматрицах матрицы инциденций, соответствующих компонентам связности, а также появляющиеся в процессе вычеркивания строк, очевидно ни на что не влияют.
Некоторые связные графы можно сделать несвязными, удалив одну вершину. Напомним, что вершина V( графа G(V, X) является точкой сочленения графа (7, если граф (G — Vi) состоит из большего числа компонент, чем G. Если G связный, то (G — vi) будет содержать по крайней мере две компоненты, т. е. (G — vi) будет несвязным. Согласно этому определению, изолированная вершина не может быть точкой сочленения. Таким образом, пустой граф не имеет точек сочленения.
Если в связном непустом графе не существует точки сочленения, то такой граф называют неразделимым графом, при этом, максимальный неразделимый подграф называют блоком.
Граф G, представленный на рис. 2.4, является разделимым графом, у которого вершины vi, V2 и г з - точки сочленения, а ребро х = {г 2,ъ з} мост; отдельно приведены блоки графа G - В\, ?2, Вз и .Е?4- Следует иметь в виду, что когда речь идет о блоках, то рассматриваются не просто компоненты преобразованного графа.
Общая постановка задачи оптимальной загрузки оборудования
Матрица Р, приводящая матрицу смежности А к виду (3.2), по сути и производит вершинную раскраску соответствующего графа, т. е. осуществляет разбиение множества вершин V на непересекающиеся подмножества V и У таких, что V U V = V.
Определение хроматического числа графа является трудной задачей теории графов. Приведем несколько основных известных результатов, относящихся к хроматическим числам. Из определения ненулевого двудольного графа Gm,n следует, что матрицы перестановок Р и Q, приводящие матрицу инциденций В к виду (3.1), по сути и производит вершинную раскраску соответствующего графа, т. е. осуществляет разбиение множества вершин V на непересекающиеся подмножества V и V таких, что V [J V = V. Тогда можно сделать вывод, что ненулевые двудольные графы и только они являются 2-хроматическими графами, т. е. x{Gm,n) — 2. В частности, заметим, что любое дерево, имеющее не менее двух вершин - двудольный граф, и следовательно, является 2-хроматическим графом (смотри Приложение Б). Очевидно, что только безреберные графы являются 1-хромати-ческими. При этом легко видеть, что х(Кр) = V Для полного графа. Кр. При каких условиях граф является 3-хроматическим, неизвестно, хотя легко привести примеры таких графов; к ним относятся циклические графы с нечетным числом вершин, колеса с нечетным числом вершин, граф Петерсена (смотри Приложение Б). Колеса с четным числом вершин являются 4-хроматическими (смотри Приложение Б). О хроматическом числе произвольного графа мало что можно сказать. Очевидно, что существует r-раскраска графа G = (V, X), V = n для любого г в диапазоне х(С) г п. Заметим, что x(G) г, если граф G = (V,X), \V\ = п содержит в качестве подграфа граф Кг для натурального числа г. Степенью вершины Vi в графе G - обозначается di или degvi -называется число ребер, инцидентных вершине V{. Лемма Если каждый блок связного графа г-раскрашиваем для некоторого г є N, то и сам граф г-раскрашиваем. Вообще говоря, хроматическое число графа нельзя найти, зная только количество вершин и количество ребер графа. Однако при известных величинах п (\V\ = п), т (\Х\ = т) и d\, G , , dn (степени вершин графа) можно получить верхнюю оценку для хроматического числа графа. Теорема(Брукс). [23] Пусть G - связный обыкновенный граф. Если он не цикл нечетной длины и не полный граф, то x{G) А-(Где А - наибольшая из степеней вершин в графе G.) Заметим, что теорема Брукса дает оценку сверху для хроматического числа графа. Однако, эта оценка является достаточно грубой и может быть сколь угодно далека от хроматического числа. Действительно, любое нетривиальное дерево является 2-хроматическим графом, при этом степень вершин графа может быть сколь угодно велика. Аналогично вершинной, реберной раскраской называется присвоение ребрам графа различных цветов таких,что никакие два смежных ребра не получают в ней одинакового цвета. Определение 3.7. Реберной раскраской (или реберной q-раскрас кой) графа G(V, X) называется разбиение множества ребер X на непересекающиеся непустые подмножества ребер Xj (іЛ Х,- = X) таким образом, что ребра, принадлежащие одному подмножеству, являются несмежными.
Как и в случае с вершинной раскраской, при реберной раскраске интересуются в первую очередь раскраской в минимальное число цветов. Минимальное число д, для которого граф G имеет реберную д-раскраску называется хроматическим индексом или реберным хроматическим числом {G) графа G. Граф, представленный на рис. 3.2 имеет хроматический индекс равный 4.
Замечание 3.2. При раскраске Х\:..., Хг каждое множество ХІ (г = 1,... , г) является паросочетанием графа G. Напомним, что паросочетанием графа G называется набор независимых ребер графа, поскольку такой набор определяет разбиение множества вершин графа на пары вершин, инцидентных ребрам набора. Поэтому x {G) можно рассматривать как наименьшее число паросочетаний, на которые разбивается множество ребер графа G.
В общем случае x (G) ф Д, где А - максимальная степень в графе G, тем не менее в случае двудольного графа x (G) = Д. Поскольку в любой раскраске ребра, инцидентные одной вершине, получают разные цвета, то х (С) А.
