вопрос по графам

[alcoholist]

Пусть $G$ -- связный двусвязный граф на плоскости (остается связным при удалении любой вершины), все грани которого треугольники. Грубо говоря, триангулированный ограниченный кусок плоскости (может быть, с дырками, это неважно) с кусочно-линейной границей.
Показать, что имеется подграф $H\subset G$ с тем же множеством вершин (остовный подграф) такой, что:
1) степени вершин $H$ не превосходят 3
2) $H$ содержит все граничные ребра
3) $H$ связен

Нужен какой-то алгоритм удаления ребер из $H$. Я не могу понять при чем здесь условие "все грани -- треугольники". Казалось бы, выкидывай себе ребра, следя за тем, чтобы граф оставался связным.

[svv]

Вот такой граф. Я назвал его «улыбка таитянки».

Степени красных вершин равны 5. Следовательно, у каждой надо удалить хотя бы два инцидентных ей ребра. Но фиолетовые нельзя удалять, потому что граничные. А если удалить по два синих с каждой стороны, граф станет несвязным.

Видимо, при треугольных гранях такое невозможно.

[sqribner48]

Уважаемый alcoholist
Извините пока писал был добавлен новый рисунок, но все равно мой вопрос про дырки остается в силе.
Пожалуйста объясните мне, что значит "с дырками" и почему это неважно?
Я так понимаю, что дырка -- это грань графа (часть плоскости), ограниченная циклом, имеющим не менее четырех ребер.
Мне кажется условие "все грани -- треугольники" является очень важным, поскольку оно определяет вид графа. Это может быть максимальный внешнеплоский граф, у которого все внутренние грани треугольники, а внешняя грань ограничена циклом длиной $n$ ($n$ -- это число вершин графа).
Или это может быть максимальный плоский граф. Естественно для графов этих двух видов искомые алгоритмы удаления ребер будут разными.
В первом случае достаточно удалить все внутренние ребра, в результате будет получен остовной подграф (цикл) $H\subset G$, удовлетворяющий всем трем условиям.

Цитата:

1) степени вершин $H$ не превосходят 3
2) $H$ содержит все граничные ребра
3) $H$ связен

(Конечно, с алгоритмом придется повозиться)..
Второй случай -- будет еще более сложным...

[alcoholist]

sqribner48 в сообщении #1105649 писал(а):

так понимаю, что дырка -- это грань графа (часть плоскости), ограниченная циклом, имеющим не менее четырех ребер.

Да-да, мне достаточно чтобы грани графа покрывали односвязный кусок плоскости
никаких дырок

[alcoholist]

Нашел алгоритм
Вообще-то крутовато для домашней работы