Регистрация


Рубрики


Ссылка на сайт:
Аннотация выпускной квалификационной работы бакалавра (магистра) О предписанной (k, l) – раскраске инциденторов мультиграфа

Новосибирский государственный университет

Механико-математический факультет

Кафедра Теоретической кибернетики

Аннотация

выпускной квалификационной работы бакалавра (магистра)

О предписанной (k,l) – раскраске инциденторов мультиграфа

Студент Васильева Екатерина Ильинична
Научный руководитель Пяткин Артем Валерьевич

Дипломная работа посвящена задаче предписанной (k, l) – раскраске инциденторов мультиграфа. Инцидентором в графе G=(V, E) называется пара (u, e), состоящая из вершины u и примыкающего к ней ребра e. Удобно трактовать инцидентор как половину дуги e, примыкающую к вершине u. Правильная раскраска инциденторов называется (k, l) – раскраской, если разность цветов начального и конечного инциденторов лежит между k и l. В предписанном варианте также требуется, чтобы каждый инцидентор лежал в множестве допустимых цветов для данной дуги. Для того, чтобы такая постановка имела смысла, считается, что множество допустимых цветов каждой дуги представляет собой целочисленный интервал. Минимальная длина интервала, при которой предписанная (k, l) – раскраска инциденторов данного мультиграфа всегда существует, называется предписанным инциденторным (k, l) – хроматическим числом, поиску которого и посвящена задача.

В работе впервые сформулирована задача предписанной (k, l) – раскрасие инциденторов мультиграфа. Доказаны общие оценки для предписанного инциденторного (k, l) – хроматического числа в зависимости от степени мультиграфа. На их основе в работе сформулирована гипотеза о значении предписанного инциденторного (k, l) – хроматического числа для любых целых неотрицательных k и l. Гипотеза доказана для мультиграфов степеней 2 и 4.



Пожаловаться

Материал из рубрики: Мои статьи
5
рейтинг рассчитывается на оценке от 1 до 5

Мои другие материалы