Вершина v дерева T называется шпернеровой вершиной, если входящее дерево T(v), полученное из T ориентацией всех рёбер в направлении к v, обладает шпернеровым свойством: в нём среди наибольших (по числу элементов) подмножеств, состоящих из попарно недостижимых вершин, по крайней мере в одном все вершины равноудалены от v. Приводятся явные способы подсчёта количества шпернеровых вершин в деревьях некоторых типов.
Скачать электронную версию публикации
Загружен, раз: 442
- Title О количестве шпернеровых вершин в дереве
- Headline О количестве шпернеровых вершин в дереве
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(32)
- Date:
- DOI
Ключевые слова
дерево, шпернерова вершина, цепь, звезда, пальма, шеренга, гусеница, кортеж пальм, graph, Sperner vertex, path, star, palm-tree, rank, caterpillar, train of palm-treesАвторы
Ссылки
Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. V. 27. Nu.1. S. 544-548.
Салий В. Н. Шпернерово свойство для многоугольных графов // Прикладная дискретная математика. Приложение. 2014. №7. С. 135-137. и
Салий В. Н. Шпернеровы деревья // Прикладная дискретная математика. Приложение. 2015. №8. С. 124-127.
О количестве шпернеровых вершин в дереве | Прикладная дискретная математика. 2016. № 2(32).
Скачать полнотекстовую версию
Загружен, раз: 1009