Cтраница 3
Напишите подробный алгоритм обхода в глубину, использующий представление графа с помощью списка примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку. Проверьте алгоритм на примерах графов, приведенных в этом разделе, и убедитесь, что он дает те же результаты. [31]
Напишите подробный алгоритм обхода по уровням, использующий представление графа с помощью списка примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку. Проверьте алгоритм на примерах графов, приведенных в этом разделе, и убедитесь, что он дает те же результаты. [32]
В этом разделе обсуждаются различные структуры данных для представления графов. [33]
Следовательно, требования конкретной задачи и определяют способ представления графов и выбор основного правила алгоритма. [34]
В технике печатного монтажа электрических схем возникает задача о представлении графа в виде объединения наименьшего числа его плоских частичных графов. Эту задачу Уэйсман [215] сводит к следующему обобщению проблемы правильной раскраски вершин. Метод нахождения решений основан на булевой алгебре; при этом необходим перебор пустых подграфов данного графа, однако, оказывается, можно ограничиться далеко не полным перебором, что существенно улучшает эффективность метода. [35]
Завершается сборник статьями: Фрактальность квазикристаллической мозаики Ценроуза в представлении древесных графов Кейли ( В.В. Юдин и соавторы), Апериодические структуры, фрактальные образы чисел ( А.И. Лазарев и соавторы), Формирование структуры полимеров при твердофазной экструзии ( В.З. Алоев и соавторы) и Использование представлений фрактальной геометрии при изучении кинетики растворения оксидов металлов в кислых средах ( ИХ. Горичев и соавторы), в которых авторы рассматривают различные области применения концепции фракталов. [36]
Если известно, что данное комбинаторное свойство выполняется в симметричном представлении графа наименьшего порядка, использованном для разбиения множества, а также в соответствующем подмножестве семейства его непосредственных потомков ( чтобы быть уверенным в том, что правила симметричного построения позволяют последовательное расширение исходного подмножества с сохранением комбинаторного свойства), то оно выполняется для произвольного потомка. [37]
Очевидно, что наиболее понятный и полезный для человека способ представления графа - изображение графа на плоскости в виде точек и соединяющих их линий - будет совершенно бесполезным, если мы захотим решать с помощью ЭВМ задачи, связанные с графами. Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов, поэтому мы подробнее остановимся на этой проблеме. Мы покажем несколько различных способов представления и кратко разберем их основные достоинства и недостатки. [38]
Эффективность программ решения задач на графах и сетях во многом зависит от представления графа в оперативной памяти ЭВМ. [39]
Для отображения коммутационной схемы в ЭВМ применяется как матричное, так и списочное представления рассмотренного графа. [40]
Временная сложность алгоритмов 2.1 и 2.2 зависит от структуры данных, используемой для представления графов, и от механизма расстановки меток и построения списочного расписания. Матричное представление содержит 0 ( п) элементов, следовательно, требуется 0 ( п2) времени, чтобы выяснить, какие элементы матрицы являются ненулевыми. Поэтому представление леса в виде матрицы нецелесообразно, так как он содержит 0 ( п) ребер. [41]
Говоря о языке описания схем Янова, нам может показаться необходимым предложить некоторое текстовое представление графа переходов. Автор, однако, в этом месте хочет показать читателю, что можно применять понятие языка не так уж буквально и, где возможно, трактовать конструктивные объекты как абстрактные, а где нужно, использовать другие наглядные формы представления объектов, нежели текстуальное. [42]
Одной из важных задач, решаемых на этапе конструкторского синтеза, является задача представления графа микромодульной схемы в плоском виде, а также задача минимизации числа пересечений межмодульных соединений. [43]
Если - каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер. [44]
Для ознакомления с дополнительными примерами составных структур данных и выяснения различий между индексированными и связными структурами данных рассмотрим структуры данных, применяемые для представления графов. [45]