|
Прикладная теория автоматов и графов
Уточнение нижней оценки числа дополнительных дуг минимального вершинного $1$-расширения ориентации цепи
М. Б. Абросимов, О. В. Моденова Саратовский государственный университет имени Н. Г. Чернышевского, г. Саратов
Аннотация:
Ранее был получен следующий результат: минимальное вершинное $1$-расширение любой отличной от гамильтоновой ориентации цепи с числом вершин больше 4 содержит по крайней мере четыре дополнительные дуги. В данной работе удалось значительно уточнить эту оценку, а также получить верхнюю оценку на число дополнительных дуг.
Ключевые слова:
минимальное вершинное $1$-расширение, ориентация цепи, отказоустойчивость.
Образец цитирования:
М. Б. Абросимов, О. В. Моденова, “Уточнение нижней оценки числа дополнительных дуг минимального вершинного $1$-расширения ориентации цепи”, ПДМ. Приложение, 2016, № 9, 101–102
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma289 https://www.mathnet.ru/rus/pdma/y2016/i9/p101
|
|