인접 행렬 - Adjacency matrix

에서는 그래프 이론컴퓨터 과학 , 인접 행렬 A는 정방 행렬 유한 나타내는 데 사용되는 그래프 . 행렬의 요소는 한 쌍의 여부를 나타내는 정점 있는 인접 그래프의 여부.

유한 단순 그래프 의 특별한 경우 , 인접 행렬은 대각선에 0 이있는 (0,1)- 행렬입니다 . 그래프가 방향지정되지 않은 경우 (즉 모든 모서리 가 양방향 인 경우) 인접 행렬은 대칭 입니다. 그래프와 인접 행렬 고유 값고유 벡터 간의 관계 스펙트럼 그래프 이론 에서 연구됩니다 .

그래프의 인접 행렬은 정점-가장자리 쌍이 입사 하는지 여부를 요소가 나타내는 다른 행렬 표현 인 발생 행렬각 정점 정도대한 정보를 포함하는 차수 행렬구별되어야합니다 .

정의

정점 세트 간단한 그래프를 들어 U = { u는 1 , ..., U N은 } 인접성 매트릭스는 정사각형 N × N 행렬 그 소자되도록 IJ는 정점에서의 에지가있는 경우 하나를 U 정점 u는 j , 가장자리가 없으면 0입니다. [1] 행렬의 대각선 요소는 모두 0 입니다. 단순한 그래프 에서는 꼭지점에서 자신까지의 가장자리 ( 루프 )가 허용되지 않기 때문입니다. 대수 그래프 이론 에서 0이 아닌 요소를 대수 변수로 대체하는 것도 때때로 유용 합니다. [2]동일한 개념을 해당 행렬 요소에있는 각 두 정점 사이의 가장자리 수를 저장하고 0이 아닌 대각선 요소를 허용함으로써 루프가있는 다중 그래프 및 그래프 로 확장 할 수 있습니다 . 루프는 일관된 규칙을 따르는 한 한 번 (단일 가장자리) 또는 두 번 (두 개의 정점 가장자리 발생)으로 계산 될 수 있습니다. 무 방향 그래프는 종종 루프를 두 번 계산하는 후자의 규칙을 사용하는 반면, 방향성 그래프는 일반적으로 전자 규칙을 사용합니다.

이분 그래프

두 부분이 rs 꼭지점 을 갖는 이분 그래프 의 인접 행렬 A다음 형식으로 작성할 수 있습니다.

여기서 Br × s 행렬이고 0 r , r0 s , sr × rs × s 0 행렬을 나타냅니다 . 이 경우 작은 행렬 B 는 그래프를 고유하게 나타내며 A 의 나머지 부분은 중복으로 버릴 수 있습니다. B 는 때때로 biadjacency matrix 라고도합니다 .

형식적하자 G =이 ( U는 , V는 , E는 )분형 그래프 부분과 U는 = { u는 1 , ..., u는 r에 }, V = { V 1 , ..., V (S) } 및 에지 전자 . biadjacency 행렬은 r × s 0–1 행렬 B 입니다. 여기서 b i , j = 1 인 경우 ( u i , v j )E .

경우 G는 분형 인 다중 그래프 또는 가중 그래프 다음 요소 B 나, j는 꼭지점 또는 에지의 무게 사이의 에지들의 개수로 찍은 ( U I , V의 J ) 각각.

이분 그래프의 인접 행렬은 완전히 단일 모듈 입니다. 이것은 모든 제곱 부분 행렬의 행렬식이 −1, 0 또는 +1임을 의미합니다.

변형

간단한 그래프 의 An ( a , b , c )- 인접 행렬 AA i , j = a if ( i , j ) 가 간선이고 b 가 아닌 경우 b , 대각선에서 c습니다 . 델 인접성 매트릭스 A는 (-1, 1, 0) -adjacency 행렬. 이 행렬은 강하게 규칙적인 그래프두 개의 그래프 를 연구 하는 데 사용 됩니다 . [삼]

거리 행렬 위치에 보유 ( I , J ) 의 정점 사이의 거리가 v에 난을 하고 브이 J . 거리는 정점을 연결하는 최단 경로의 길이입니다. 가장자리 길이가 명시 적으로 제공되지 않는 한 경로의 길이는 경로의 가장자리 수입니다. 거리 행렬은 인접 행렬의 높은 거듭 제곱과 비슷하지만 두 정점이 연결되어 있는지 여부 (즉, 부울 값 을 포함하는 연결 행렬) 만 알려주는 대신 이들 사이의 정확한 거리를 제공합니다.

무 방향 그래프

The convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2.[4] This allows the degree of a vertex to be easily found by taking the sum of the values in either its respective row or column in the adjacency matrix.

Labeled graph Adjacency matrix
6n-graph2.svg


Coordinates are 1–6.

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg


Nauru graph

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg


Coordinates are 0–23.
White fields are zeros, colored fields are ones.

Directed graphs

The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that

  1. a non-zero element Aij indicates an edge from i to j or
  2. it indicates an edge from j to i.

전자의 정의는 일반적으로 그래프 이론 및 소셜 네트워크 분석 (예 : 사회학, 정치학, 경제학, 심리학)에 사용됩니다. [5] 후자는 다른 응용 과학 (예 : 동적 시스템, 물리학, 네트워크 과학)에서 더 일반적입니다. 여기서 A 는 때때로 그래프에서 선형 역학을 설명하는 데 사용됩니다. [6]

첫 번째 정의를 사용하면 해당 열의 항목을 합산하고 해당 행의 항목을 합산하여 꼭지점의 이탈도를 합산하여 꼭지점 in-degrees 를 계산할 수 있습니다. 두 번째 정의를 사용할 때 정점의 in-degree는 해당 행 합계로 제공되고 out-degree는 해당 열 합계로 제공됩니다.

레이블이있는 그래프 인접 행렬
Symmetric group 4; Cayley graph 4,9; numbers.svg


Directed Cayley graph of S4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg


Coordinates are 0–23.
As the graph is directed, the matrix is not necessarily symmetric.

Trivial graphs

The adjacency matrix of a complete graph contains all ones except along the diagonal where there are only zeros. The adjacency matrix of an empty graph is a zero matrix.

Properties

Spectrum

The adjacency matrix of an undirected simple graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph.[7] It is common to denote the eigenvalues by

The greatest eigenvalue is bounded above by the maximum degree. This can be seen as result of the Perron–Frobenius theorem, but it can be proved easily. Let v be one eigenvector associated to and x the component in which v has maximum absolute value. Without loss of generality assume vx is positive since otherwise you simply take the eigenvector , also associated to . Then

For d-regular graphs, d is the first eigenvalue of A for the vector v = (1, …, 1) (it is easy to check that it is an eigenvalue and it is the maximum because of the above bound). The multiplicity of this eigenvalue is the number of connected components of G, in particular for connected graphs. It can be shown that for each eigenvalue , its opposite is also an eigenvalue of A if G is a bipartite graph.[8] In particular −d is an eigenvalue of bipartite graphs.

The difference is called the spectral gap and it is related to the expansion of G. It is also useful to introduce the spectral radius of denoted by . This number is bounded by . This bound is tight in the Ramanujan graphs, which have applications in many areas.

Isomorphism and invariants

가정 두 방향 또는 무향 그래프 G 1G 2 인접와는 행렬 12에 나타내었다. G 1G 2 는 다음 같은 순열 행렬 P 가있는 경우에만 동형 입니다.

특히 A 1A 2유사 하므로 최소 다항식 , 특성 다항식 , 고유 값, 행렬식추적이 동일 합니다. 따라서 이들은 그래프의 동형 불변의 역할을 할 수 있습니다. 그러나 두 그래프는 동일한 고유 값 집합을 가질 수 있지만 동형이 아닐 수 있습니다. [9] 이러한 선형 연산자등분 광 이라고합니다 .

매트릭스 파워

If A is the adjacency matrix of the directed or undirected graph G, then the matrix An (i.e., the matrix product of n copies of A) has an interesting interpretation: the element (i, j) gives the number of (directed or undirected) walks of length n from vertex i to vertex j. If n is the smallest nonnegative integer, such that for some i, j, the element (i, j) of An is positive, then n is the distance between vertex i and vertex j. This implies, for example, that the number of triangles in an undirected graph G is exactly the trace of A3 divided by 6. The adjacency matrix can be used to determine whether or not the graph is connected.

Data structures

The adjacency matrix may be used as a data structure for the representation of graphs in computer programs for manipulating graphs. The main alternative data structure, also in use for this application, is the adjacency list.[10][11]

Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only |V|2/8 bytes to represent a directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately |V|2/16 bytes to represent an undirected graph. Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all n-vertex graphs.[12] For storing graphs in text files, fewer bits per byte can be used to ensure that all bytes are text characters, for instance by using a Base64 representation.[13] Besides avoiding wasted space, this compactness encourages locality of reference. However, for a large sparse graph, adjacency lists require less storage space, because they do not waste any space to represent edges that are not present.[11][14]

An alternative form of adjacency matrix (which, however, requires a larger amount of space) replaces the numbers in each element of the matrix with pointers to edge objects (when edges are present) or null pointers (when there is no edge).[14] It is also possible to store edge weights directly in the elements of an adjacency matrix.[11]

공간 절충 외에도 서로 다른 데이터 구조는 서로 다른 작업을 용이하게합니다. 인접 목록에서 주어진 정점에 인접한 모든 정점을 찾는 것은 목록을 읽는 것만 큼 간단하며 이웃 수에 비례하는 시간이 걸립니다. 인접 행렬을 사용하는 경우 전체 행을 대신 스캔해야하므로 전체 그래프의 정점 수에 비례하여 더 많은 시간이 걸립니다. 반면, 주어진 두 정점 사이에 가장자리가 있는지 여부를 테스트하는 것은 인접 행렬을 사용하여 한 번에 결정할 수 있으며 인접 목록이있는 두 정점의 최소 정도에 비례하는 시간이 필요합니다. [11] [14]

또한보십시오

참고 문헌

  1. ^ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p. 7.
  2. ^ Harary, Frank (1962), "The determinant of the adjacency matrix of a graph", SIAM Review, 4 (3): 202–210, Bibcode:1962SIAMR...4..202H, doi:10.1137/1004057, MR 0144330.
  3. ^ Seidel, J. J. (1968). "Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3". Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6.
  4. Shum, Kenneth; 블레이크, 이안 (2003-12-18). "그래프 및 코드 확장" . 이산 수학 및 이론적 컴퓨터 과학의 DIMACS 시리즈 68 권 . 대수 코딩 이론 및 정보 이론 : DIMACS 워크숍, 대수 코딩 이론 및 정보 이론. 미국 수학 학회. 피. 63.
  5. Borgatti, Steve; 에버렛, 마틴; Johnson, Jeffrey (2018), 소셜 네트워크 분석 (2 판), SAGE, p. 20
  6. Newman, Mark (2018), Networks (2nd ed.), Oxford University Press, p. 110
  7. Biggs (1993) , Chapter 2 ( "그래프의 스펙트럼"), pp. 7–13.
  8. ^ Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartite graphs", Spectra of Graphs, Universitext, New York: Springer, pp. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR 2882891
  9. ^ Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164
  10. ^ Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."
  11. ^ a b c d Cormen, Thomas H .; Leiserson, Charles E .; Rivest에, 로널드 L. ; Stein, Clifford (2001), "섹션 22.1 : 그래프 표현", Introduction to Algorithms (Second ed.), MIT Press 및 McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7 .
  12. Turán, György (1984), "그래프의 간결한 표현", Discrete Applied Mathematics , 8 (3) : 289–294, doi : 10.1016 / 0166-218X (84) 90126-4 , MR 0749658 .
  13. ^ McKay, Brendan , graph6 및 sparse6 인코딩 설명 .
  14. ^ a b c Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363.

External links