“This is the 29th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

@TOC

preface

Hello! Friend!!! ଘ(੭, ᵕ)੭ Nickname: Haihong Name: program monkey | C++ player | Student profile: Because of C language, I got acquainted with programming, and then transferred to the computer major, and had the honor to win some state awards, provincial awards… Has been confirmed. Currently learning C++/Linux/Python learning experience: solid foundation + more notes + more code + more thinking + learn English! Machine learning small white stage article only as their own learning notes for the establishment of knowledge system and review know why!

series

Graph theory (1) : The basic concepts of graphs

1.3 Matrix representation of figure

1.3.1 Adjacency matrix

Adjacency matrix of an undirected graph

Let G=(V,E)G=(V,E)G=(V,E) G=(V,E) is an undirected graph, V={ν1,ν2… That argument n} V = \ {\ nu_1 \ nu_2,… , \ nu_n \} V = {argument 1, argument, 2,… , argument n}, GGG adjacency matrix of A = (aij) n * nA = (a_ {ij}) _ {n * n} A = n * n (aij), one of them

M, if \nu_i and \nu_j have m edges \\ 0, \nu_i and \nu_j are not adjacent \end{cases}

Note: Loop count twice

For example,

When the graph is simple (no loops, no double edges)When the graph contains rings

summary

  • The adjacency matrix of an undirected graph is a symmetric square matrix
  • The sum of each row or column of elements in the adjacency matrix of an undirected graph is the number of corresponding vertices
  • If the undirected graph is a simple graph, then its adjacency matrix is a symmetric (0,1) matrix and the diagonal elements are all 0

The adjacency matrix of a directed graph

Let D=(V,E)D=(V,E)D=(V,E) D=(V,E)D=(V,E) is a digraph, V={ν1,ν2… That argument n} V = \ {\ nu_1 \ nu_2,… , \ nu_n \} V = {argument 1, argument, 2,… ,νn}, then DDD adjacentmatrix A=(aij)n×nA=(a_{ij})_{n× N}A=(aij)n×n, where AIj =ma_{ij}=maij=m, meaning ν I \nu_iν I pointing to vjv_jvj arc has MMM, MMM can be 0

The adjacency matrix of the digraph is not necessarily symmetric, the sum of the elements in the third row is the degree of ν I \nu_iν I, and the sum of the elements in the JJJ column is the degree of νj\nu_jνj

For example,

summary

The graph corresponds to the adjacency matrix

  • The adjacency matrix can be drawn
  • We can draw the corresponding graph with the neighbor matrix

Weighted adjacency matrix for weighted directed graphs

If a directed graph D=(V,E)D=(V,E) is assigned a number to each edge of D=(V,E), DDD is called a weighted directed graph

Let D=(V,E)D=(V,E)D=(V,E) D=(V,E) is a simple weighted digraph, V={ν1,ν2… That argument n} V = \ {\ nu_1 \ nu_2,… , \ nu_n \} V = {argument 1, argument, 2,… , argument n}, DDD adjacency matrix of A = (aij) n * nA = (a_ {ij}) _ {n * n} A = n * n (aij), one of them

W_ {ij}, if (, \ \ nu_i nu_j) \ in E and w_ {ij} it is the right \ \ 0, if I = = j \ \ \ infty, if (, \ \ nu_i nu_j) \ \ notin E end {cases}

For example,

The weighted adjacency matrix of a weighted undirected graph is similar but symmetric

1.3.2 Association matrix

The incidence matrix of an undirected graph

Let G=(V,E)G=(V,E)G=(V,E) G=(V,E) is an undirected graph, V={ν1,ν2,…. That argument n} V = \ {\ nu_1 \ nu_2,… , \ nu_n \} V = {argument 1, argument, 2,… That argument n}, E = {e1, e2,… ,em}E=\{e_1,e_2,… ,e_m\}E={e1,e2,… , em}, GGG correlation matrix M = n * (mij) mM = (m_ {ij}) _ {n * M} M = (mij) n * M, and one of them

2, if e_j is ring \\ 1 on \nu_i, if \nu_i is associated with \\ 0, if \nu_i is not associated with e_j \end{cases}

The sum of the elements in each column of the association matrix of an undirected graph is 2, and the sum of the elements in the third row is the degree of ν I \nu_iν I

The association matrix of a simple graph is the (0,1) matrix

For example,

The incidence matrix of a digraph

Let G=(V,E)G=(V,E)G=(V,E) G=(V,E) is a directed acyclic digraph, V={ν1,ν2,…. That argument n} V = \ {\ nu_1 \ nu_2,… , \ nu_n \} V = {argument 1, argument, 2,… That argument n}, E = {e1, e2,… ,em}E=\{e_1,e_2,… ,e_m\}E={e1,e2,… , em}, GGG correlation matrix M = n * (mij) mM = (m_ {ij}) _ {n * M} M = (mij) n * M, and one of them

1, if \nu_i is the start of e_j \\ -1, if \nu_i is the end of e_j \\ 0, other \end{cases}

The sum of each column of the correlation matrix of a digraph is zero. The number of “1” in each row is the number of exits of the corresponding vertices, and the number of “-1” is the number of entries of the corresponding vertices; The vertices corresponding to rows completely “0” are outliers

1.3.3 edge matrix

conclusion

Description:

  • Refer to the textbook Graph Theory
  • With the book concept explanation combined with some of their own understanding and thinking

The essay is just a study note, recording a process from 0 to 1

Hope to have a little help to you, if there is a mistake welcome small partners correct