RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2014, выпуск 7, страницы 135–137 (Mi pdma176)

Эта публикация цитируется в 2 статьях

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

Шпернерово свойство для многоугольных графов

В. Н. Салий

Саратовский государственный университет, г. Саратов

Аннотация: Конечное упорядоченное множество называется шпернеровым, если среди его максимальных по длине антицепей хотя бы одна составлена из элементов одинаковой высоты. Под многоугольным графом понимается бесконтурный граф, полученный из цикла путём некоторой ориентации его рёбер. В многоугольном графе отношение достижимости вершин является отношением порядка. Таким образом, многоугольный граф можно рассматривать как упорядоченное множество. Найдено необходимое и достаточное условие шпернеровости таких упорядоченных множеств.

Ключевые слова: упорядоченное множество, шпернерово свойство, многоугольный граф, цепь, зигзаг.

УДК: 519.17



© МИАН, 2024