adjacency

The adjacency list representation of a digraph requires storage proportional to sum of the number of vertices plus the number of arcs; it is often used when the number of arcs is much less than n2.

Представление орграфа с помощью списков смежности требует для хранения объем памяти, пропорциональный сумме количества вершин и количества дуг. Если количество дуг имеет порядок 0(n), то и общий объем необходимой памяти имеет такой же порядок.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

Indeed, with a given graph, adequately labeled, there are associated several matrices, including the adjacency matrix, incidence matrix, cycle matrix, and cocycle matrix.

Действительно, с данным графом, помеченным соответствующим образом, связаны несколько матриц, в том числе матрица смежностей, матрица инциденций, матрица циклов и матрица коциклов.

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

Sometimes a labeling is irrelevant, as in the following results which interpret the entries of the powers of the adjacency matrix.

Иногда выбор конкретной нумерации вершин графа не существен, как, например, в следующих результатах, в которых дается интерпретация элементов степеней матрицы смежностей.

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

(This is defined just as for graphs in Chapter 2, except that adjacency is directed.)

(В гл. 2 такое же определение дано для графов, только здесь у нас ориентированная смежность.)

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

linked adjacency lists, and

связанных списков смежности;

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

Constructing the augmenting path graphs for a given matching takes 0(e) time if we use an adjacency list representation for edges.

Если используются списки смежности для представления ребер, то на построение графа чередующейся цепи потребуется времени порядка 0(e).

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

The adjacency matrix

Матрица смежностей

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

For example, if adjacency lists are used to represent the graph, then an index is really a position on the adjacency list for v.

Например, если для представления орграфа используются списки смежности, то индекс — это позиция в списке смежности вершины v.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

Let A be the adjacency matrix of the line digraph of a complete symmetric digraph.

Пусть А —матрица смежностей реберного орграфа полного симметрического орграфа.

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

Characterize the adjacency matrix of a bipartite graph.

Охарактеризовать матрицу смежностей двудольного графа.

Harary, Frank / Graph TheoryХарари, Фрэнк / Теория графов

Теория графов

Харари, Фрэнк

© Едиториал УРСС. 2003

Graph Theory

Harary, Frank

© 1969 by Addison-Wesley Publishing Company, Inc.

Adjacency list representations of the transition function provide more compact implementations, but access to a given transition is slower.

Представление функции переходов в виде списка более компактно, правда, в данном случае замедляется доступ к переходам.

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey / Compilers: Principles, Techniques, and ToolsАхо, Альфред В.,Ульман, Джеффри,Сети, Рави / Компиляторы: принципы, технологии, инструменты

Компиляторы: принципы, технологии, инструменты

Ахо, Альфред В.,Ульман, Джеффри,Сети, Рави

© Addison-Wesley Publishing Company, Inc., 1985

© 2001

© Издательский дом "Вильямс", 2001

Compilers: Principles, Techniques, and Tools

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey

© 2001 by PEARSON EDUCATION NORTH ASIA LIMITED and PEOPLE'S POSTS & TELECOMMUNICATIONS PUBLISHING HOUSE

© 1986