Русская Википедия:Минимизация изломов
При визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой)Шаблон:Sfn или общее число изломов на рисункеШаблон:Sfn. Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величиныШаблон:SfnШаблон:Sfn.
Исключение изломов
Классическим примером минимизации изломов служит теорема Фари, утверждающая, что любой планарный граф можно нарисовать без изломов, то есть можно найти планарное вложение графа, в котором все рёбра будут представлены отрезкамиШаблон:Sfn.
Представление графа, в котором рёбра не имеют изломов и параллельны осям, иногда называется прямоугольным представлением и является одним из вариантов представления Шаблон:Не переведено 5, в котором все пересечения рёбер происходят под прямым угломШаблон:Sfn. Однако определение, имеет ли планарный граф прямоугольное преставление, является NP-полной задачейШаблон:Sfn. NP-полной задачей является также определение, имеет ли произвольный граф прямоугольное представление при допущении пересечений рёберШаблон:Sfn.
Минимизация изломов
Тамассиа показал, что минимизация изломов ортогонального рисунка планарных графов, в котором вершины размещаются в узлах целочисленной решётки а рёбра рисуются в виде ломаных, состоящих из отрезков, параллельных осям, может быть осуществлена за полиномиальное время путём перевода задачи в задачу поиска потока минимальной стоимостиШаблон:SfnШаблон:Sfn. Однако если изменить способ вложения планарного графа, задача минимизации изломов становится NP-полной и должна решаться методами, такими как целочисленное программирование, которое не гарантирует одновременность получения точного решения и быстрой скорости работыШаблон:Sfn.
Несколько изломов на ребро
Многие стили рисования графов позволяют изломы, но в ограниченном виде — сложность кривой этих представлений (максимальное число изломов на одно ребро) ограничивается некоторой константой. Разрешение этой константе подрасти может быть использовано для улучшения других характеристик рисунка, таких как площадьШаблон:Sfn. В некоторых случаях стиль может оказаться возможным только при разрешении изломов. Например, не всякий граф имеет Шаблон:Не переведено 5 без изломов, или со сложностью кривой два, но любой граф имеет такой рисунок со сложностью кривой триШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
