Визуализация графов


Визуализация графов

Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускаются пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.

Проблема визуализации графов встаёт, например, при отображении больших интегральных схем, анализе социальных сетей, в таких областях как картография и биоинформатика.

Содержание

Обзор

Графы, как правило, отображаются графически при помощи точек для представления вершин и отрезков, или ломаных, для отображения рёбер между связанными вершинами. Ориентация ребра (в орграфе) отображается при помощи стрелки. При этом отображение графа не следует путать с самим графом (абстрактной, не геометрической структурой). Для каждого графа существует множество различных способов его отображения. Абстрактно, все они сводятся к способам отображения вершин и рёбер. Более конкретно, важно расположение этих вершин и рёбер, удобство восприятия, использования, стоимость создания и эстетические критерии.

Способы визуализации

Ортогональное отображение графа
Сеточное отображение графа

В связи с большим разнообразием видов графов, существует множество различных способов отображения графов.

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

Можно выделить следующие способы отображения[1]:

  • произвольное;
  • прямолинейное — рёбра представляются отрезками;
  • сеточное;
  • полигональное — для отображения рёбер используются ломаные;
  • ортогональное — рёбра представляются ломаными, отрезки которых — вертикальные или горизонтальные линии
  • планарное;
  • восходящее или низходящее (для ориентированных графов).

Эстетические критерии

Эстетические критерии определяют параметры отображения. Наиболее распространённые среди них[1]:

  • Пересечения: минимизация общего числа пересечений рёбер. В идеале, если это возможно, должно быть получено планарное отображение.
  • Области: минимизация размеров областей.
  • Общая длина рёбер: минимизация суммарной длины всех рёбер.
  • Максимальная длина рёбер.
  • Универсальная длина рёбер: минимизация различий в длинах рёбер.
  • Общее число изгибов: уменьшение общего числа изгибов.
  • Максимальное число изгибов.
  • Угловое разрешение.
  • Характеристическое отношение.
  • Симметрия.

См. также

Примечания

  1. 1 2 Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. 397 p. ISBN 0-13-301615-3.

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Визуализация графов" в других словарях:

  • Визуализация — Египетские иероглифы позволяли интуитивно наглядно описывать понятия …   Википедия

  • ДРАКОН — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/28 сентября 2012. Пока процесс обсуждения не завершён, статью мож …   Википедия

  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф  это совокупность непустого множества вершин и множества пар… …   Википедия

  • Планарный граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим …   Википедия

  • Планарность — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его …   Википедия

  • Плоский граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его …   Википедия

  • Объектный граф — Граф объектный  это совокупность узлов и ребер, соединяющих эти узлы. Объектные графы обеспечивают простой способ учёта взаимных связей в множестве объектов, и не обязательно, чтобы эти связи в точности проецировались в классические связки… …   Википедия

  • Граф объектный — это совокупность узлов и ребер, соединяющих эти узлы. Объектные графы обеспечивают простой способ учета взаимных связей в множестве объектов, и не обязательно, чтобы эти связи в точности проецировались в классические связки объектно… …   Википедия

  • Хемоинформатика — Хемоинформатика  применение методов информатики для решения химических проблем. Сферы приложения хемоинформатики: прогноз физико химических свойств молекул (в частности, липофильности, водорастворимости), свойств материалов,… …   Википедия

  • Mathematica — Тип Сист …   Википедия

Книги

Другие книги по запросу «Визуализация графов» >>