О некоторых свойствах n-последовательносвязной цепи
Бесплатный доступ
Вводится класс n-последовательносвязных цепей. Рассматриваются области применения n-последовательносвязных цепей, в частности задачи оптимального размещения в дискретных постановках и задачи выбора оптимального поведения в системах, описываемых управляемыми марковскими процессами. Приводятся основные характеристики п-последовательносвязной цепи, такие как число ребер, размер максимальной клики, хроматическое и цикломатическое число и др. Исследуются свойства n-последовательносвязных цепей. Определяются отношения класса n-последовательносвязных цепей к классам совершенных, триангулированных, полных и расщепляемых графов.
Триангулированный граф, хордальный граф, дерево клик, задача вебера, n-последовательносвязная цепь
Короткий адрес: https://sciup.org/147160477
IDR: 147160477
Список литературы О некоторых свойствах n-последовательносвязной цепи
- Panyukov A.V. Polynomial Algorithms to Finite Veber Problem for a Tree Network/A. V. Panyukov, B.V. Pelzwerger//Journal of Computational and Applied Mathematics. -1991. -Vol. 35. -P. 291-296.
- Шангин Р.Э. Детерминированный алгоритм для решения задачи Вебера для n-последовательносвязной цепи/Р.Э. Шангин/XIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям: Труды Всероссийской конференции (Новосибирск, 15-17 октября 2012 г.). URL: http://conf.nsc.ru/ym2012/ru/reportview/137128 (дата обращения 15.10.2012).
- Bender E.A. Almost All Chordal Graphs Split/E.A. Bender, L.B. Richmond, N. C. Wormald//Journal of the Australian Mathematical Society. -1985. -Vol. 38. -P. 214-221.
- McKee T.A. On the Chordality of a Graph/T.A. McKee, E.R. Scheinerman//Journal of Graph Theory. -1993. -Vol. 17. -P. 221-232.
- McKee T.A. Beyond Chordal Graphs/T.A. McKee//Journal of Combinatorial Mathematics and Combinatorial Computing. -1997. -Vol. 23. -P. 21-31.
- Dirac G.A. On Rigid Circuit Graphs/G.A. Dirac//Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg. -1961. -Vol. 25. -P. 71-76.
