"Записки научных семинаров ПОМИ"
Том 415, стр. 91-102
Оснащения максимальных деревьев парами хорд
Ю. В. Маслова, В. М. Нежинский
ООО ``Август'',
Ленинский пр., 140,
Санкт-Петербург, Россия
yuliapetrova@mail.ru
С.-Петербургский государственный университет,
Университетский пр. 28, Петродворец,
198504 Санкт-Петербург, Россия; Российский
государственный
педагогический университет
им. А. И. Герцена, наб. р.
Мойки, 48, 191186 Санкт-Петербург, Россия
nezhin@pdmi.ras.ru
- Аннотация:
Найдены достаточные условия того, чтобы в конечном связном графе
существовало максимальное дерево, обладающее следующим свойством.
Существуют нумерация ребер дерева и инъективное отображение
множества ребер дерева в множество пар различных хорд (= ребер графа, не
содержащихся в дереве), такие, что для любой пары ребер из образа этого
отображения циклы, содержащие по хорде из этой пары и не содержащие других
хорд, пересекаются по ребру из прообраза и, быть может, другим ребрам
(дерева), но только с меньшими номерами. Задача изучения графов,
обладающих этим свойством, возникла при решении задачи (изотопической)
классификации вложений графов в трехмерное пространство.
Библ. -- 3 назв.
- Ключевые слова:граф, ветвь, хорда, элементарный цикл, оснащение вершины
[graph, branch, chord, elementary cycle, framing of a vertex]
Полный текст(.pdf)