Представление - граф
Cтраница 1
Представление графа с помощью структуры смежности позволяет ускорить обследование графа. В просмотре глубины 1 граф предварительно исследуется таким образом, что всегда выбирается ребро, выходящее из вершины, у которой имеются еще не пройденные инцидентные ребра и которую мы достигли позже всех других вершин с таким свойством. [1]
Представление графа матрицей смежности в данном случае оказывается для нас очень удобным: число вершин, разделяющих i - ю и - ю, равно просто скалярному произведению i - й и у - й строк матрицы U. Если вершины находятся друг от друга дальше, чем на расстоянии 2, произведение будет равно нулю. [2]
Оба представления графа являются массивами более простых структур данных ( по одной для каждой вершины), которые описывают ребра, связанные с данной вершиной. Для матрицы смежности более простая структура данных реализована в виде индексированного массива, а для списка смежности - в виде связного списка. [3]
Для представления графов мы пользовались диаграммами, на которых точки или кружки изображали вершины, а прямолинейные отрезки или дуги кривых - ребра. Такие диаграммы очень удобны при исследовании свойств отдельных графов. Естественно поэтому спросить, что это на самом деле означает - представить граф с помощью диаграммы, и всякий ли граф может быть представлен таким образом. Читателю, которому нравится рисовать картинки и которого нисколько не беспокоит обоснование этого занятия, достаточно будет узнать, что он все делает правильно. [4]
Всякое представление графа связано с тем или иным обозначением ( нумерацией) вершин и ребер. [5]
 |
Фрагмент сводного графа расчета показателей по уровням объекта управления. [6] |
Форма представления графа ( и соответственно вычислительная сложность) расчета показателей существенным образом зависит от структуры представления ЭММ предметной области. В целях обеспечения эффективной схемы вывода в ряде случаев существующие формулы расчета экономических показателей ( применяемые на практике) формализуются так, чтобы их выбор не зависел от конкретных значений каких-либо параметров. [7]
 |
Граф организационной структуры сводного статистического. [8] |
Задача представления графа G в памяти машины сводится к записи отдельного его элемента с последующим объединением всех элементов в общую систему, называемую словарем структур. [9]
Кроме альтернативного представления графов фиксированных комбинаторов, направляющие также дают нам понимание того, как функция трансляции comb из разд. Коротко говоря, функция трансляции удаляет ( абстрагирует) переменные из выражений, оставляя после себя что-то вроде маршрутной карты, закодированной в форме комбинаторов, которая описывает, как входящий аргумент может быть передан обратно в первоначальную позицию ( или позиции) абстрагированной переменной. Таким образом, из практики становится ясно, почему только фиксированное число комбинаторов является теоретически необходимым: существует только фиксированное множество путей, выходящих из каждой вершины графа. Более того, появляется интуитивное понимание оптимизаций из разд. В и С: если мы посылаем аргумент по обеим ветвям - вершины ( S) и затем в одной из ветвей отбрасываем его ( К), то в качестве оптимизации его вообще можно не посылать по ветви К, а вместо этого направить аргумент только туда, где он необходим. [10]
Определенное выше представление графа приводит еще к одному инварианту. [11]
Требуется найти представление графа G ( V) с минимальным числом пересечений. Искомое представление должно задавать взаимное размещение элементов и возможную последовательность их соединения. Список соединений U представляет собой совокупность множеств [ / /, задающих ветви электрической цепи. [12]
Требуется найти представление графа G ( V) с минимальным числом пересечений. Искомое представление должно задавать взаимное размещение элементов и возможную последовательность их соединения. Список соединений U представляет собой совокупность множеств Ui, задающих ветви электрической цепи. [13]
В этом представлении графа, изображенного на рис. 3.14, применен массив списков. Необходимое для данных пространство пропорционально сумме количеств вершин и ребер. Для поиска индексов вершин, присоединенных к данной вершине i, анализируется i-тая позиция массива, содержащая указатель связного списка, который содержит по одному узлу для каждой присоединенной к i вершины. [14]
Таким образом, представление графа различными методами создает альтернативные возможности расхода пространства. При небольшом количестве ребер ( такой граф называется разреженным), представление /: использованием списков смежности потребует намного меньшего размера пространства. Если большинство пар вершин соединены ребрами ( такой граф называется насыщенным), использование матрицы смежности предпочтительнее, поскольку оно не связано со ссылками. [15]
Страницы: 1 2 3 4