Аннотация:
Правильная раскраска инциденторов ориентированного взвешенного мультиграфа называется допустимой, если разность между цветами конечного и начального инциденторов каждой дуги не меньше веса этой дуги. Наименьшее число цветов, необходимое для допустимой раскраски инциденторов, называется инциденторным хроматическим числом мультиграфа. Исследуется задача отыскания инциденторного хроматического числа ориентированного мультиграфа. Доказывается NP-полнота этой задачи. Найдены верхние оценки для инциденторного хроматического числа. Приводится приближённый полиномиальный алгоритм решения задачи с максимальной относительной погрешностью, меньшей 2.
Библ. 7.
Полный текст:
PDF файл (256 kB)