Автоматика и телемеханика, № 9, 2013
Анализ данных
© 2013 г. С.В. КУРАПОВ, канд. физ.-мат. наук (Запорожский национальный университет, Украина), А.В. ТОЛОК, д-р техн. наук (Московский государственный технологический университет "Станкин")
МЕТОДЫ ПОСТРОЕНИЯ ТОПОЛОГИЧЕСКОГО РИСУНКА ГРАФА
Рассмотрены алгоритмы для построения топологического рисунка графа на плоскости. Описываемые алгоритмы позволяют хранить, описывать и видоизменять информацию о рисунке графа. Рассмотрены необходимые понятия и структуры для решения задачи топологического построения рисунка графа на плоскости.
1. Введение
Что такое рисунок графа? Как его изобразить на плоскости? Ведь для заданной матрицы смежностей графа можно построить множество рисунков. Например, граф К5 можно представить множеством рисунков (рис. 1,а).
Первые, кто столкнулись с задачей построения рисунка графа на плоскости, были разработчики автоматизированных систем проектирования плоских конструктивов, таких как печатные платы, микросборки, интегральные микросхемы и т.д. Конструктор располагал контакты в виде вершин графа, задавая их геометрические координаты, и после этого начиналось решение задачи проведения соединений. Но если характеризовать соединения прямыми линиями (см. рис. 1,б), то они могут пересекаться, а это недопустимо для электрических соединений. Чтобы избежать пересечения, лучше характеризовать соединения ломаными линиями (см. рис. 1,в). Но как проводить ломаные линии? Решение было найдено с появлением волнового алгоритма Ли [1-5]. В нем вся плоскость проведения соединений разбивалась на клетки определенного размера и последовательно проводились соединения путем распространения волны (см. рис. 1,г). Это метрический способ, так как проведение соединений рассматривалось в некотором пространстве R2 с заданной эвклидовой метрикой. Основные недостатки волнового алгоритма - его большая вычислительная сложность и последовательный характер проведения соединений, так как проведение последующих соединений напрямую зависит от проведения предыдущих. Такой способ не гарантировал оптимального конструкторского решения.
Для устранения недостатков волнового алгоритма Ли создано множество модификаций: лучевые алгоритмы, канальные, магистральные и т.д., что поз-
Рис. 1. а - Различные рисунки графа К5; б - соединения пересекаются; в - соединения не пересекаются; г - проведение соединений алгоритма Ли; д - пересечения соединений двух фрагментов; е - рисунок графа в пространстве; ж - изображение на плоскости.
волило упростить вычисления. На базе волнового алгоритма Ли и его модификаций созданы мощные системы автоматизации проектирования плоских конструктивов, такие как РСЛБ, ОгСЛБ и др.
Последовательный характер проведения соединений и, как следствие, разбиение единого процесса проведения соединений на размещение элементов и трассировку соединений с потерей оптимальности решения не устраивал разработчиков автоматизированных систем проектирования. Это вызвало появление целой серии новых математических подходов к решению поставленной проблемы, которые можно условно назвать топологическими методами, использующими теоретико-множественное представление [6-9].
Одной из первых отечественных публикаций по представлению топологического описания рисунка графа с определением количества пересечений соединений только для двух циклических фрагментов была работа [9].
Авторам настоящей статьи удалось преобразовать задачу построения рисунка графа на плоскости к решению известной задачи теории графов - представлению двудольного графа с минимальным числом пересечения ребер (см. рис. 1,д). Такой подход привел к развитию методов цепочечного построения рисунка графа для определения количества пересечений [2, 6]. Однако вопрос поиска оптимальной цепочки соединений для получения рисунка графа с минимальным числом пересечений ребер остался открытым.
Дальнейшее развитие методов определения пересечений соединений представлено в [10], авторы которой первыми высказали мысль, что при построении рисунка графа анализ отношения пересечения ребер можно производить в топологическом пространстве, где метрические свойства не определены. Авторы [10] разработали основы векторной алгебры пересечений, где для полного и непротиворечивого описания рисунка графа вводится понятие координатно-базисной системы (КБС) и относительно нее устанавливаются проекции всех соединений с целью определения пересечения ребер по их проекциям.
Как правило, такая координатно-базисная система может быть построена относительно любого дерева графа. Несмотря на революционность подхода, ограничения, накладываемые на построение координатно-базисной системы и запрещающие соединениям пересекать базовые векторы КБС, несколько сократили применимость метода. Так как различные деревья порождают разные КБС с разным количеством пересечений соединений, то возникает проблема оптимального, с точки зрения минимального количества пересечений соединений, выбора дерева графа. Выбор такого дерева является сложной задачей, требующей перебора всех деревьев графа и построения рисунков на их основе.
Трудности, связанные с топологическим способом определения пересечений соединений (ребер графа), привели к более тщательному исследованию процесса планаризации и созданию алгоритмов для плоской укладки графа.
Имеется несколько критериев планарности графа, предложенных Л.С. Понтрягиным, К. Куратовским, К. Вайнером, С. Мак-Лейном [11-17]. Критерии планарности таковы, что если даже удалось установить планар-ность графа, то нет информации о том, как строить укладку на плоскости. В то же время при решении практических задач недостаточно знать, что граф планарен, а необходимо построить его плоское изображение. Практическое использование критериев затруднено из-за необходимости полного перебора простых циклов для содержательного рассмотрения графа. Поэтому были разработаны эвристические методы определения планарности. Условно их можно разделить на три класса: циклические, матричные и комбинированные. В [8] приведены ссылки на опубликованные работы по созданию алгоритмов планаризации. Подробно рассмотрены все применяемые типы алгоритмов на тот временной период и указаны их основные недостатки для практического применения.
Один из лучших алгоритмов планаризации разработан Хопкрофтом и Та-рьяном [18], которые нашли алгоритм, требующий O(|N| log |N|) единиц времени и который они, в конечном счете, улучшили до O(|N|), где N - ко-
личество узлов графа. Данный алгоритм проверяет граф на планарность и, если граф планарен, производит его плоскую укладку. Однако этот алгоритм лишь косвенно содержит информацию о рисунке графа, и применение алгоритма затруднительно для дальнейшего решения задачи построения и выделения максимально плоского суграфа из непланарного графа, а также для решения задачи построения рисунка графа с минимальным числом пересечений для непланарного графа.
Опыт построения рисунка графа для электрических соединений был перенесен на другие области деятельности человека, связанные с сетевыми структурами, такие как картография и биоинформатика, биологические науки, искусственный интеллект, анализ финансовой информации, анализ социальных сетей и т.д.
В настоящее время сформировалось новое научное направление, связанное с рисованием графов и визуализацией сетей на компьютере. Основные вопросы, решаемые данным научным направлением, можно сформулировать следующим образом: получить графическое представление укладки графа, направленное на удобное отображение некоторых свойств моделируемого объекта, представленного в виде графа.
В обзорной работе [19] представлена эволюция методов визуализации графов в связи с потребностями практики.
Следует заметить, что понятия "рисование графов" (Graph drawing) и "визуализация графов" (Graph visualization), появившиеся первоначально в англоязычной литературе, отличаются по смыслу. Термин Graph drawing чаще употребляется в контексте теоретических работ по рисованию графов на плоскости, а термин визуализация графов является самостоятельным подмножеством в быстро развивающемся направлении "Визуализация информации". Понятие "визуализация графов" является более широким по отношению к понятию "рисование графов". С алгоритмической точки зрения визуализация графов рассматривает не только проблемы рисования графов, но и вопросы интерактивного взаимодействия с графами, навигацию по очень большим графам, вопросы удобства использования тех или иных изображений графа.
Исторически выделение направления Graph drawing в качестве самостоятельного научного направления принято связывать с первой международной конференцией, которая состоялась в 1992 г. в Риме. С тех пор издательство Springer-Verlag ежегодно публикует в сериях LNCS труды этих конференций, которые содержат новые алгоритмы рисования и визуализации графов, теоретические результаты, касающиеся эффективности этих алгоритмов, а также демонстрации новых систем. Недавно начал издаваться электронный журнал "Journal of Graph Algorithms and Applications", посвященный конструированию и анализу алгоритмов визуализации графов, а также экспериментам и приложениям.
Среди книг, посвященных рисованию графов, следует отметить книгу основоположников этого направления Дж. Ди Батиста, П. Идес, Р. Тамассиа, И. Дж. Толлис. Книги по визуализации информации, использующей методы визуализации графов, более многочисленны (С.К. Кард, Ж.Д. Маккиндлэй, Б. Шнейдэрман и др.) [20-24].
В настоящее время известно большое количество статей, предлагающих разные способы отображения и рассматривающие вопрос о хорошем изображении графа. Для характеристики можно придумать огромное количество разных способов классификации изображений (см. рис. 1,е и 1,ж). Во-первых, изображения графов можно классифицировать в соответствии с типом изображаемого графа. Во-вторых, можно разбить графы на группы. Графы, которые можно нарисовать без пересечений ребер, образуют группу пла-нарных графов. Также принято рассматривать отдельно алгоритмы визуализации деревьев, ориентированных и неориентированных графов и т.д.
Много ограничений
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.