RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1983, том 34, выпуск 4, страницы 625–628 (Mi mzm5894)

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

О самонепересекающихся и непересекающихся цепях

С. Б. Белый


Аннотация: Для графов на плоскости вводятся понятия самонепересекающихся и непересекающихся цепей. Доказывается, что для любого эйлерова графа на плоскости существует самонепересекающийся эйлеров цикл. Приводится алгоритм построения самонепересекающегося эйлерова цикла, а также некоторые следствия, в частности – доказательство теоремы о двухцветной раскраске карт. Указывается критерий для существования самонепересекающегося эйлерова орцикла в эйлеровом орграфе. Отмечается, что основной результат переносится на бесконечные графы. Библ. 3 назв.

УДК: 519.1

Поступило: 30.03.1981


 Англоязычная версия: Mathematical Notes, 1983, 34:4, 802–804

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


© МИАН, 2024