"Записки научных семинаров ПОМИ"
Том 475, стр. 93-98
Об остовных деревьях без вершин степени 2 в плоских триангуляциях
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский
государственный университет,
Университетский пр. 28,
Старый Петергоф,
198504 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Пусть $G$ -- двусвязный плоский граф на более чем 3 вершинах, все грани которого, кроме, может быть, одной -- треугольники. Доказано, что $G$ имеет остовное дерево без вершин степени 2.
Библ. -- 3 назв.
- Ключевые слова: плоский граф, триангуляция, остовное дерево
[plane graph, triangulation, spanning tree]
Полный текст(.pdf)