О некоторых свойствах n-последовательносвязной цепи

Роман Эдуардович Шангин

Аннотация


Вводится класс n-последовательносвязных цепей. Рассматриваются области применения n-последовательносвязных цепей, в частности задачи оптимального размещения в дискретных постановках и задачи выбора оптимального поведения в системах, описываемых управляемыми марковскими процессами. Приводятся основные характеристики n-последовательносвязной цепи, такие как число ребер, размер максимальной клики, хроматическое и цикломатическое число и др. Исследуются свойства n-последовательносвязных цепей. Определяются отношения класса n-последовательносвязных цепей к классам совершенных, триангулированных, полных и расщепляемых графов. 

Полный текст:

PDF

Литература


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 Universit¨at Hamburg. – 1961. – Vol. 25. – P. 71–76.




DOI: http://dx.doi.org/10.14529/cmse130111