10.10.2011, 22:32
|
|
.
модератор форума
Регистрация: Sep 2003
Адрес: Москва
Сообщений: 4,630
|
Как создать максимально плоский граф G(V)?
Подскажите, пожалуйста, алгоритм создания максимально плоского графа G(V).
Добавлено через 25 часов 30 минут
Максимально плоский граф (на плоскости, граф, в который невозможно добавить ребро без пересечения других ребер) является триангулированным; все его грани образованы тремя вершинами. В том числе и внешняя грань. Построение графа можно начать с единственной внутренней грани, добавляя следующую вершину в неё и разбивая последнюю на три новых грани. Кстати, "Паучки" и им подобное развлекалово являются разряженным плоским графом. Вроде кто-то задавал вопрос как создать граф для этой игры.
|