М. Б. Абросимов, О. В. Моденова, “О точных оценках числа дополнительных дуг минимального вершинного $1$-расширения турнира”, ПДМ. Приложение, 2015, выпуск 8,страницы 111

Прикладная теория кодирования, автоматов и графов

О точных оценках числа дополнительных дуг минимального вершинного $1$-расширения турнира

М. Б. Абросимов, О. В. Моденова

Саратовский государственный университет им. Н. Г. Чернышевского, г. Саратов

Аннотация: Получены нижняя и верхняя оценки для числа дополнительных дуг минимального вершинного $1$-расширения произвольного турнира. Показывается, что оценки являются точными, и описываются турниры, для которых оценки достигаются.

Ключевые слова: турнир, минимальное вершинное расширение, отказоустойчивость.

УДК: 519.17

DOI: 10.17223/2226308X/8/42