2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: вопрос по графам
Сообщение10.03.2016, 22:22 
Аватара пользователя
Изображение
Вот такой граф. Я назвал его «улыбка таитянки».

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

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

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

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

 
 
 
 Re: вопрос по графам
Сообщение10.03.2016, 23:25 
Аватара пользователя
sqribner48 в сообщении #1105649 писал(а):
так понимаю, что дырка -- это грань графа (часть плоскости), ограниченная циклом, имеющим не менее четырех ребер.


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

 
 
 
 Re: вопрос по графам
Сообщение12.03.2016, 11:32 
Аватара пользователя
Нашел алгоритм
Вообще-то крутовато для домашней работы

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group