Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




22.04.2021


20.04.2021


19.04.2021


19.04.2021


17.04.2021





Яндекс.Метрика

Интервальное хроматическое число

09.03.2021

Интервальное хроматическое число X<(H) упорядоченного графа H — это минимальное число интервалов, на которое может быть разбит (линейно упорядоченный) набор вершин H так, что никакие две вершины, принадлежащие одному и тому же интервалу, не смежны в H.

Отличие от хроматического числа

Интервальное хроматическое число интересно тем, что оно просто вычисляется. Более того, с помощью простого жадного алгоритма можно эффективно найти оптимальное разбиение набора вершин H на X<(H) независимых интервалов. Это сильно контрастирует с фактом, что для обычного хроматического числа графа даже его аппроксимация является NP-трудной задачей.

Пусть K(H) — хроматическое число упорядоченного графа H. Тогда для любого упорядоченного графа H выполняется неравенство X < ( H ) ⩾ K ( H ) {displaystyle X_{<}(H)geqslant K(H)} .

Следует заметить, что у конкретного графа H и изоморфных ему графов хроматическое число одно и то же, а вот интервальное хроматическое число может отличаться. Оно зависит от упорядочения вершин графа.