RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2013, том 415, страницы 91–102 (Mi znsl5689)

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

Оснащения максимальных деревьев парами хорд

Ю. В. Масловаa, В. М. Нежинскийbc

a ООО "Август", Ленинский пр., 140, Санкт-Петербург, Россия
b С.-Петербургский государственный университет, Университетский пр. 28, Петродворец, 198504 Санкт-Петербург, Россия
c Российский государственный педагогический университет им. А. И. Герцена, наб. р. Мойки, 48, 191186 Санкт-Петербург, Россия

Аннотация: Найдены достаточные условия того, чтобы в конечном связном графе существовало максимальное дерево, обладающее следующим свойством. Существуют нумерация ребер дерева и инъективное отображение множества ребер дерева в множество пар различных хорд ($=$ ребер графа, не содержащихся в дереве), такие, что для любой пары ребер из образа этого отображения циклы, содержащие по хорде из этой пары и не содержащие других хорд, пересекаются по ребру из прообраза и, быть может, другим ребрам (дерева), но только с меньшими номерами. Задача изучения графов, обладающих этим свойством, возникла при решении задачи (изотопической) классификации вложений графов в трехмерное пространство. Библ. – 3 назв.

Ключевые слова: граф, ветвь, хорда, элементарный цикл, оснащение вершины.

УДК: 519.17+515.162.8

Поступило: 01.09.2012


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2016, 212:5, 577–583

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


© МИАН, 2024