0
Follow
0
View

# If the adjacency matrix of a graph is an upper triangular moment with zero diagonal elements

duanduan630 注册会员
2023-02-28 00:32

directed acyclic graph.

For an adjacency matrix of a digraph, the elements on the diagonal represent the relation of the node itself, which should be 0 in general. If it is an upper triangular matrix, it means that only some nodes have directed edges, and there are no loops. Therefore, the graph is a directed acyclic graph.

2023-02-28 00:32

package from < a href =" https://blog.csdn.net/hihell" target="_blank"> The dream eraser Storm group based on the GPT "secret"

B. Connected graph.

An upper triangular matrix where the diagonal elements are zero indicates that the graph is undirected, because for every vertex i, if there is an edge from i to j, there must be an edge from j to i, so the adjacency matrix is symmetric and the upper and lower triangular elements are equal. Since the diagonal elements are all 0, there is no self-loop. Since the upper triangular element of the adjacency matrix represents a directed edge, the graph is an undirected graph, and the diagonal elements of the upper triangular matrix are all zero, indicating that the graph has no double edge, that is, each edge only appears once. If and only if the graph is connected, the graph satisfies the upper triangular matrix with zero diagonal elements. Therefore, the graph is a connected graph.

xianyuxuyang 注册会员

Publish Time
2023-02-28 00:32
Update Time
2023-02-28 00:32