Под конгруэнцией цепи понимается отношение эквивалентности на множестве её вершин, все классы которого являются независимыми подмножествами. Доказана теорема 1 о количестве всех конгруэнций для m-рёберной цепи. Для заданного связного графа G теорема 2 находит длину наименьшей цепи, факторизующейся на данный граф.
Скачать электронную версию публикации
Загружен, раз: 69
- Title Конгруэнции цепей: некоторые комбинаторные свойства
- Headline Конгруэнции цепей: некоторые комбинаторные свойства
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(16)
- Date:
- DOI
Ключевые слова
quotient-graph, Bell number, equivalence relation, congruence relation, path, число Белла, фактор- граф, отношение эквивалентности, конгруэнция, цепьАвторы
Ссылки
Bellman R. and Cooke K. L. The Konigsberg bridges problem generalized // J. Math. Anal. Appl. 1969. No. 25. P. 1-7.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. С. 227-239.
Duncan B. and Peele R. Bell and Stirling numbers for Graphs // J. Integ. Sequenc. 2009. V. 12. Article 09.7.1.
Карманова Е. О. О конгруэнциях цепей // Прикладная дискретная математика. 2011. № 2(12). С. 96-100.
Мирзаянов М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С.91-95.
Мирзаянов М. Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Вып. 7. Саратов: Изд-во Сарат. ун-та, 2006. С.104-114.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 367 с.
Конгруэнции цепей: некоторые комбинаторные свойства | Прикладная дискретная математика. 2012. № 2(16).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 210