RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Южно-Уральского государственного университета. Серия «Математика. Механика. Физика» // Архив

Вестн. Южно-Ур. ун-та. Сер. Матем. Мех. Физ., 2016, том 8, выпуск 1, страницы 5–12 (Mi vyurm282)

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

Математика

О числе $OE$-цепей для заданной системы переходов

Т. А. Макаровских

Южно-Уральский государственный университет, г. Челябинск, Российская Федерация

Аннотация: Ранее установлено существование $OE$-цепи в плоском эйлеровом графе и предложен алгоритм построения такой цепи. В статье исследуется вопрос о числе $OE$-цепей с системой переходов, индуцируемой отдельной $OE$-цепью и установлено, что верхняя оценка этого числа не превышает удвоенной суммы количества вершин, смежных внешней грани, и суммы степеней разделяющих вершин. Построенная оценка достижима, если система переходов является системой переходов $A$-цепи. Исследован вопрос существования $OE$-цепей, удовлетворяющих произвольной системе переходов.

Ключевые слова: плоский граф; эйлеров цикл; система переходов; $A$-цепь; упорядоченное охватывание.

УДК: 519.178

Поступила в редакцию: 29.06.2015

DOI: 10.14529/mmph160101



Реферативные базы данных:


© МИАН, 2024