Cтраница 4
Лемма 5.10 Время, требующееся для выполнения поиска в глубину в графе с V вершинами и Е ребрами, пропорционально V Е, если использовать представление графа в виде списков смежности. [46]
Различные представления графов описаны в препринте В. К. Попкова [66], различные представления деревьев - в препринте [67], однако большая их часть имеет лишь теоретический интерес. Заслуживает упоминания представление графов в виде йГ - формул. [47]
Согласно следствию 1, мы уже знаем, что неравенство справедливо. Построим теперь представление графа G и единичный вектор d, для которых выполняется равенство. [48]
В первом параграфе приводятся основные понятия теории бинарных отношений и теории графов. Описываются формы представления графов и экономные процедуры реализации некоторых операций над графами. [49]
Очевидно, что наиболее понятный и полезный для человека способ представления графа - изображение графа на плоскости в виде точек и соединяющих их линий - будет совершенно бесполезным, если мы захотим решать с помощью ЭВМ задачи, связанные с графами. Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов, поэтому мы подробнее остановимся на этой проблеме. Мы покажем несколько различных способов представления и кратко разберем их основные достоинства и недостатки. [50]
При решении различных задач анализа и синтеза сложных сетевых систем, для которых справедливы 1 - й и 2 - й законы Кирхгофа, на определенных этапах решения необходимо иметь информацию либо о системе фундаментальных циклов, либо о множестве главных сечений. В некоторых работах рассмотрено матричное и эквивалентное ему теоретикомножественное представление графа сети и базисных систем некоторых его элементов ( главных сечений, фундаментальных циклов) и приведены алгоритмы взаимосвязи между ними, которые по начальной информации в виде матрицы инциденций Аа или множества узловых пар А позволяют последовательно получить матрицу главных сечений Qa и матрицу фундаментальных циклов 5 а или множеств узловых подмножеств графа А, главных сечений Q и фундаментальных циклов В. [51]
Вектор с, на котором этот минимум достигается, назовем ручкой представления. Пусть 0 ( G) обозначает минимум значений всех представлений графа G. Легко видеть, что этот минимум достигается. Назовем представление оптимальным, если его значение минимально. [52]
Раскрывается роль указателя на запись в обеспечении упорядоченности файла. Ценное свойство связных списков состоит в том, что их можно расширить с целью представления транзитивных графов. [53]