Русская Википедия:Площадь (визуализация графов)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Другие значения Площадь в задачах визуализации графов — числовая характеристика качества графического представления графа.

Определение характеристики зависит от избранного стиля визуализации. В технике, в которой вершины располагаются на целочисленной решётке, площадь представления может быть определена как площадь наименьшего расположенного параллельно осям ограничивающего прямоугольника для представления, то есть как произведение наибольшей разности координат <math>x</math> двух вершин на наибольшую разность координат <math>y</math> двух вершин. Для других стилей представления, в которых вершины располагаются более свободным образом, представление может быть приведено к масштабу, при котором пара самых близких вершин имеет единичное расстояние, после чего площадь представления может быть определена как наименьший ограничивающий прямоугольник рисунка. Альтернативно, площадь можно определить как площадь выпуклой оболочки представления, опять же, при подходящем масштабеШаблон:Sfn.

Полиномиальные границы

Для нарисованного с прямыми рёбрами планарного графа с <math>n</math> вершинами оптимальной границей площади рисунка в худшем случае будет <math>\Theta(n^2)</math>. Граф вложенных треугольников требует такую площадь независимо от того, как граф вложенШаблон:Sfn, и известны некоторые методы, которые позволяют нарисовать планарные графы с максимум квадратичной площадью представленияШаблон:SfnШаблон:Sfn. Двоичные деревья и деревья ограниченной степени как более общий случай имеют представления с линейной или почти линейной площадью, зависящей от стиля рисункаШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Любой внешнепланарный граф имеет внешнепланарное представление с прямыми отрезками в качестве рёбер и субквадратичной от числа вершин площадьюШаблон:SfnШаблон:Sfn, а если разрешены изломы или пересечения, то внешнепланарные графы имеют представления с почти линейной площадьюШаблон:SfnШаблон:Sfn. Однако представление параллельно-последовательных графов требует площадь, большую произведения <math>n</math> на суперполилогарифмическую величину, даже в случае разрешения рисовать рёбра в виде ломаныхШаблон:Sfn.

Экспоненциальные границы

Некоторые стили представления могут показать экспоненциальный рост площади, так что эти стили могут оказаться пригодными лишь для небольших графов. Примером служит восходящее планарное представление планарных направленных ациклических графов, площадь которых для представления графа с <math>n</math> вершинами может быть пропорциональна <math>2^n</math> в худшем случаеШаблон:Sfn. Даже планарные деревья могут потребовать экспоненциальную площадь, если они нарисованы прямолинейными отрезками, которые сохраняют фиксированный циклический порядок вокруг каждой вершины и должны быть расположены с равными расстояниями вокруг вершиныШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Площадь_(визуализация_графов)&oldid=10602509