2 Определения.14.2. Раскраска ребер графа

Пусть G= (V,E) будет графом, а {1,2,3,…,k} – подмножество натуральных чисел («цвета»).

Тогда отображение :E{1,2,3,…,k}называютk-раскраской реберграфаG.

k-раскраска будетправильной, если смежные ребра получают различную окраску.

Граф называется k-реберно-раскрашиваемым, если существует правильная раскраска ребер вkцветов.

Пример

a



a 

c 

 b

 d

1

1

2

2

’(G) = 2

2

1

’(G) = 3



c



b

3

Рис.2.14.2. Реберная раскраска графов

Меры

• ’(G) –реберное хроматическое число или хроматический индекс: минимальное числоk, при котором существует правильнаяk-раскраска ребер графа).

Теорема Визинга

Если (G) – минимальная степень простого графа, то

(G)  ’(G)  (G) +1

Для двудольных графов ’(G) =(G).

Класс сложности

Проблема раскраски ребер в ’(G) цветов являетсяNP-тяжелой, а проблема нахождения’(G) –NP-сложной.

Определения

Пусть fбудет функцией, которая присваивает цвета ребрам графа. Тогда f-раскраской графаGявляется раскраска ребер этого графа, такой, что для каждой вершиныvVпо меньшей мереf(v) ребер, инцидентных вершинеv, раскрашены одним цветом.

Обычная раскраска ребер графа есть специальный случай f-раскраски приf=1 для каждой вершиныvV.

Меры

• ’_f-f-хроматический индекс -минимальное число цветов, необходимое дляf-раскраски графа.

Класс сложности

Проблема нахождения f-раскраски ребер графа являетсяNP-тяжелой, а нахождениеf-хроматического индекса –NP-сложной.

15. Совершенные графы

Определение

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

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

Замечание

Теория совершенных графов началась с работы TiborGallaiв 1958 году.

Теорема о совершенных графах (1972 г.)

Граф будет совершенным тогда и только тогда, когда его дополнение будет совершенным.

Определения

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

Строгая теорема совершенных графов (2002 г.)

Граф будет совершенным тогда и только тогда, когда он является графом Берге.

Семейства совершенных графов

Некоторые наиболее известные семейства совершенных графов:

• двудольные графы;

• реберные графы двудольных графов;

• хордовые графы;

• интервальные графы;

• графы единичного диска;

• расщепляющиеся графы;

• сильные хордальные графы;

• слабые хордальные графы.

Хордовые графы

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

Пример

Интервальные графы

Граф G=(V,E) будетинтервальным графомтогда и только тогда, когда имеется отношение один-к-одному между его вершинами и множеством интервалов на действительной оси, причем вершины графа смежны только тогда, когда интервалы пересекаются.

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

Граф единичного диска

Граф единичного диска является графом, представляющим семейство единичных кругов на евклидовой плоскости. Каждая вершина этого графа представляет круг, а его вершины смежны, если круги пересекают друг друга.

Расщепляющиеся графы

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

Расщепление графа на клику и независимое множество вершин не уникально и встречается у ряда графов. Например, путь a-b-cявляется можно представить тремя способами:

1. клика {a,b} и независимое множество {c};

2. клика {b,c} и независимое множество {a};

3. клика {a} и независимое множество {a,c}.

Для значений числа вершин nбыло высчитано число существующих расщепляющих графов:

n	1	2	3	5	6	7	8	9	10	11	12
Число графов	1	2	4	21	56	164	557	2223	10766	64956	501696

- 27-