Лекция: Совершенные графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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