2015-06-24
2689
Аналитическое представление – это задание графа с помощью некоторого конечного набора символов, в отличие от рисунка – объекта с континуальным носителем.
Способ задания графа для теоретического изучения его – вопрос чисто личных привязанностей. Но не так это для программистов. — Различные представления графов в компьютере требуют различных объёмов памяти и различаются скоростью выполнения операций (это связано с количеством обращений к памяти и объемом извлекаемой из памяти информации за один запрос). Поэтому различные представления графов приводят к существенной разнице во времени при решении достаточно сложных задач на графах.
От аналитического представления графа можно потребовать следующих свойств:
1) различимость – два разных графа должны обладать разными представлениями (это свойство необходимо);
2) изоморфные графы должны иметь одно и то же представление (это в идеале, в реальности более слабое условие – представления изоморфных графов должны отличаться минимально в некотором смысле);
3) минимальная сложность представления (это уже сильно зависит от задачи);
4) другие – определяемые задачей.
Пусть граф G имеет n вершин и m ребер. Далее приводятся наиболее употребительные способы задания графов с указанием характеристики O (m,n) – объёма памяти для каждого представления.
В качестве примера будем рассматривать два графа: А – простой и В – ориентированный:
