|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 3, страницы 76–81
(Mi da777)
|
|
|
|
О мультираскраске рёбер унициклических графов
А. В. Пяткинab a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
Аннотация:
Мультираскраской рёберно взвешенного графа называется назначение интервалов его рёбрам такое, что интервалы смежных рёбер не пересекаются по внутренним точкам, а длина каждого интервала равна весу ребра. Минимальная длина объединения всех интервалов называется рёберным мультихроматическим числом графа. Очевидной его нижней оценкой является максимальная взвешенная степень вершины, т.е. сумма весов инцидентных ей рёбер. Известны примеры, когда мультихроматическое число в полтора раза превышает нижнюю оценку, и существует гипотеза, что больше оно её превосходить не может. В настоящей работе эта гипотеза доказывается для класса унициклических графов. Библиогр. 4.
Ключевые слова:
рёберная раскраска, мультираскраска, взвешенные графы, интервалы, задача open shop.
Статья поступила: 13.06.2013 Переработанный вариант: 24.07.2013
Образец цитирования:
А. В. Пяткин, “О мультираскраске рёбер унициклических графов”, Дискретн. анализ и исслед. опер., 21:3 (2014), 76–81; J. Appl. Industr. Math., 8:3 (2014), 362–365
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da777 https://www.mathnet.ru/rus/da/v21/i3/p76
|
Статистика просмотров: |
Страница аннотации: | 284 | PDF полного текста: | 72 | Список литературы: | 49 | Первая страница: | 12 |
|